Designing Cost-Sharing Methods for Bayesian Games
Open Access
- 20 December 2017
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 63 (1) , 4-25
Abstract
We study the design of cost-sharing protocols for two fundamental resource allocation problems, the Set Cover and the Steiner Tree Problem, under environments of incomplete information (Bayesian model). Our objective is to design protocols where the worst-case Bayesian Nash equilibria have low cost, i.e. the Bayesian Price of Anarchy (PoA) is minimized. Although budget balance is a very natural requirement, it puts considerable restrictions on the design space, resulting in high PoA. We propose an alternative, relaxed requirement called budget balance in the equilibrium (BBiE). We show an interesting connection between algorithms for Oblivious Stochastic optimization problems and cost-sharing design with low PoA. We exploit this connection for both problems and we enforce approximate solutions of the stochastic problem, as Bayesian Nash equilibria, with the same guarantees on the PoA. More interestingly, we show how to obtain the same bounds on the PoA, by using anonymous posted prices which are desirable because they are easy to implement and, as we show, induce dominant strategies for the players.Keywords
Funding Information
- Engineering and Physical Sciences Research Council (EP/M008118/1, EP/K01000X/1)
- Royal Society Leverhulme Trust Senior Research Fellowship (LT140046)
- Google Focused award ”Algorithms for Large-scale Data analysis”
- EU FET project (317532 ”Multiplex”)
This publication has 58 references indexed in Scilit:
- The power of randomness in Bayesian optimal mechanism designGames and Economic Behavior, 2015
- Designing Network Protocols for Good EquilibriaSIAM Journal on Computing, 2010
- An upper bound on the price of stability for undirected Shapley network design gamesInformation Processing Letters, 2009
- Limitations of cross-monotonic cost-sharing schemesACM Transactions on Algorithms, 2008
- A simpler and better derandomization of an approximation algorithm for single source rent-or-buyOperations Research Letters, 2007
- Strategyproof cost-sharing mechanisms for set cover and facility location gamesDecision Support Systems, 2005
- Walrasian Equilibrium with Gross SubstitutesJournal of Economic Theory, 1999
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Charging and rate control for elastic trafficEuropean Transactions on Telecommunications, 1997
- Strategic Information TransmissionEconometrica, 1982