Abstract
We study the subclass of singleton congestion games in which there are identical resources with increasing cost functions. In this domain, we prove that there always exists an outcome that is resilient to weakly-improving deviations by singletons (i.e., the outcome is a Nash equilibrium), by the grand coalition (i.e., the outcome is Pareto efficient), and by coalitions with respect to an a priori given partition coalition structure (i.e., the outcome is a partition equilibrium). To our knowledge, this is the strongest existence guarantee in the literature on congestion games when weakly-improving deviations are considered. Our proof technique gives the false impression of a potential function argument but it is a novel application of proof by contradiction.
This work is supported by The Scientific and Technological Research Council of Turkey (TÜBİTAK) through grant 118E126.
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
Similar content being viewed by others
Notes
- 1.
See Feldman and Tennenholtz [7] for a very simple ISCG instance, with only three agents and two resources, for which a super-strong equilibrium does not exist.
References
Altman, E., et al.: Blockchain competition between miners: a game theoretic perspective. Front. Blockchain 2 (2020)
Anshelevich, E., Caskurlu, B., Hate, A.: Partition equilibrium always exists in resource selection games. Theory Comput. Syst. 53(1), 73–85 (2013)
van den Berg, J., Guy, S.J., Lin, M., Manocha, D.: Reciprocal n-body collision avoidance. In: Pradalier, C., Siegwart, R., Hirzinger, G. (eds.) Robotics Research, pp. 3–19. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-19457-3_1
Bilò, V., Gourvès, L., Monnot, J.: Project games. In: Heggernes, P. (ed.) CIAC 2019. LNCS, vol. 11485, pp. 75–86. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17402-6_7
Caskurlu, B., Ekici, O., Erdem Kizilkaya, F.: On existence of equilibrium under social coalition structures. In: Chen, J., Feng, Q., Xu, J. (eds.) TAMC 2020. LNCS, vol. 12337, pp. 263–274. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-59267-7_23
Caskurlu, B., Ekici, Ö., Kizilkaya, F.E.: On efficient computation of equilibrium under social coalition structures. Turkish J. Electr. Eng. Comput. Sci. 28(3), 1686–1698 (2020)
Feldman, M., Tennenholtz, M.: Structured coalitions in resource selection games. ACM Trans. Intell. Syst. Technol. 1(1), 1–21 (2010)
Harks, T., Klimm, M., Möhring, R.H.: Strong Nash equilibria in games with the lexicographical improvement property. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 463–470. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10841-9_43
Hoefer, M., Penn, M., Polukarov, M., Skopalik, A., Vöcking, B.: Considerate equilibrium. In: International Joint Conference on Artificial Intelligence (IJCAI). ACM Press (2011)
Holzman, R., Law-Yone, N.: Strong equilibrium in congestion games. Games Econ. Behav. 21(1–2), 85–101 (1997)
Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., Sun, Q.: Fast and compact: a simple class of congestion games. In: Proceedings of the 20th National Conference on Artificial Intelligence (AAAI), vol. 2, pp. 489–494. AAAI Press (2005)
Rahwan, T., Michalak, T.P., Wooldridge, M., Jennings, N.R.: Coalition structure generation: a survey. Artif. Intell. 229, 139–174 (2015)
Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2(1), 65–67 (1973)
Wardrop, J.G.: Some theoretical aspects of road traffic research. Proc. Inst. Civ. Eng. 1(3), 325–362 (1952)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Caskurlu, B., Ekici, Ö., Kizilkaya, F.E. (2021). On Singleton Congestion Games with Resilience Against Collusion. In: Chen, CY., Hon, WK., Hung, LJ., Lee, CW. (eds) Computing and Combinatorics. COCOON 2021. Lecture Notes in Computer Science(), vol 13025. Springer, Cham. https://doi.org/10.1007/978-3-030-89543-3_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-89543-3_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-89542-6
Online ISBN: 978-3-030-89543-3
eBook Packages: Computer ScienceComputer Science (R0)