Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3667
Articles: 2'599'751
Articles rated: 2609

08 February 2025
 
  » arxiv » 2301.01367

 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
AbstractWe 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   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  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.






ScienXe.org
» my Online CV
» Free

home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2025 - Scimetrica