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

摘要

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.