Can I read The Price of Anarchy of the Asymmetric One-Sided Allocation Problem on EtoBox?

The Price of Anarchy of the Asymmetric One-Sided Allocation Problem by Jiang, Sissi; Ndiaye, Ndiame; Vetta, Adrian; Wu, Eggie is a scholarly article available to read on EtoBox.

What is The Price of Anarchy of the Asymmetric One-Sided Allocation Problem about?

We study fair mechanisms for the (asymmetric) one-sided allocation problem with m items and n multi-unit demand agents with additive, unit-sum valuations. The symmetric case (m=n), the one-sided matching problem, has been studied extensively for the class of unit demand agents, in particular with respect to the folklore Random Priority mechanism and the Probabilistic Serial mechanism, introduced by Bogomolnaia and Moulin. Under the assumption of unit-sum valuation functions, Christodoulou et al. proved that the price of anarchy is $\Theta(\sqrt{n})$ in the one-sided matching problem for both the Random Priority and Probabilistic Serial mechanisms. Whilst both Random Priority and Probabilistic Serial are ordinal mechanisms, these approximation guarantees are the best possible even for the broader class of cardinal mechanisms. To extend these results to the general setting there are two technical obstacles. One, asymmetry ($m\neq n$) is problematic especially when the number of items is much greater than the number of items. Two, it is necessary to study multi-unit demand agents rather than simply unit demand agents. Our approach is to study a cardinal mechanism variant of Probabilis

Author

Jiang, Sissi; Ndiaye, Ndiame; Vetta, Adrian; Wu, Eggie

Published

2023

Language

EN