The Price of Anarchy of Probabilistic Serial in One-Sided Allocation Problems

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 special 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 [6]. These are both fair mechanisms and attention has focused on their structural properties, incentives, and performance with respect to social welfare. Under the standard assumption of unit-sum valuation functions, Christodoulou et al. [10] proved that the price of anarchy is \(\varTheta (\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 of the one-sided allocation problems there are two technical obstacles. One, asymmetry ( \(m\ne n\) )is problematic especially when the number of items is much greater than the number of agents, \(m\gg n\) . Two, it is necessary to study multi-unit demand agents rather than simply unit demand agents. For this paper, our focus is on Probabilistic Serial. Our first main result is an upper bound of \(O(\sqrt{n}\cdot \log m)\) on the price of anarchy for the asymmetric one-sided allocation problem with multi-unit demand agents. We then present a complementary lower bound of \(\varOmega (\sqrt{n})\) for any fair mechanism. That lower bound is unsurprising. More intriguing is our second main result: the price of anarchy of Probabilistic Serial degrades with the number of items. Specifically, a logarithmic dependence on the number of items is necessary as we show a lower bound of \(\varOmega (\min \{n\, , \, \log m\})\) .