Abstract
We study Congestion Games with non-increasing cost functions (Cost Sharing Games) from a complexity perspective and resolve their computational hardness, which has been an open question. Specifically we prove that when the cost functions have the form f(x) = c r /x (Fair Cost Allocation) then it is PLS-complete to compute a Pure Nash Equilibrium even in the case where strategies of the players are paths on a directed network. For cost functions of the form f(x) = c r (x)/x, where c r (x) is a non-decreasing concave function we also prove PLS-completeness in undirected networks. Thus we extend the results of [7,1] to the non-increasing case. For the case of Matroid Cost Sharing Games, where tractability of Pure Nash Equilibria is known by [1] we give a greedy polynomial time algorithm that computes a Pure Nash Equilibrium with social cost at most the potential of the optimal strategy profile. Hence, for this class of games we give a polynomial time version of the Potential Method introduced in [2] for bounding the Price of Stability.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ackermann, H., Röglin, H., Vöcking, B.: On the impact of combinatorial structure on congestion games. J. ACM 55(6) (2008)
Anshelevich, E., Dasgupta, A., Kleinberg, J.M., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: FOCS, pp. 295–304. IEEE Computer Society, Los Alamitos (2004)
Balcan, M.-F., Blum, A., Mansour, Y.: Circumventing the price of anarchy: Leading dynamics to good behavior. In: ICS, pp. 200–213 (2010)
Charikar, M., Karloff, H.J., Mathieu, C., Naor, J., Saks, M.E.: Online multicast with egalitarian cost sharing. In: SPAA, pp. 70–76. ACM, New York (2008)
Chekuri, C., Chuzhoy, J., Lewin-Eytan, L., Naor, J., Orda, A.: Non-cooperative multicast and facility location games. IEEE Journal on Selected Areas in Communications 25(6), 1193–1206 (2007)
Epstein, A., Feldman, M., Mansour, Y.: Strong equilibrium in cost sharing connection games. In: EC, pp. 84–92. ACM, New York (2007)
Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure nash equilibria. In: STOC, pp. 604–612. ACM, New York (2004)
Hansen, T.D., Telelis, O.: Improved bounds for facility location games with fair cost allocation. In: COCOA 2009. LNCS, vol. 5573, pp. 174–185. Springer, Heidelberg (2009)
Harks, T., Hoefer, M., Klimm, M., Skopalik, A.: Computing pure nash and strong equilibria in bottleneck congestion games. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol. 6347, pp. 29–38. Springer, Heidelberg (2010)
Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., Sun, Q.: Fast and compact: A simple class of congestion games. In: AAAI, pp. 489–494 (2005)
Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79–100 (1988)
Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM 41(5), 960–981 (1994)
Rosenthal, R.W.: A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory 2(1), 65–67 (1973)
Schäffer, A.A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM J. Comput. 20(1), 56–87 (1991)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Matroids, Trees, Stable Sets, vol. B (2003)
Skopalik, A., Vöcking, B.: Inapproximability of pure nash equilibria. In: STOC, pp. 355–364. ACM, New York (2008)
Syrgkanis, V.: Equilibria in Congestion Game Models. Undergraduate Diploma Thesis (2009), http://www.cs.cornell.edu/~vasilis/thesis.pdf
Tardos, E., Kleinberg, J.: Algorithm Design, ch. 12. Addison-Wesley, Reading (2005)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Syrgkanis, V. (2010). The Complexity of Equilibria in Cost Sharing Games. In: Saberi, A. (eds) Internet and Network Economics. WINE 2010. Lecture Notes in Computer Science, vol 6484. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17572-5_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-17572-5_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17571-8
Online ISBN: 978-3-642-17572-5
eBook Packages: Computer ScienceComputer Science (R0)