×

Leadership in singleton congestion games: what is hard and what is easy. (English) Zbl 1482.91015

Summary: We study the problem of computing Stackelberg equilibria in Stackelberg games whose underlying structure is a congestion game, focusing on singleton congestion games, i.e., on congestion games where each player can choose a single resource, and assuming that one of them acts as leader while the other ones act as followers. We provide a comprehensive picture of the computational complexity of finding equilibria in these games, investigating different forms of commitment (pure-strategy and mixed-strategy) and followers’ tie-breaking rules (optimistic and pessimistic). We identify two features of such games, namely, identical/different action spaces and monotonic/generic cost functions, by which we provide a complete characterization of the cases in which the equilibrium-finding problem is either easy or hard. In particular, we show that, in the case where the action spaces are different, the cost the leader incurs in an optimistic or pessimistic Stackelberg equilibrium cannot be approximated in polynomial time up to any polynomial factor in the size of the game unless \(\mathsf{P} = \mathsf{NP} \), independently of the cost functions being monotonic or generic. This result holds even when the commitment is restricted to pure strategies. For general mixed-strategy commitments, we show that a similar result also holds when the players have generic cost functions, even if their action spaces are identical. Furthermore, we prove that the case with identical action spaces and monotonic cost functions is easy. We also improve the efficiency of a polynomial-time algorithm available in the literature for the computation of a socially optimal Nash equilibrium in non-Stackelberg singleton congestion games with identical action spaces and generic cost functions, and we extend it to the computation of a Stackelberg equilibrium for the case where the leader is restricted to playing pure strategies. For the cases in which the problem of finding an equilibrium is hard, we show how, in the optimistic setting where the followers break ties in favor of the leader, the problem can be formulated via mixed-integer linear programming techniques. We also provide an experimental evaluation of our algorithms both on random instances and on instances generated from our inapproximability reductions.

MSC:

