Leadership in singleton congestion games : what is hard and what is easy

We study the problem of computing Stackelberg equilibria in congestion games, focusing on the case where each player can choose a single resource (a.k.a. singleton congestion games) and one of them acts as leader. In par- ticular, we address the cases where the players either have the same action spaces (i.e., the set of resources they can choose is the same for all of them) or different ones, and where their costs are either monotonic functions of the resource congestion or not. We show that, in the case where the players have different action spaces, the cost the leader incurs in a Stackelberg equilibrium cannot be approxi- mated in polynomial time up to within any polynomial factor in the size of the game unless P = NP, independently of the cost functions being mono- tonic or not. We show that a similar result also holds when the players have nonmonotonic cost functions, even if their action spaces are the same. We also improve an algorithm for the computation of a socially optimal equi- librium in singleton congestion games with the same action spaces without leadership, and extend it to the computation of a Stackelberg equilibrium for the case where the leader is restricted to 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, which computational experiments show to scale quite well.

Viene studiato il problema di calcolare equilibri di Stackelberg nei congestion games, in particolare il caso in cui ogni giocatore pu`o scegliere una singola risorsa (singleton congestion games) e un giocatore gioca come leader. Nello specifico, vengono considerati i casi in cui i giocatori hanno o lo stesso spazio di azioni (l’insieme di risorse che possono scegliere `e lo stesso) o differenti, e in cui i costi sono o funzioni monotone della congestione delle risorse o non lo sono. Viene mostrato che, nel caso in cui i giocatori hanno spazi di azioni diversi, il costo del leader in un equilibrio di Stackelberg non pu`o essere ap- prossimato in tempo polinomiale con un fattore polinomiale nella dimensione del gioco a meno che P = NP, indipendentemente dal fatto che le funzioni di costo siano monotone o meno. Viene mostrato che un risultato simile vale anche quando i giocatori hanno funzioni di costo non-monotone, anche se gli spazi di azione sono gli stessi. Viene migliorato inoltre un algoritmo per il calcolo dell’equilibrio socialmente ottimo nei singleton congestion games con gli stessi spazi di azione e senza leadership, e viene esteso al calcolo dell’equilibrio di Stackelberg, nel caso in cui il leader sia limitato a giocare in strategie pure. Per i giochi in cui trovare un equilibrio `e difficile, viene mostrato come, nel caso ottimistico nel quale i follower favoriscono il leader in caso di pareg- gio, il problema pu`o essere formulato attraverso programmi lineari misto- interi, che gli esperimenti mostrano scalare discretamente.