Document Open Access Logo

Efficient Black-Box Reductions for Separable Cost Sharing

Authors Tobias Harks, Martin Hoefer, Anja Huber, Manuel Surek

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.154.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Author Details

Tobias Harks
  • Universität Augsburg, Institut für Mathematik, Augsburg, Germany
Martin Hoefer
  • Goethe-Universität Frankfurt am Main, Institut für Informatik, Frankfurt am Main, Germany
Anja Huber
  • Universität Augsburg, Institut für Mathematik, Augsburg, Germany
Manuel Surek
  • Universität Augsburg, Institut für Mathematik, Augsburg, Germany

Funding

The research of the authors from Augsburg was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - HA 8041/1-1.

Cite As Get BibTex

Tobias Harks, Martin Hoefer, Anja Huber, and Manuel Surek. Efficient Black-Box Reductions for Separable Cost Sharing. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 154:1-154:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.154

Abstract

In cost sharing games with delays, a set of agents jointly uses a finite subset of resources. Each resource has a fixed cost that has to be shared by the players, and each agent has a non-shareable player-specific delay for each resource. A prominent example is uncapacitated facility location (UFL), where facilities need to be opened (at a shareable cost) and clients want to connect to opened facilities. Each client pays a cost share and his non-shareable physical connection cost. Given any profile of subsets used by the agents, a separable cost sharing protocol determines cost shares that satisfy budget balance on every resource and separability over the resources. Moreover, a separable protocol guarantees existence of pure Nash equilibria in the induced strategic game for the agents.
In this paper, we study separable cost sharing protocols in several general combinatorial domains. We provide black-box reductions to reduce the design of a separable cost sharing protocol to the design of an approximation algorithm for the underlying cost minimization problem. In this way, we obtain new separable cost sharing protocols in games based on arbitrary player-specific matroids, single-source connection games without delays, and connection games on n-series-parallel graphs with delays. All these reductions are efficiently computable - given an initial allocation profile, we obtain a profile of no larger cost and separable cost shares turning the profile into a pure Nash equilibrium. Hence, in these domains any approximation algorithm can be used to obtain a separable cost sharing protocol with a price of stability bounded by the approximation factor.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
  • Theory of computation → Exact and approximate computation of equilibria
  • Theory of computation → Network games
