Optimal Item Pricing for Max-Min Greedy Matching
Event details
| Date | 21.08.2025 |
| Hour | 13:00 › 15:00 |
| Speaker | Aruzhan Amanbayeva |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Andrés Cristi
Co-examiner: Prof. Michael Kapralov
Abstract
In our problem we have $n$ buyers, $n$ items, and valuations $w_{ij} \geq 0$ that buyer $i$ values item $j$ at. We set prices $p_j \geq 0$ for each item $j\in [n]$, and after that, the buyers arrive in adversarial order picking an available item $j$ that maximizes their utility $u_i = max_{j \text{ is available}} w_{ij}-p_j$ if the maximum utility is nonnegative and does not pick any item otherwise. This results in a matching $M$. Our goal is to set the prices that will maximize total value of the resulting matching, $\sum_{ij \in M}w_{ij}$.
Selected papers
coming soon
Exam president: Prof. Ola Svensson
Thesis advisor: Prof. Andrés Cristi
Co-examiner: Prof. Michael Kapralov
Abstract
In our problem we have $n$ buyers, $n$ items, and valuations $w_{ij} \geq 0$ that buyer $i$ values item $j$ at. We set prices $p_j \geq 0$ for each item $j\in [n]$, and after that, the buyers arrive in adversarial order picking an available item $j$ that maximizes their utility $u_i = max_{j \text{ is available}} w_{ij}-p_j$ if the maximum utility is nonnegative and does not pick any item otherwise. This results in a matching $M$. Our goal is to set the prices that will maximize total value of the resulting matching, $\sum_{ij \in M}w_{ij}$.
Selected papers
coming soon
Practical information
- General public
- Free
Contact
- edic@epfl.ch