Christodoulou, George, Gkatzelis, Vasilis, Latifian, Mohamad and Sgouritsa, Alkmini
(2020)
Resource-Aware Protocols for Network Cost-Sharing Games.
In: EC '20: The 21st ACM Conference on Economics and Computation, 2020-7-13 - 2020-7-17.
|
Text
EC20.pdf - Author Accepted Manuscript Download (446kB) | Preview |
Abstract
We study the extent to which decentralized cost-sharing protocols can achieve good price of anarchy (PoA) bounds in network cost-sharing games with $n$ agents. We focus on the model of resource-aware protocols, where the designer has prior access to the network structure and can also increase the total cost of an edge(overcharging), and we study classes of games with concave or convex cost functions. We first consider concave cost functions and our main result is a cost-sharing protocol for symmetric games on directed acyclic graphs that achieves a PoA of $2+\varepsilon$ for some arbitrary small positive $\varepsilon$, which improves to $1+\varepsilon$ for games with at least two players. We also achieve a PoA of 1 for series-parallel graphs and show that no protocol can achieve a PoA better than $\Omega(\sqrt{n})$ for multicast games. We then also consider convex cost functions and prove analogous results for series-parallel networks and multicast games, as well as a lower bound of $\Omega(n)$ for the PoA on directed acyclic graphs without the use of overcharging.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Additional Information: | Full version of a paper published at Economics and Computation (EC) 2020 |
| Uncontrolled Keywords: | cs.GT, cs.GT, 91A43, 91A11 |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 08 Jun 2020 09:03 |
| Last Modified: | 18 Nov 2023 22:48 |
| DOI: | 10.1145/3391403.3399528 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3089751 |
Dimensions
Dimensions
