| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
08 February 2025 |
|
| | | |
|
Article overview
| |
|
The Price of Anarchy in One-Sided Allocation Problems with Multi-Unit Demand Agents | Sissi Jiang
; Ndiame Ndiaye
; Adrian Vetta
; Eggie Wu
; | Date: |
3 Jan 2023 | Abstract: | 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
$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 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(sqrt{n}cdot log n)$ for
the one-sided allocation problem with multi-unit demand agents. This result is
near tight. | Source: | arXiv, 2301.01367 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|