SODA Conference 2025 Conference Paper
A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization
- Shuchi Chawla 0001
- Dimitris Christou
- Trung Dang 0001
- Zhiyi Huang
- Gregory Kehne
- Rojin Rezvan
Author name cluster
Rojin Rezvan
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
3 papers
2 author rows
Possible papers
3IJCAI Conference 2022 Conference Paper
An EF2X Allocation Protocol for Restricted Additive Valuations
- Hannaneh Akrami
- Rojin Rezvan
- Masoud Seddighin
We study the problem of fairly allocating a set of indivisible goods to a set of n agents. Envy-freeness up to any good (EFX) criterion (which requires that no agent prefers the bundle of another agent after the removal of any single good) is known to be a remarkable analogue of envy-freeness when the resource is a set of indivisible goods. In this paper, we investigate EFX for restricted additive valuations, that is, every good has a non-negative value, and every agent is interested in only some of the goods. We introduce a natural relaxation of EFX called EFkX which requires that no agent envies another agent after the removal of any k goods. Our main contribution is an algorithm that finds a complete (i. e. , no good is discarded) EF2X allocation for restricted additive valuations. In our algorithm we devise new concepts, namely configuration and envy-elimination that might be of independent interest. We also use our new tools to find an EFX allocation for restricted additive valuations that discards at most n/2 -1 goods.
STOC Conference 2022 Conference Paper
Pricing ordered items
- Shuchi Chawla 0001
- Rojin Rezvan
- Yifeng Teng
- Christos Tzamos
We study the revenue guarantees and approximability of item pricing. Recent work shows that with n heterogeneous items, item-pricing guarantees an O (log n ) approximation to the optimal revenue achievable by any (buy-many) mechanism, even when buyers have arbitrarily combinatorial valuations. However, finding good item prices is challenging – it is known that even under unit-demand valuations, it is NP-hard to find item prices that approximate the revenue of the optimal item pricing better than O (√ n ).