91A14 Potential and congestion games
91A68 Algorithmic game theory and complexity
91A65 Hierarchical games (including Stackelberg games)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Marchesi, A.; Coniglio, S.; Gatti, N., Leadership in singleton congestion games, (IJCAI (2018))
[2] von Stackelberg, H., Marktform und Gleichgewicht (1934) · Zbl 1405.91003
[3] Conitzer, V.; Sandholm, T., Computing the optimal strategy to commit to, (Proceedings of the 7th ACM Conference on Electronic Commerce (2006)), 82-90
[4] von Stengel, B.; Zamir, S., Leadership games with convex strategy sets, Games Econ. Behav., 69, 2, 446-457 (2010) · Zbl 1230.91022
[5] Conitzer, V.; Korzhyk, D., Commitment to correlated strategies, (AAAI (2011)), 632-637
[6] Coniglio, S.; Gatti, N.; Marchesi, A., Pessimistic leader-follower equilibria with multiple followers, (IJCAI (2017)), 171-177
[7] Coniglio, S.; Gatti, N.; Marchesi, A., Computing a pessimistic leader-follower equilibrium with multiple followers: the mixed-pure case, CoRR · Zbl 1435.91046
[8] Smith, A.; Vorobeychik, Y.; Letchford, J., Multidefender security games on networks, Perform. Eval. Rev., 41, 4, 4-7 (2014)
[9] Lou, J.; Vorobeychik, Y., Equilibrium analysis of multi-defender security games, (IJCAI (2015))
[10] Laszka, A.; Lou, J.; Vorobeychik, Y., Multi-defender strategic filtering against spear-phishing attacks, (AAAI (2016))
[11] Lou, J.; Smith, A.; Vorobeychik, Y., Multidefender security games, IEEE Intell. Syst., 32, 1, 50-60 (2017)
[12] Gan, J.; Elkind, E.; Wooldridge, M., Stackelberg security games with multiple uncoordinated defenders, (AAMAS (2018))
[13] Castiglioni, M.; Marchesi, A.; Gatti, N., Be a leader or become a follower: the strategy to commit to with multiple leaders, (Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019 (2019)), 123-129
[14] Pang, J.-S.; Fukushima, M., Quasi-variational inequalities, generalized nash equilibria, and multi-leader-follower games, Comput. Manag. Sci., 2, 1, 21-56 (2005) · Zbl 1115.90059
[15] Leyffer, S.; Munson, T., Solving multi-leader-common-follower games, Optim. Methods Softw., 25, 4, 601-623 (2010) · Zbl 1201.90187
[16] Kulkarni, A.; Shanbhag, U., A shared-constraint approach to multi-leader multi-follower games, Set-Valued Var. Anal., 22, 4, 691-720 (2014) · Zbl 1307.91046
[17] Breton, M.; Alj, A.; Haurie, A., Sequential stackelberg equilibria in two-person games, J. Optim. Theory Appl., 59, 1, 71-97 (1988) · Zbl 0631.90100
[18] Paruchuri, P.; Pearce, J. P.; Marecki, J.; Tambe, M.; Ordonez, F.; Kraus, S., Playing games for security: an efficient exact algorithm for solving bayesian stackelberg games, (AAMAS (2008)), 895-902
[19] Kiekintveld, C.; Jain, M.; Tsai, J.; Pita, J.; Ordóñez, F.; Tambe, M., Computing optimal randomized resource allocations for massive security games, (AAMAS (2009)), 689-696
[20] An, B.; Pita, J.; Shieh, E.; Tambe, M.; Kiekintveld, C.; Marecki, J., Guards and Protect: next generation applications of security games, ACM SIGecom Exch., 10, 1, 31-34 (2011)
[21] Tambe, M., Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned (2011), Cambridge University Press · Zbl 1235.91005
[22] Labbé, M.; Marcotte, P.; Savard, G., A bilevel model of taxation and its application to optimal highway pricing, Manag. Sci., 44, 12-part-1, 1608-1622 (1998) · Zbl 0989.90014
[23] Labbé, M.; Violin, A., Bilevel programming and price setting problems, Ann. Oper. Res., 240, 1, 141-169 (2016) · Zbl 1342.90185
[24] Caprara, A.; Carvalho, M.; Lodi, A.; Woeginger, G. J., Bilevel knapsack with interdiction constraints, INFORMS J. Comput., 28, 2, 319-333 (2016) · Zbl 1343.90075
[25] Matuschke, J.; McCormick, S. T.; Oriolo, G.; Peis, B.; Skutella, M., Protection of flows under targeted attacks, Oper. Res. Lett., 45, 1, 53-59 (2017) · Zbl 1409.90042
[26] Amaldi, E.; Capone, A.; Coniglio, S.; Gianoli, L. G., Network optimization problems subject to max-min fair flow allocation, IEEE Commun. Lett., 17, 7, 1463-1466 (2013)
[27] Avenhaus, R.; Okada, A.; Zamir, S., Inspector leadership with incomplete information, (Game Equilibrium Models IV (1991), Springer), 319-361 · Zbl 0736.90089
[28] Sandholm, W. H., Evolutionary implementation and congestion pricing, Rev. Econ. Stud., 69, 3, 667-689 (2002) · Zbl 1025.91002
[29] Rosenthal, R. W., A class of games possessing pure-strategy nash equilibria, Int. J. Game Theory, 2, 1, 65-67 (1973) · Zbl 0259.90059
[30] Ackermann, H.; Röglin, H.; Vöcking, B., On the impact of combinatorial structure on congestion games, J. ACM, 55, 6, 25 (2008) · Zbl 1325.91010
[31] Ieong, S.; McGrew, R.; Nudelman, E.; Shoham, Y.; Sun, Q., Fast and compact: a simple class of congestion games, (AAAI (2005)), 489-494
[32] Chen, P.-A.; Lu, C.-J., Generalized mirror descents in congestion games, Artif. Intell., 241, 217-243 (2016) · Zbl 1406.91069
[33] Fotakis, D., A selective tour through congestion games, (Algorithms, Probability, Networks, and Games (2015), Springer), 223-241 · Zbl 1331.91009
[34] Suri, S.; Tóth, C. D.; Zhou, Y., Selfish load balancing and atomic congestion games, Algorithmica, 47, 1, 79-96 (2007) · Zbl 1107.68026
[35] Konur, D.; Geunes, J., Competitive multi-facility location games with non-identical firms and convex traffic congestion costs, Transp. Res., Part E, Logist. Transp. Rev., 48, 1, 373-385 (2012)
[36] Roughgarden, T., Selfish Routing and the Price of Anarchy, vol. 174 (2005), MIT press: MIT press Cambridge
[37] Monderer, D.; Shapley, L. S., Potential games, Games Econ. Behav., 14, 1, 124-143 (1996) · Zbl 0862.90137
[38] Fabrikant, A.; Papadimitriou, C.; Talwar, K., The complexity of pure nash equilibria, (Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing (2004), ACM), 604-612 · Zbl 1192.91042
[39] Werneck, R.; Setubal, J.; da Conceicao, A., Finding minimum congestion spanning trees, J. Exp. Algorithmics, 5, 11 (2000) · Zbl 1066.05050
[40] Roughgarden, T., Stackelberg scheduling strategies, SIAM J. Comput., 33, 2, 332-350 (2004) · Zbl 1080.90046
[41] Küçükaydın, H.; Aras, N.; Altınel, İ. K., A leader-follower game in competitive facility location, Comput. Oper. Res., 39, 2, 437-448 (2012) · Zbl 1251.90242
[42] Basilico, N.; Coniglio, S.; Gatti, N.; Marchesi, A., Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games, EURO J. Comput. Optim. (2019) · Zbl 1435.91045
[43] Basilico, N.; Coniglio, S.; Gatti, N., Methods for finding leader-follower equilibria with multiple followers: (extended abstract), (Proc. of AAMAS, International Foundation for Autonomous Agents and Multiagent Systems (2016)), 1363-1364
[44] Basilico, N.; Coniglio, S.; Gatti, N.; Marchesi, A., Bilevel programming approaches to the computation of optimistic and pessimistic single-leader-multi-follower equilibria, Leibniz Int. Proc. Inform., 75, 1-14 (2017) · Zbl 1436.91018
[45] Letchford, J.; Conitzer, V.; Munagala, K., Learning and approximating the optimal strategy to commit to, (International Symposium on Algorithmic Game Theory (2009), Springer), 250-262 · Zbl 1262.91006
[46] De Nittis, G.; Marchesi, A.; Gatti, N., Computing the optimal strategy to commit to in polymatrix games, (AAAI (2018)), 82-90
[47] Letchford, J.; Conitzer, V., Computing optimal strategies to commit to in extensive-form games, (EC (2010))
[48] Farina, G.; Marchesi, A.; Kroer, C.; Gatti, N.; Sandholm, T., Trembling-hand perfection in extensive-form games with commitment, (IJCAI (2018))
[49] Bošanskỳ, B.; Cermak, J., Sequence-form algorithm for computing stackelberg equilibria in extensive-form games, (AAAI (2015))
[50] Cermak, J.; Bošanskỳ, B.; Durkota, K.; Lisy, V.; Kiekintveld, C., Using correlated strategies for computing Stackelberg equilibria in extensive-form games, (AAAI (2016))
[51] Kroer, C.; Farina, G.; Sandholm, T., Robust Stackelberg equilibria in extensive-form games and extension to limited lookahead, (AAAI (2018))
[52] Marchesi, A.; Farina, G.; Kroer, C.; Gatti, N.; Sandholm, T., Quasi-perfect stackelberg equilibrium, (AAAI (2019))
[53] De Nittis, G.; Marchesi, A.; Gatti, N., Computing the strategy to commit to in polymatrix games (Extended Version), CoRR
[54] Letchford, J.; MacDermed, L.; Conitzer, V.; Parr, R.; Isbell, C. L., Computing optimal strategies to commit to in stochastic games, (AAAI (2012))
[55] Vorobeychik, Y.; Singh, S. P., Computing stackelberg equilibria in discounted stochastic games, (AAAI (2012))
[56] Xu, H.; Freeman, R.; Conitzer, V.; Dughmi, S.; Tambe, M., Signaling in bayesian stackelberg games, (Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, International Foundation for Autonomous Agents and Multiagent Systems (2016)), 150-158
[57] Fotakis, D., Stackelberg strategies for atomic congestion games, Theory Comput. Syst., 47, 1, 218-249 (2010) · Zbl 1203.91035
[58] Bonifaci, V.; Harks, T.; Schäfer, G., Stackelberg routing in arbitrary networks, Math. Oper. Res., 35, 2, 330-346 (2010) · Zbl 1232.91016
[59] Bilò, V.; Vinci, C., On stackelberg strategies in affine congestion games, (International Conference on Web and Internet Economics (2015), Springer), 132-145 · Zbl 1404.91045
[60] Luo, Z.-Q.; Pang, J.-S.; Ralph, D., Mathematical Programs with Equilibrium Constraints (1996)
[61] Sherali, H., A multiple leader stackelberg model and analysis, Oper. Res., 32, 2, 390-404 (1984) · Zbl 0581.90008
[62] DeMiguel, V.; Xu, H., A stochastic multiple-leader stackelberg model: analysis, computation, and application, Oper. Res., 57, 5, 1220-1235 (2009) · Zbl 1233.91062
[63] Shoham, Y.; Leyton-Brown, K., Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations (2008), Cambridge University Press · Zbl 1163.91006
[64] Garey, M. R.; Johnson, D. S., Computers and Intractability: a Guide to the Theory of NP-Completeness (1979), WH Freeman and Company · Zbl 0411.68039
[65] McCormick, G., Computability of global solutions to factorable nonconvex programs: part I - convex underestimating problems, Math. Program., 10, 1, 147-175 (1976) · Zbl 0349.90100
[66] Cheeseman, P.; Kanefsky, B.; Taylor, W., Where the really hard problems are, (IJCAI (1991)), 331-337 · Zbl 0747.68064
[67] Sandholm, T.; Gilpin, A.; Conitzer, V., Mixed-integer programming methods for finding nash equilibria, (AAAI (2005)), 495-501
[68] Marchesi, A.; Castiglioni, M.; Gatti, N., Leadership in congestion games: multiple user classes and non-singleton actions, (Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019 (2019)), 485-491
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.