On Singleton Congestion Games with Resilience Against Collusion
This work addresses stability issues in resource allocation for agents, but it is incremental as it focuses on a specific subclass of congestion games.
The paper tackles the problem of ensuring equilibrium outcomes in singleton congestion games that are resilient to weakly improving deviations by various coalitions, and proves the existence of such equilibria, which is the strongest guarantee in the literature for this subclass of games.
We study the subclass of singleton congestion games with identical and increasing cost functions, i.e., each agent tries to utilize from the least crowded resource in her accessible subset of resources. Our main contribution is a novel approach for proving the existence of equilibrium outcomes that are resilient to weakly improving deviations: $(i)$ by singletons (Nash equilibria), $(ii)$ by the grand coalition (Pareto efficiency), and $(iii)$ by coalitions with respect to an a priori given partition coalition structure (partition equilibria). To the best of our knowledge, this is the strongest existence guarantee in the literature of congestion games that is resilient to weakly improving deviations by coalitions.