Designing Cost-Sharing Methods for Bayesian Games


Christodoulou, George, Leonardi, Stefano and Sgouritsa, Alkmini (2019) Designing Cost-Sharing Methods for Bayesian Games. THEORY OF COMPUTING SYSTEMS, 63 (1). pp. 4-25.

This is the latest version of this item.

[img] Text
main.pdf - Author Accepted Manuscript
Available under License : See the attached licence file.
Download (382kB)

Abstract

We study the design of cost-sharing protocols for two fundamental resource allocation problems, the <i>Set Cover</i> and the <i>Steiner Tree Problem</i>, 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. <i>the Bayesian Price of Anarchy (PoA)</i> 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 <i>Oblivious Stochastic</i> 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 <i>anonymous</i> posted prices which are desirable because they are easy to implement and, as we show, induce <i>dominant strategies</i> for the players.

Item Type: Article
Uncontrolled Keywords: Price of anarchy, Bayesian games, Network design, Cost-sharing games
Depositing User: Symplectic Admin
Date Deposited: 08 Jun 2020 07:49
Last Modified: 18 Jan 2023 23:59
DOI: 10.1007/s00224-017-9832-3
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3077467

Available Versions of this Item

Dimensions
Altmetric
CORE (COnnecting REpositories)