Integer Splittable Congestion Games with Capacitated Resources and Player-Specific Costs

Integer Splittable Congestion Games with Capacitated Resources and Player-Specific Costs

Gianpiero Monaco, Raffaele Mosca, Luca Moscardelli

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence
Main Track. Pages 279-287. https://doi.org/10.24963/ijcai.2026/32

Motivated by practical allocation problems, we study integer splittable congestion games with capacitated resources and player-specific costs. In this setting, each player has an integer weight that has to be split in integer units across multiple resources, each with a capacity limiting the total assigned weight, i.e., its congestion. The latency of a resource is equal to a player-specific constant when its congestion is not greater than the capacity and becomes prohibitive, i.e., equal to ∞, once the capacity is exceeded. We analyze the computational complexity of finding an allocation that optimizes utilitarian social welfare under two cost models (total cost and per-unit cost). Furthermore, we investigate the computation of, speed of convergence to, and efficiency of Nash equilibria.
Keywords:
Agent-based and Multi-agent Systems: Agent theories and models
Game Theory and Economic Paradigms: Noncooperative games