Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Leadership in Congestion Games: Multiple User Classes and Non-Singleton
  Actions (Extended Version)   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 NP-hard 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 NP-hard even with only four classes
and monotonic costs. Finally, for both settings, we provide mixed-integer
linear programming formulations, and we experimentally evaluate their
scalability on both random game instances and worst-case instances based on our
hardness reductions.

16
The categories of this paper are: stat
27
The categories of this paper are: comp-gas
24
The categories of this paper are: dg-ga
4
The categories of this paper are: cond-mat
7
The categories of this paper are: hep-th
31
The categories of this paper are: ao-sci
0
The categories of this paper are: hep-ph
11
The categories of this paper are: hep-lat
19
The categories of this paper are: eess
5
The categories of this paper are: gr-qc
15
The categories of this paper are: nucl-ex
9
The categories of this paper are: nlin
22
The categories of this paper are: chao-dyn
25
The categories of this paper are: patt-sol
36
The categories of this paper are: cmp-lg
23
The categories of this paper are: solv-int