On the Existence of Pure Strategy Nash Equilibria in Integer–Splittable Weighted Congestion Games

Abstract. We study the existence of pure strategy Nash equilibria (PSNE) in integer–splittable weighted conges-tion games (ISWCGs), where agents can strategically assign different amounts of demand to different resources, but must distribute this demand in fixed-size parts. Such scenarios arise in a wide range of application domains, including job scheduling and network routing, where agents have to allocate multiple tasks and can assign a num-ber of tasks to a particular selected resource. Specifically, in an ISWCG, an agent has a certain total demand (aka weight) that it needs to satisfy, and can do so by requesting one or more integer units of each resource from an element of a given collection of feasible subsets.1 Each resource is associated with a unit–cost function of its level of congestion; as such, the cost to an agent for using a particular resource is the product of the resource unit–cost and the number of units the agent requests. While general ISWCGs do not admit PSNE (Rosenthal, 1973b), the restricted subclass of these games with linear unit–cost functions has been shown to possess a potential function (Meyers, 2006), and hence, PSNE. However, the linearity of costs may not be necessary for the existence of equilibria in pure strategies. Thus, in this paper we prove that PSNE always exist for a larger class of convex and monotonically increasing unit–costs. On the other hand, our result is accompanied by a limiting asumption on the structure of agents ’ strategy sets: specifically, each agent is associated with its set of accessible resources, and can distribute its demand across any subset of these resources