Keywords
  • Cost Sharing
  • Price of Stability
  • Matroids
  • Connection Games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nir Andelman, Michal Feldman, and Yishay Mansour. Strong price of anarchy. Games Econom. Behav., 65(2):289-317, 2009. Google Scholar
  2. Elliot Anshelevich and Bugra Caskurlu. Exact and approximate equilibria for optimal group network formation. Theor. Comput. Sci., 412(39):5298-5314, 2011. Google Scholar
  3. Elliot Anshelevich and Bugra Caskurlu. Price of stability in survivable network design. Theory Comput. Syst., 49(1):98-138, 2011. Google Scholar
  4. Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Tim Roughgarden, Éva Tardos, and Tom Wexler. The price of stability for network design with fair cost allocation. SIAM J. Comput., 38(4):1602-1623, 2008. URL: http://dx.doi.org/10.1137/070680096.
  5. Elliot Anshelevich, Anirban Dasgupta, Éva Tardos, and Tom Wexler. Near-optimal network design with selfish agents. Theory of Computing, 4(1):77-109, 2008. Google Scholar
  6. Guy Avni and Tami Tamir. Cost-sharing scheduling games on restricted unrelated machines. Theor. Comput. Sci., 646:26-39, 2016. Google Scholar
  7. Mohammadhossein Bateni, Mohammadtaghi Hajiaghayi, and Dániel Marx. Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. JACM, 58(5):21:1-21:37, 2011. Google Scholar
  8. Vittorio Bilò, Angelo Fanelli, Michele Flammini, and Luca Moscardelli. When ignorance helps: Graphical multicast cost sharing games. Theoretical Computer Science, 411(3):660-671, 2010. Google Scholar
  9. Vittorio Bilò, Michele Flammini, and Luca Moscardelli. The price of stability for undirected broadcast network design with fair cost allocation is constant. In Proc. 54th Symp. Foundations of Computer Science (FOCS), pages 638-647, 2013. Google Scholar
  10. C. Bird. On cost allocation for a spanning tree: A game theoretic approach. Networks, 6:335-350, 1976. Google Scholar
  11. Jaroslaw Byrka and Karen Aardal. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM Journal on Computing, 39(6):2212-2231, 2010. Google Scholar
  12. Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. J. ACM, 60(1):6:1-6:33, 2013. Google Scholar
  13. Ioannis Caragiannis, Vasilis Gkatzelis, and Cosimo Vinci. Coordination mechanisms, cost-sharing, and approximation algorithms for scheduling. In Nikhil R. Devanur and Pinyan Lu, editors, Web and Internet Economics, pages 74-87, 2017. Google Scholar
  14. Jean Cardinal and Martin Hoefer. Non-cooperative facility location and covering games. Theor. Comput. Sci., 411:1855-1876, March 2010. Google Scholar
  15. Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, and Sudipto Guha. Approximation algorithms for directed Steiner problems. J. Algorithms, 33(1):192-200, 1999. Google Scholar
  16. Chandra Chekuri and Martin Pál. A recursive greedy algorithm for walks in directed graphs. In Proc. 46th Symp. Foundations of Computer Science (FOCS), pages 245-253, 2005. Google Scholar
  17. Ho-Lin Chen, Tim Roughgarden, and Gregory Valiant. Designing network protocols for good equilibria. SIAM J. Comput., 39(5):1799-1832, 2010. Google Scholar
  18. Xujin Chen, Zhuo Diao, and Xiaodong Hu. Network characterizations for excluding Braess’s paradox. Theory Comput. Syst., 59(4):747-780, 2016. Google Scholar
  19. Giorgos Christodoulou, Vasilis Gkatzelis, and Alkmini Sgouritsa. Cost-sharing methods for scheduling games under uncertainty. In Proc. 18th ACM Conf. Economics and Computation (EC), pages 441-458, 2017. Google Scholar
  20. Giorgos Christodoulou, Stefano Leonardi, and Alkmini Sgouritsa. Designing cost-sharing methods for bayesian games. In Proc. 9th Intl. Symp. Algorithmic Game Theory (SAGT), pages 327-339, 2016. Google Scholar
  21. Giorgos Christodoulou and Alkmini Sgouritsa. Designing networks with good equilibria under uncertainty. In Proc. 27th Symp. Discrete Algorithms (SODA), pages 72-89, 2016. Google Scholar
  22. Xiaotie Deng, Toshihide Ibaraki, and Hiroshi Nagamochi. Algorithmic aspects of the core of combinatorial optimization games. Math. Oper. Res., 24(3):751-766, 1999. Google Scholar
  23. Yann Disser, Andreas Feldmann, Max Klimm, and Matús Mihalák. Improving the H_k-bound on the price of stability in undirected shapley network design games. Theoret. Comput. Sci., 562:557-564, 2015. Google Scholar
  24. Michal Feldman and Tami Tamir. Conflicting congestion effects in resource allocation games. Oper. Res., 60(3):529-540, 2012. Google Scholar
  25. Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetzky, and Ronen Shabo. On the price of stability for designing undirected networks with fair cost allocations. In Proc. 33rd Intl. Coll. Automata, Languages and Programming (ICALP), volume 1, pages 608-618, 2006. Google Scholar
  26. Naveen Garg, Goran Konjevod, and R Ravi. A polylogarithmic approximation algorithm for the Group Steiner tree problem. J. Algorithms, 37:66-84, 2000. Google Scholar
  27. Konstantinos Georgiou and Chaitanya Swamy. Black-box reductions for cost-sharing mechanism design. In Proc. 23rd Symp. Discrete Algorithms (SODA), pages 896-913, 2012. Google Scholar
  28. Michel X. Goemans and Martin Skutella. Cooperative facility location games. J. Algorithms, 50(2):194-214, 2004. Google Scholar
  29. Daniel Granot and Gur Huberman. On minimum cost spanning tree games. Math. Prog., 21:1-18, 1981. Google Scholar
  30. Daniel Granot and Michael Maschler. Spanning network games. Internat. J. Game Theory, 27:467-500, 1998. Google Scholar
  31. Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. J. Algorithms, 31:228-248, 1999. Google Scholar
  32. Thomas Dueholm Hansen and Orestis Telelis. On pure and (approximate) strong equilibria of facility location games. In Christos Papadimitriou and Shuzhong Zhang, editors, Internet and Network Economics, pages 490-497, 2008. Google Scholar
  33. Thomas Dueholm Hansen and Orestis Telelis. Improved bounds for facility location games with fair cost allocation. In Proc. 3rd Intl. Conf. Combinatorial Optimization and Applications (COCOA), pages 174-185, 2009. Google Scholar
  34. Tobias Harks, Martin Hoefer, Anja Huber, and Manuel Surek. Efficient black-box reductions for separable cost sharing, 2018. URL: https://arxiv.org/abs/1802.10351.
  35. Tobias Harks, Anja Huber, and Manuel Surek. A characterization of undirected graphs admitting optimal cost shares. In Nikhil R. Devanur and Pinyan Lu, editors, Web and Internet Economics, pages 237-251, Cham, 2017. Springer International Publishing. Google Scholar
  36. Tobias Harks and Britta Peis. Resource buying games. Algorithmica, 70(3):493-512, 2014. Google Scholar
  37. Tobias Harks and Philipp von Falkenhausen. Optimal cost sharing for capacitated facility location games. European Journal of Operational Research, 239(1):187-198, 2014. Google Scholar
  38. Martin Hoefer. Non-cooperative tree creation. Algorithmica, 53:104-131, 2009. Google Scholar
  39. Martin Hoefer. Competitive cost sharing with economies of scale. Algorithmica, 60:743-765, 2011. Google Scholar
  40. Martin Hoefer. Strategic cooperation in cost sharing games. Internat. J. Game Theory, 42(1):29-53, 2013. Google Scholar
  41. Kamal Jain and Vijay Vazirani. Applications of approximation algorithms to cooperative games. In Proc. 33rd Symp. Theory of Computing (STOC), pages 364-372, 2001. Google Scholar
  42. Jochen Könemann, Stefano Leonardi, Guido Schäfer, and Stefan van Zwam. A group-strategyproof cost sharing mechanism for the steiner forest game. SIAM J. Comput., 37(5):1319-1341, 2008. Google Scholar
  43. Euiwoong Lee and Katrina Ligett. Improved bounds on the price of stability in network cost sharing games. In Proc. 14th Conf. Electronic Commerce (EC), pages 607-620, 2013. Google Scholar
  44. Jian Li. An o(log(n)/log(log(n))) upper bound on the price of stability for undirected shapley network design games. Inform. Process. Lett., 109(15):876-878, 2009. Google Scholar
  45. Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput., 222:45-58, 2013. Google Scholar
  46. Nimrod Megiddo. Cost allocation for Steiner trees. Networks, 8(1):1-6, 1978. Google Scholar
  47. Hervé Moulin and Scott Shenker. Strategyproof sharing of submodular costs: budget balance versus efficiency. Econom. Theory, 18(3):511-533, 2001. Google Scholar
  48. Martin Pál and Éva Tardos. Group strategyproof mechanisms via primal-dual algorithms. In FOCS, pages 584-593, 2003. Google Scholar
  49. Gabriel Robins and Alexander Zelikovsky. Tighter bounds for graph Steiner tree approximation. SIAM J. Disc. Math., 19(1):122-134, 2005. Google Scholar
  50. Robert Rosenthal. A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory, 2:65-67, 1973. Google Scholar
  51. Vasilis Syrgkanis. The complexity of equilibria in cost sharing games. In A. Saberi, editor, Proc. 6th Internat. Workshop on Internet and Network Econom., LNCS, pages 366-377, 2010. Google Scholar
  52. Arie Tamir. On the core of network synthesis games. Math. Prog., 50:123-135, 1991. Google Scholar
  53. Phlipp von Falkenhausen and Tobias Harks. Optimal cost sharing for resource selection games. Math. Oper. Res., 38(1):184-208, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact