Welfare guarantees for proportional allocations

DOI10.1007/S00224-016-9674-4MaRDI QIDQ506519zbMATH OpenOpenAlexFDO

Authors I. Caragiannis, Alexandros A. Voudouris

Publication date 1 February 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.3447, http://repository.essex.ac.uk/27912/1/bandwidth.journal.v2.pdf

zbMATH Keywords

price of anarchyalgorithmic game theoryBayes-Nash equilibriumproportional allocation mechanism

Mathematics Subject Classification ID

Applications of game theory (91A80) Auctions, bargaining, bidding and selling, and other market models (91B26) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: According to the proportional allocation mechanism from the network optimization literature, users compete for a divisible resource -- such as bandwidth -- by submitting bids. The mechanism allocates to each user a fraction of the resource that is proportional to her bid and collects an amount equal to her bid as payment. Since users act as utility-maximizers, this naturally defines a proportional allocation game. Recently, Syrgkanis and Tardos (STOC 2013) quantified the inefficiency of equilibria in this game with respect to the social welfare and presented a lower bound of 26.8% on the price of anarchy over coarse-correlated and Bayes-Nash equilibria in the full and incomplete information settings, respectively. In this paper, we improve this bound to 50% over both equilibrium concepts. Our analysis is simpler and, furthermore, we argue that it cannot be improved by arguments that do not take the equilibrium structure into account. We also extend it to settings with budget constraints where we show the first constant bound (between 36% and 50%) on the price of anarchy of the corresponding game with respect to an effective welfare benchmark that takes budgets into account.

Recommendations

• Welfare guarantees for proportional allocations
• On the Efficiency of the Proportional Allocation Mechanism for Divisible Resources
• On the efficiency of the proportional allocation mechanism for divisible resources
• The price of anarchy of the proportional allocation mechanism revisited
• On the efficiency of markets with two-sided proportional allocation mechanisms

Cites work

• Bayesian Combinatorial Auctions
• Bounding the inefficiency of outcomes in generalized second price auctions
• Composable and efficient mechanisms
• Efficiency Guarantees in Auctions with Budgets
• Efficiency Loss in a Network Resource Allocation Game
• Inefficiency of standard multi-unit auctions
• Potential functions and the inefficiency of equilibria
• Simultaneous auctions are (almost) efficient
• The price of anarchy and the design of scalable resource allocation mechanisms
• The price of anarchy of the proportional allocation mechanism revisited
• Welfare guarantees for combinatorial auctions with item bidding
• Welfare guarantees for proportional allocations
• Worst-case equilibria

Cited in

(16)

• On the efficiency of markets with two-sided proportional allocation mechanisms
• The price of anarchy of the proportional allocation mechanism revisited
• Simple combinatorial auctions with budget constraints
• Automata, Languages and Programming
• Asymptotic efficiency of the proportional compensation scheme for a large number of producers
• On the efficiency of the proportional allocation mechanism for divisible resources
• The Efficiency of Resource Allocation Mechanisms for Budget-Constrained Users
• Welfare equivalent NNP under distributional objectives
• On proportional allocation in hedonic games
• Welfare means and equalizing transfers
• Quasi-proportional mechanisms: prior-free revenue maximization
• Fair welfare maximization
• Welfare guarantees for proportional allocations
• Distributed welfare games
• A note on the efficiency of position mechanisms with budget constraints
• Optimal Nash equilibria for bandwidth allocation

This page was built for publication: Welfare guarantees for proportional allocations

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