2019/05/30 by Alberto Marchesi, Matteo Castiglioni, Marchesi, Alberto +3
Decision Sciences · Economics, Econometrics and Finance · Mathematics · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.1905.13108
openalex publication_date 2019/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of finding Stackelberg equilibria in games with a\nmassive number of players. So far, the only known game instances in which the\nproblem is solved in polynomial time are some particular congestion games.\nHowever, a complete characterization of hard and easy instances is still\nlacking. In this paper, we extend the state of the art along two main\ndirections. First, we focus on games where players' actions are made of\nmultiple resources, and we prove that the problem is NP-hard and not in\nPoly-APX unless P = NP, even in the basic case in which players are symmetric,\ntheir actions are made of only two resources, and the cost functions are\nmonotonic. Second, we focus on games with singleton actions where the players\nare partitioned into classes, depending on which actions they have available.\nIn this case, we provide a dynamic programming algorithm that finds an\nequilibrium in polynomial time, when the number of classes is fixed and the\nleader plays pure strategies. Moreover, we prove that, if we allow for leader's\nmixed strategies, then the problem becomes NP-hard even with only four classes\nand monotonic costs. Finally, for both settings, we provide mixed-integer\nlinear programming formulations, and we experimentally evaluate their\nscalability on both random game instances and worst-case instances based on our\nhardness reductions.\n