The Price of Anarchy in One-Sided Allocation Problems with Multi-Unit Demand Agents
share
We study the one-sided allocation problem with multi-unit demand agents. The special case of the one-sided matching problem with unit demand agents has been studied extensively. The primary focus has been on the folklore Random Priority mechanism and the Probabilistic Serial mechanism, introduced by Bogomolnaia and Moulin, with emphasis on structural properties, incentives, and performance with respect to social welfare. Under the standard assumption of unit-sum valuation functions, Christodoulou et al. proved that the price of anarchy is Θ(√(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 of one-sided allocation problems with multi-unit demand agents, we consider a natural cardinal mechanism variant of Probabilistic Serial, which we call Cardinal Probabilistic Serial. We present structural theorems for this mechanism and use them to show that Cardinal Probabilistic Serial has a price of anarchy of O(√(n)·log n) for the one-sided allocation problem with multi-unit demand agents. This result is near tight.
READ FULL TEXT