The Efficiency of Resource Allocation Mechanisms for Budget-Constrained Users

DOI10.1287/MOOR.2020.1070zbMATH Open1468.91063arXiv1707.03551OpenAlexW3117412622MaRDI QIDQ5000644FDOQ5000644

Authors: I. Caragiannis, Alexandros A. Voudouris 

Publication date: 15 July 2021

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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 [Mathematics of Operations Research, 2004], 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 multi-user 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.

Full work available at URL: https://arxiv.org/abs/1707.03551

Recommendations

• Efficient resource allocation under multi-unit demand
• Assigning resources to budget-constrained agents
• Improved algorithms for resource allocation under varying capacity
• Improved algorithms for resource allocation under varying capacity
• Stable and efficient resource allocation under weak priorities
• On the efficiency of the proportional allocation mechanism for divisible resources
• On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources
• On Efficient Resource Allocation in Communication Networks
• scientific article; zbMATH DE number 2086936

zbMATH Keywords

resource allocationprice of anarchyliquid welfare

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Welfare economics (91B15) Algorithmic game theory and complexity (91A68)

Cites Work

• Worst-case equilibria
• Rate control for communication networks: shadow prices, proportional fairness and stability
• Efficiency of scalar-parameterized mechanisms
• Composable and efficient mechanisms
• Efficiency Loss in a Network Resource Allocation Game
• On the efficiency of the proportional allocation mechanism for divisible resources
• Efficiency Guarantees in Auctions with Budgets
• The price of anarchy and the design of scalable resource allocation mechanisms
• Welfare guarantees for proportional allocations
• Liquid price of anarchy
• Liquid welfare maximization in auctions with multiple items
• Intrinsic robustness of the price of anarchy
• The Price of Anarchy in Auctions
• A note on the efficiency of position mechanisms with budget constraints

Cited In (7)

• Resource Pooling and Cost Allocation Among Independent Service Providers
• Walrasian pricing in multi-unit auctions
• Auction design for value maximizers with budget and return-on-spend constraints
• Efficiency of scalar-parameterized mechanisms
• Online random sampling for budgeted settings
• A note on the efficiency of position mechanisms with budget constraints
• The Stackelberg equilibria of the Kelly mechanism

This page was built for publication: The Efficiency of Resource Allocation Mechanisms for Budget-Constrained Users

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5000644)