Abstract
We study the problem of finding Stackelberg equilibria in games with a massive number of players.
So far, the only known game instances in which
the problem is solved in polynomial time are some
particular congestion games. However, a complete
characterization of hard and easy instances is still
lacking. In this paper, we extend the state of the
art along two main directions. First, we focus on
games where players’ actions are made of multiple
resources, and we prove that the problem is NPhard and not in Poly-APX unless P = NP, even
in the basic case in which players are symmetric,
their actions are made of only two resources, and
the cost functions are monotonic. Second, we focus
on games with singleton actions where the players
are partitioned into classes, depending on which actions they have available. In this case, we provide a
dynamic programming algorithm that finds an equilibrium in polynomial time, when the number of
classes is fixed and the leader plays pure strategies.
Moreover, we prove that, if we allow for leader’s
mixed strategies, then the problem becomes NPhard even with only four classes and monotonic
costs. Finally, for both settings, we provide mixedinteger linear programming formulations, and we
experimentally evaluate their scalability on both
random game instances and worst-case instances
based on our hardness reductions