The Efficiency of Resource Allocation Mechanisms for Budget-Constrained Users

Ioannis Caragiannis () and Alexandros A. Voudouris ()
Additional contact information
Ioannis Caragiannis: Department of Computer Engineering and Informatics, University of Patras, 26504 Rion, Greece
Alexandros A. Voudouris: Department of Computer Science, University of Oxford, Oxford OX1 3QD, United Kingdom

Mathematics of Operations Research, 2021, vol. 46, issue 2, 503-523

Abstract: We study the efficiency of mechanisms for allocating a divisible resource. Given scalar signals submitted by all users, such a mechanism decides the fraction of the resource that each user will receive and a payment that will be collected from her. Users are self-interested and aim to maximize their utility (defined as their value for the resource fraction they receive minus their payment). Starting with the seminal work of Johari and Tsitsiklis, a long list of papers studied the price of anarchy (in terms of the social welfare—the total users’ value) of resource allocation mechanisms for a variety of allocation and payment rules. Here, we further assume that each user has a budget constraint that invalidates strategies that yield a payment that is higher than the user’s budget. This subtle assumption, which is arguably more realistic, constitutes the traditional price of anarchy analysis meaningless as the set of equilibria may change drastically and their social welfare can be arbitrarily far from optimal. Instead, we study the price of anarchy using the liquid welfare benchmark that measures efficiency taking budget constraints into account. We show a tight bound of 2 on the liquid price of anarchy of the well-known Kelly mechanism and prove that this result is essentially best possible among all multiuser resource allocation mechanisms. This comes in sharp contrast to the no-budget setting where there are mechanisms that considerably outperform Kelly in terms of social welfare and even achieve full efficiency. In our proofs, we exploit the particular structure of worst-case games and equilibria, which also allows us to design (nearly) optimal two-player mechanisms by solving simple differential equations.

Keywords: Primary: 91A68; secondary: 68Q25; 68W40; Primary: games/group decisions: noncooperative; secondary: games/group decisions: bidding/auctions; resource allocation; liquid welfare; price of anarchy (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1070 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:2:p:503-523

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().