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

1 Introduction

Congestion games provide a natural and fundamental framework for modeling autonomous agents that compete for shared resources. In classical congestion games (as introduced by Rosenthal [Rosenthal, 1973a]) we are given a set of resources and the strategy of each player is to select a subset of them. The total cost of each player is the sum of the costs of the chosen resources, where the cost of a resource depends on the number of players using it.

In this paper we consider integer Splittable Congestion Games with Capacitated resources and player-Specific costs (SCGCS), in which we are given a set of n players with a weight wi associated to each player i, and a set of resources with, associated to each resource, a capacity limiting the number of players who can use it. Given any player, a possible strategy consists in distributing her weight among the resources, and an outcome of the game is given by a strategy selection for every player. Given any resource r with capacity Cr, its congestion in an outcome is given by summing up all players' weights contributions to that resource and its capacity constraint is implemented by means of the latency function of r being defined as ∞ when the congestion on r is greater than Cr. We assume that players' weights are integers and have to be allocated in integer parts among the resources.

Moreover, we consider simple latency functions being constant (when the congestion is not greater than the resource capacity) and player-specific, which means that player i pays a fixed constant cost cir for each unit of weight she requests from resource r. In an outcome of the game, a player i pays a total cost which is the sum of the costs of the selected resources in her strategy, where the cost for a selected resource r is proportional to the portion of the weight wi that i requests to r1 . We also consider the setting where, in an outcome of the game, a player i pays a per-unit cost which is defined as the total cost of i divided by her weight wi. The per-unit cost represents the average cost that a player pays for every unit of her weight.

We adopt pure Nash equilibria, i.e., strategy profiles where no player can decrease her cost by unilaterally changing her strategy, as stable outcomes for SCGCS.

Splittable congestion games, congestion games with capacitated resources and congestion games with player-specific costs have been widely studied (see Subsection 1.2); however, based on our knowledge, there is no work studying all these three features (i.e., splittable, capacitated and player-specific) together, as this paper does. We initiate the study of SCGCS by considering a basic setting in which the latency functions are constant and players are symmetric (i.e., all players have the same set of strategies).

Our setting is motivated by the following practical allocation scenarios. For instance, consider an energy supply scenario where autonomous energy consumers (players) strategically interact to request discrete energy units from an energy provider. Specifically, we have a set of n players who simultaneously require energy, e.g., electricity, units from an energy provider, within a certain time period, e.g., a day, divided into R time slots, e.g. hours (corresponding to the resources of our game); within the time period, every player i has a demand of wi energy units. The strategy of each player is to decide, for each time slot r ∈ R, the number of energy units to require from the provider such that the overall number of energy units required in the whole period by player i is equal to wi. For each time slot r ∈ R, the provider will supply the players with the required energy units only if such requirements in total do not exceed a value Cr which represents the maximum number of energy units that the provider can supply for the time slot r, while it will go into blackout otherwise and no player get energy units in time slot r. In a strategy profile (e.g. outcome), each player pays a total cost for the energy that she received, which may vary on time slots. Players may have different costs per unit energy for the same time slot, because the provider may tailor its offers to different players. If in a time slot r the provider goes into black-out, all the players requiring at least one unit of energy from r will experience a cost of infinite because they are not satisfying their demand.

1 If player i requires sir units to resource r, then i pays sir · cir for the resource r.

Task allocation in cloud computing is another possible scenario of application. Consider a set of companies (players) that want to run computational tasks on a set R of cloud servers (resources). Each company has a total amount wi of computational work (measured in integer units) to distribute among servers and each server r has a limited processing capacity Cr that represents the total number of work units it can handle. Each cloud server r ∈ R supplies the players with the required work units if and only if the total demand does not exceed its capacity Cr, given that it cannot decide which companies should or should not be accommodated, for instance for fairness reasons. In an outcome, each player pays a total cost for the work units that she received, which may vary on cloud servers. Moreover, players may have different costs per unit for the same cloud server because it may offer different commercial plans.

Other practical application scenarios include the following: truck-load allocation across warehouses, where several shipping companies need to store or process goods at a set of regional facilities; electric vehicle charging networks, where multiple fleet operators must decide where to charge their vehicles among a set of charging stations; and a well-studied case in congestion games, namely network congestion games on parallel capacitated links where multiple players, each with a quantity of flow and with the same source and destination, have to decide how many of their units of flow to route on each link.

1.1 Our Contribution

We first focus, in Section 3, on the computational complexity of computing optimal outcomes minimizing the utilitarian social welfare function, which is defined as the sum of the players' costs, by showing that this problem is solvable in polynomial time.

In Section 4, we study the complexity of and convergence to Nash equilibria. After observing that in SCGCS Nash dynamics are convergent (and therefore Nash equilibria always exist), we provide tight bounds on the convergence time of best response dynamics. We also show that computing a best response for a player, as well as computing a Nash equilibrium that minimizes the utilitarian social welfare, are polynomial-time solvable problems.

In Section 5, we study the performances of Nash equilibria by resorting to the two standard notions of price of anarchy and price of stability, that quantify the multiplicative social welfare loss of the worst and the best Nash equilibria with respect to the social optimum, respectively. In particular, we provide tight bounds for all considered cases.

All above mentioned results of Sections 3, 4 and 5 hold for both total and per-unit players' costs.

1.2 RelatedWork

Congestion games have been introduced by Rosenthal [Rosenthal, 1973a] and then extensively studied. The existence of (pure) Nash equilibria [Nash, 1950] for (unweighted) congestion games is proved by means of an exact potential function [Monderer and Shapley, 1996; Rosenthal, 1973a], and it also holds that each game admitting an exact potential function is isomorphic to a congestion game. These games are also well studied in strategic settings such as routing [Roughgarden and Tardos, 2002], network design [Anshelevich et al., 2008] and load balancing [Even-Dar et al., 2007]. The complexity of computing (pure) Nash equilibria has been widely studied [Ackermann et al., 2008; Fabrikant et al., 2004] as well as the performance of Nash equilibria in terms of the price of anarchy [Koutsoupias and Papadimitriou, 1999] and the price of stability [Anshelevich et al., 2008].

Weighted congestion games, where players have weights and the total congestion on a resource is given by the sum of the weights of players using it 2 , generalizes congestion games and are not potential games anymore. These games admit Nash equilibria only under specific conditions [Fotakis et al., 2009; Fotakis et al., 2005; Milchtaich, 1996].

Splittable congestion games are a variant of congestion games where each player is associated with a positive weight and her strategy is a possibly fractional distribution of her weight over the resources. These games are not potential games and most of the work of the literature focuses on the existence and computation of Nash equilibria [Bhaskar and Lolakapuri, 2018; Dunkel and Schulz, 2008; Harks and Timmermans, 2018; Harks and Timmermans, 2022]. The performance of Nash equilibria in terms of the price of anarchy is studied in [Roughgarden and Schoppmann, 2015]. A special case, which is related to our setting, are integer-splittable congestion games where the players' weights are integers which have to be allocated in integer parts among the resources. Again, these games are not potential games and most work focus on the existence and computation of Nash equilibria [Dunkel and Schulz, 2008; Rosenthal, 1973b; Tran-Thanh et al., 2011].

Congestion games with capacitated resources is another studied generalization of congestion games where each resource has capacity limiting the total assigned weight, i.e., its congestion. Different versions of congestion games with capacitated resources have been considered in the literature. The one most related to our setting is considered in [Feldman and Ron, 2015], where the authors study capacitated symmetric network design games. Specifically, given a graph, each player wishes to construct a path from a source to a sink and the cost of each edge is shared equally among the players using it; however, if the congestion of an edge is greater than its capacity, then any player using that edge experiences an infinite cost. In [Feldman and Ron, 2015], the authors study existence of and convergence to Nash equilibria as well as performance of Nash equilibria in terms of the price of anarchy and the price of stability. Further results on Nash equilibria are presented in [Hanaka et al., 2022; Erlebach and Radoja, 2015], while in [Feldman and Geri, 2016] the authors deals with existence and performance of strong Nash equilibria. A different version of congestion games with capacitated resources, which are less related to our setting, is studied in [Gourv`es et al., 2015], where it is assumed that each resource has a capacity and is associated with an order of the players using it; any player that in the order has a position greater than the capacity experiences an infinite cost. A further different model of congestion games with capacitated resources is studied in [Drees et al., 2019].

2 In congestion games all players have the same weight of one.

Congestion Games with player-specific payoff functions (denoted successively also as player-specific latency functions or player-specific costs), namely, with latency functions which are specific to the particular player, were introduced in [Milchtaich, 1996] with a focus on the existence of pure Nash equilibria. Subsequent work [Ackermann and Skopalik, 2008; Gairing and Klimm, 2013; Gairing et al., 2011] characterizes the existence of, complexity, convergence to and performance of pure Nash equilibria for specific latency functions and settings. The work [Mavronicolas et al., 2007] is one of the most closely related to ours: it considers congestion games with player-specific costs, where the cost that a player associates to each resource is given by the product of a (non-decreasing) delay function and a player-specific constant; in [Mavronicolas et al., 2007], existence, complexity, and convergence to pure Nash equilibria in both general and network congestion games are studied. Finally, the complexity of computing Nash equilibria has been also studied for splittable congestion games with player-specific latency functions [Klimm and Warode, 2020].

To the best of our knowledge, we are the first to study integer splittable congestion games with capacitated resources and player-specific costs.

2 Model

Given a positive integer n, we denote by [n] the set {1, . . . , n}. An integer Splittable Congestion Games with Capacitated resources and player-Specific costs (SCGCS) is a tuple G = ([n], [R], (wi)i∈[n], (Cr)r∈[R], (cir )i∈[n],r∈[R]): there is a set [n] of players who simultaneously have to split in integer parts their integer weight, representing the number of required workload units, among R resources. In particular, every player i has a weight of wi workload units, every resource r ∈ [R] has an integer capacity Cr and every player i has to decide, for each resource r, the number of units, say sir , to require from r. We assume

A strategy for player i is a R-dimensional vector si = (si1 , . . . , siR) of non-negative integers, such that ∑r∈[R] sir = wi; we denote by Si the strategy space of player i. A strategy profile or outcome σ = (s1 , . . . , sn ) is a n-dimensional vector of strategies, one for each player; we denote by Σ = ×i∈NSi the set of all possible strategy profiles of the game.

The congestion xr(σ) of resource r in outcome σ is defined as xr(σ) = ∑i∈[n] sir . The player-specific latency function ℓir (σ) of resource r for player i in outcome σ is such that the latency incurred by player i using r is equal to ∞ when xr(σ) > Cr, and is equal to a player specific cost cir otherwise. More formally,

For every r ∈ [R], when xr(σ) > Cr, we say that resource r is overfull in σ and we denote by ar(σ) the residual capacity of r in σ, i.e., ar(σ) = max{0,Cr - xr(σ)}. Moreover, let wmax = maxi∈[n] wi be the maximum weight among all players. When the costs cir are such that, for every r ∈ [R], it holds that cir = cjr for any i, j ∈ [n], i.e., the latencies are not player-specific, we say that the game is simple.

The total cost cost TOTAL i (σ) of player i in strategy profile σ, is

The per-unit cost cost PER-UNIT i (σ) in strategy profile σ is defined as the total cost divided by the weight of player i:

In the following, in order to deal both with the total cost and the per-unit cost, we denote by Z any element in set {TOTAL, PER-UNIT}.

Nash equilibrium. Given a strategy profile σ = (s1 , . . . , sn ), a player i ∈ [n] and a strategy s ∈ Si, (σ-i , s) denotes the strategy profile obtained from σ when player i changes her strategy from si to s.

An improving deviation (or shortly a move) for i in σ is any strategy s ∈ Si such that cost Zi (σ-i , s) < cost Zi (σ), that is, player i improves (decreases) her cost by changing her strategic choice to s. A best-response (also a best-move) for i in σ is any strategy in the set argmins∈Si cost Zi (σ-i , s).

A dynamics τ starting at a strategy profile σ0 and ending at a strategy profile σh is a sequence τ = ⟨σ0 , σ1 , . . . , σh ⟩ of h + 1 ≥ 1 outcomes such that, if h ≥ 1, for every r ∈ {0, 1, . . . , h - 1}, σr+1 is the outcome resulting from an improving deviation, from σr , for some player. The length of τ is defined as h ≥ 0. A dynamics τ = ⟨σ0 , σ1 , . . . , σh ⟩ is cyclic if there exist t, t′ ∈ {0, 1, . . . , h} with t ̸= t′ such that σt = σt′ . We say that a game G is convergent if there exist no cyclic dynamics for G. A best response dynamics is a dynamics in which all improving deviations are best responses.

A pure Nash equilibrium (NE, for short) is a strategy profile σ such that cost Zi (σ) ≤ cost Zi (σ-i , s) for every i ∈ [n] and s ∈ Si. In other words, no player possesses an improving deviation or, equivalently, every player is playing a best-response. We denote by NE(G) the set of NE of G. It is worth noticing that, by the definition of cost PER-UNIT , Nash deviations, dynamics and Nash equilibria do not change when considering total costs and per-unit costs, i.e., they are independent of Z. Moreover, convergence implies the existence of a Nash stable outcome.

SocialWelfare Function. We consider the utilitarian social welfare function, defined as the sum over all the players of the player costs. More formally, given any σ ∈ Σ, the social welfare is defined as

We denote by σ∗Z a social optimum, that is, a strategy profile minimizing the social welfare function SW Z .

Efficiency measures. We adopt the two standard notions of price of anarchy and price of stability, quantifying the multiplicative social welfare loss of the worst and the best Nash equilibria with respect to the social optimum, respectively. Formally, the price of anarchy of G is defined as PoAZ (G) = maxσ∈NE(G) SW Z (σ) SW Z (σ∗Z ) and the price of stability SW Z (σ)

We now introduce a definition that will be useful later in order to consider feasible solutions "up to equivalence": Two outcomes σ, ¯σ ∈ Σ of game G are equivalent if cost Zi (σ) = cost Zi (¯σ) for every i ∈ [n] and Z ∈ {TOTAL, PER-UNIT}.

3 Computation and Complexity of Optimal Solutions

In this section we deal with the problem of computing an outcome (i.e., a strategy profile) minimizing the utilitarian social welfare for a given SCGCS.

We start with a useful observation.

Observation 1. Studying per-unit costs makes sense only for simple games, because, when the costs cir are player specific, it holds that, for every i ∈ [n], the denominator wi of the perunit cost function can be included in costs cir , for any r ∈ [R].

In the following theoremwe show that it is possible to compute in polynomial time an outcome minimizing the utilitarian social welfare.

Theorem 1. For Z ∈ {TOTAL, PER-UNIT}, given any SCGCS G, it is possible to compute in polynomial time the strategy profile minimizing SW Z .

Proof sketch. By Observation 1, it is sufficient to solve the problem of minimizing SW TOTAL .

The problem of computing the strategy profile minimizing SW TOTAL can be formulated as a integer linear program as follows:

Notice that this formulation fits the setting of the "Hitchcock- transportation problem". Well-known results show that the "Hitchcock-transportation problem" can be solved in polynomial time [Papadimitriou and Steiglitz, 1998].

4 Computation and Complexity of Nash Equilibria

In this section we deal with the problem of computing Nash stable solutions and studying the convergence of Nash dynamics to them.

4.1 Computation of Nash equilibria

We first provide a preliminary result showing that it is possible to compute in polynomial time a best response.

Lemma 1. Given any SCGCS G, any strategy profile σ for G and any player i, the problem of computing a best response for player i in σ is polynomial-time solvable.

Proof. Consider Algorithm 1, in which we assume without loss of generality that resources are numbered such that ci1 ≤ ci2 ≤ . . . ≤ ciR.

In the while loop of line 3, player i moves all her workload units from resources that are overfull. Notice that this is always possible since we assume that ∑i∈[n] wi ≤ ∑r∈[R] Cr. In particular, at each iteration of the while loop of line 3, player i moves some units from one overfull resource to one of the cheapest non-overfull resource (resource α). Since the number of workload units moved at an iteration is min{aα(σ), δ}, it follows that either α increases or the number of overfull resources that player i is using decreases after the shift, thus implying that the number of iterations of the while loop of line 3 is at most R. Notice that when the execution of Algorithm 1 reaches line 11, player i is not using any overfull resource. At each iteration of the while loop of line 12, player i moves some units from one of the most expensive resource she is using (resource ω) to one of the cheapest resource with positive residual capacity (resource α). Since the number of workload units moved at an iteration is min{aα(σ), siω }, it follows that either α increases or ω decreases after the shift, thus implying that the number of iterations of the while loop is at most R. Finally, when ciα ≥ ciω , it means that there is no available resource with cost smaller than the cost that i is paying for her most costly used resource, thus implying that i is playing a best response in σ.

We now focus on the computation of Nash equilibria minimizing the considered social welfare functions. We first provide a useful observation which essentially says that when a player performs a best response no other player worsens her cost.

Observation 2. For Z ∈ {TOTAL, PER-UNIT}, given a strategy profile σ, assume that there exists a player i ∈ [n] possessing an improving deviation s ∈ Si leading to the new strategy profile σ′ = (σ-i , s). It holds that cost Zi (σ′ ) < cost Zi (σ), and for any player j ∈ [n], it holds that cost Zj (σ′ ) ≤ cost Zj (σ).

Indeed, when a player performs an improving deviation, she does not make overfull any non-overfull resource, and a player can worsen (i.e., increase) her cost only if a nonoverfull resource becomes overfull.

For the utilitarian social welfare function, it can be easily shown that any optimal solution is also a Nash equilibrium.

Algorithm 1 Best response computation

Require: SCGCS G, outcome σ, player i Ensure: a strategy profile resulting from a best response of i

starting from σ = (s1 , . . . , sn ) 1: Assume w.l.o.g. that ci1 ≤ ci2 ≤ . . . ≤ ciR 2: α←min{r ∈ [R] : ar(σ) > 0} 3: while there exists r ∈ R : sir > 0 ∧ xr(σ) > Cr do 4: s′ ← si 5: δ ←min{Cr -xr(σ), sir } 6: s′α ← siα +min{aα(σ), δ} 7: s′r ← sir -min{aα(σ), δ} 8: σ ← (σ-i , s′ ) 9: α←min{r ∈ [R] : ar(σ) > 0} 10: end while 11: ω ←max{r ∈ [R] : sir > 0} 12: while ciα < ciω do 13: s′ ← si 14: s′α ← siα +min{aα(σ), siω } 15: s′ω ← siω -min{aα(σ), siω } 16: σ ← (σ-i , s′ ) 17: α←min{r ∈ [R] : ar(σ) > 0} 18: ω ←max{r ∈ [R] : sir > 0} 19: end while 20: return σ

Indeed, by Observation 2, we get that a best response cannot worsen the cost paid by other players: if a Nash deviation existed from the optimal solution, its social welfare would decrease: a contradiction. Thus, the following corollary is an immediate consequence of Theorem 1.

Corollary 1. For Z ∈ {TOTAL, PER-UNIT}, given any SCGCS G, it is possible to compute in polynomial time a Nash equilibrium minimizing SW Z .

4.2 Nash dynamics

We now focus on the study of best response dynamics for general games and provide an almost tight analysis on the number of best responses needed to reach a Nash equilibrium starting from a generic strategy profile.

Theorem 2. Given any SCGCS G, every best response dynamics has length at most n + (R - 1) · ∑i∈N wi.

Proof. By Observation 2, we know that a move of a player cannot increase the cost of another player. Therefore, it directly follows that every dynamics is convergent (because every player can decrease her cost only a finite number of times).

In order to prove that every best response dynamics has length at most n + (R - 1) · ∑i∈N wi, first of all notice that no best response can use an overfull resource. For any player i ∈ [n], it holds that only the first best response of i in a best response dynamics can start from a strategy profile σ in which player i is using an overfull resource, and therefore there are in total at most n best responses of a player experiencing an infinite cost. Moreover, as a result of a best response by player i starting from a state in which i is experiencing a finite cost, no workload unit increases its cost, while some workload units do not change their costs (these units do not change their resource), and some workload units decrease their costs (by moving to a cheaper resource). Hence, for every i ∈ [n], player i can perform a number of best response that is at most wi · (R- 1), because every unit can move at most R - 1 times. The claim follows.

The following proposition shows that the bound analysis presented in Theorem 2 is almost tight.

Proposition 1. Given any n ≥ 2 and any (wi)i∈[n], there exists a SCGCS G with n players having weights w1, . . . , wn for which a best response dynamics has length (R - 1) · ∑i∈[n] wi.

Proof. We show an instance G of SCGCS for which there exists a best response dynamics starting from a specific strategy profile that needs (R- 1) · ∑i∈[n] wi best responses to reach a Nash equilibrium. Let G be a game with n players. For the sake of readability, in this proof we assume that the n players are numbered from 0 to n - 1 and are such that w0 = w1 = · · · = wn-1 = k, for some fixed positive integer k > 0. There are R = n resources, also numbered from 0 to n - 1, such that C0 = k + 1, and for any r = 1, · · · , n - 1, it holds that Cr = k. Finally, for any i, r = 0, · · · , n - 1, cir = 1 + (r - i) mod n. Moreover, we assume that numbers identifying players and resources are always modulo n.

Let us consider a best response dynamics starting from the initial strategy profile σ where each player i is requiring all the needed wi = k workload units from resource i - 1, i.e., for any i = 0, · · · , n - 1, the strategy profile of player i is such that sii-1 = k, and for any other resource r ̸= i - 1, sir = 0. Notice that in σ only resource 0 has one available unit of residual capacity, while resources 1, · · · , n - 1 have no unit available.

The key point is that the sum of the capacities of all resources is one plus the sum of weights of all players. It follows that, in a state without overfull resources, the unique improving move (and thus also the best one) for a player can only consist in moving one unit of workload to the unique non-overfull resource.

Let us consider a dynamics composed by R-1 consecutive rounds. For γ ∈ [n-1], round γ is composed by k sequences of best responses, each of which consists of the following n best responses: for j ∈ [n], the j-th best response is performed by player γ + j, that moves one workload unit from resource j to resource j - 1.

For instance, when γ = 1, in each of the k sequences, we have the following best responses: first, player 2 moves one workload unit from resource 1 to resource 0, then player 3 moves one workload unit from resource 2 to resource 1 and so on until player 1 moves one workload unit from resource 0 to resource n - 1.

We conclude that there exists a best response dynamics composed of (R - 1) · k · n = (R - 1) · ∑i∈[n] wi best responses and finally reaching a Nash equilibrium.

Finally, it is worth noticing that, as shown in Lemma 2, in simple games it holds that best response dynamics converge in a number of best responses that is linear in the number of players.

Lemma 2. For Z ∈ {TOTAL, PER-UNIT}, given any strategy profile σ of SCGCS G, there exists a strategy profile ¯σ ∈ NE(G) such that SW ¯σ ≤ SWσ . If G is simple, ¯σ can be computed in polynomial time by performing a best response dynamics starting from outcome σ.

Proof. If σ ∈ NE(G), the claim clearly holds (σ = ¯σ). Assume that in σ there exists a player i ∈ [n] possessing a best response s ∈ Si, i.e., σ is not a Nash equilibrium. From Observation 2, we know that at each step of the best response dynamics the utilitarian social welfare strictly decrease. This implies that the best response dynamics is convergent and thus that, after a finite number of steps, it reaches a Nash equilibrium ¯σ ∈ NE(G) such that SW ¯σ < SWσ .

We now show that, if G is simple, the best response dynamics converges to a Nash equilibrium after a linear (with respect to the number of players) number of steps. Specifically, we argue that each player performs at most one best response. Suppose that a player i performs a best response leading the game from some strategy profile σ′ to σ′′ . From Lemma 1 we know that: (i) computing a best response is polynomial-time solvable, (ii) player i after performing a best move is not using any overfull resource. Let cimax (σ′′ ) = maxr∈[r]:sir >0 cir be the highest cost of a resource from which player i gets at least one workload unit in σ′′ . We have that, for any resource r ∈ [R] such that ar(σ′′ ) > 0, it holds that cir ≥ cimax (σ′′ ), because otherwise player i could still improve her cost by requiring a workload unit from resource r: a contradiction to the fact that player i has performed a best response. Moreover, in any strategy profile of the dynamics starting from strategy profile σ′′ , no player will reduce the number of workload units that requires from a resource with cost smaller than cimax (σ′′ ) since, in this case, she must use a resource with cost higher or equal than cimax (σ′′ ). This means that in any strategy profile ¯σ of the best move dynamics starting from strategy profile σ′′ there will be no resource r such that cr < cimax (σ′′ ) ∧ ar(¯σ) > 0. It implies that each player performs at most one best move and the claim follows.

5 Efficiency of Nash Equilibria

In this section, we focus on the efficiency of Nash equilibria. Given that, as a direct consequence of Lemma 2 (by choosing, for Z ∈ {TOTAL, PER-UNIT}, σ = σ∗Z ), the price of stability is 1, in the following we focus on the price of anarchy.

In order to provide fine grained bounds on the price of anarchy, we define the diversity parameter β = maxr∈R maxi,j∈[n] cir cjr as the maximum ratio between the costs that two players have for the same resource (β = ∞ if there exists a resource with cost equal to 0 for a player and a non-zero cost for another player). Notice that in simple games we have β = 1.

The following observations will be exploited in many proofs of this section.

Observation 3. It is worth noticing that, for both total and per-unit costs, in any optimal solution σ∗ and in any Nash equilibrium σ, we are guaranteed that no player i ∈ [n] is paying an infinite cost. In fact, by the assumption that ∑i∈[n] wi ≤ ∑r∈[R] Cr, we know that (i) there exists an outcome with a finite cost and (ii) when there is an overfull resource r, there always exists a player with an improving deviation available.

Moreover, in order to reason about the price of anarchy, it is convenient to consider a modified single-capacitated version of a SCGCS, in which every resource r has a capacity Cr = 1.

Observation 4. Considering single-capacitated games is without loss of generality, because given any SCGCS G = ([n], [R], (Cr)r∈[R], (cir )i∈[n],r∈[R]) it is possible to obtain an equivalent single-capacitated SCGCS G ′ = ([n′ ], [R′ ], (M ′r = 1)r∈[R′ ], (c′i r )i∈[n],r∈[R′ ]) in which n′ = n, R′ = ∑r∈R Cr and, for every r ∈ R, we add to G ′ Cr resources (belonging to set R′r with |R′r | = Cr) with the same per-unit costs of resource r, i.e., c′i r′ = cir for any r′ ∈ R′r and for any i ∈ [n]. Consequently, it is possible to map every strategy profile of G in an corresponding strategy profile of G ′ with the same player costs. Therefore, although this transformation is not polynomial (and cannot be used for providing positive complexity results), it preserves player costs and stability, and, in particular, it holds that PoAZ (G) = PoAZ (G ′ ), for Z ∈ {TOTAL, PER-UNIT}.

A tight bound equal to the diversity parameter β and to wmax · β can be proved for the price of anarchy in the cases of total costs and per-unit costs, respectively. When β = ∞, a tight bound depending on β means that the price of anarchy is unbounded.

Theorem 3. Given any SCGCS G with diversity parameter β, PoA TOTAL (G) ≤ β and PoA PER-UNIT (G) ≤ β · wmax.

Proof. By Observation 4, we assume without loss of generality that G is single-capacitated. Notice that, in a singlecapacitated game, the optimal and Nash stable strategy profiles are such that sir ∈ {0, 1} for any i ∈ [n] and any r ∈ [R]. We can therefore assume that a strategy for player i is denoted by the set Si of resources for which sir = 1. We also denote by f(r, σ) the player using resource r in outcome σ, with f(r, σ) = 0 if no player is using resource r in σ.

We first prove that PoA TOTAL (G) ≤ β. Consider an optimal outcome σ∗ = σ∗ TOTAL for G and any Nash equilibrium σ for G.

Let X∗ = ⋃i∈[n] S∗i be the subset of resources used in σ∗ and X = ⋃i∈[n] Si be the subset of resources used in σ. We partition the set X in three subsets A, B and C such that:

• A = ⋃i∈[n] (Si ∩S∗i ) is the set of resources that are used by the same player both in σ and σ∗ ;
• B = (X∗ ∩X) \ A is the set of resources that are used both in σ and σ∗ by different players;
• C = X\X∗ is the set of resources that are used in σ but are not used in σ∗ .

Analogously, we partition the set X∗ in three subsets A∗ , B∗ and C ∗ such that:

• A∗ = A is the set of resources that are used by the same player both in σ and σ∗ ;
• B∗ = B is the set of resources that are used both in σ and σ∗ by different players;
• C ∗ = X∗ \ X is the set of resources that are used in σ∗ but are not used in σ.

When D and E are two equal cardinality sets, by the notation ∑i∈D,j∈E h(i, j) we mean that we are summing |D| = |E| terms, and each term h(i, j) is obtained for i getting (in any order) values from set D and j getting (again in any order) values from set E.

By Observation 3, since σ = (s1 , . . . , sn ) is a Nash equilibrium, we are guaranteed that no player i ∈ [n] is paying in σ an infinite cost. We have

where equality (1) holds because A = A∗ , all resource in A∗ are used by the same players both in σ and σ∗ and B = B∗ , inequality (2) holds by definition of the diversity parameter β, inequality (3) holds because σ is a Nash equilibrium and, fixed any r ∈ C, for any resource r′ ∈ C ∗ , since r′ is not used in σ, player f(r, σ) has no incentive to use r′ instead of r; finally, inequality (4) holds by definition of the diversity parameter β.

In order to prove that PoA PER-UNIT (G) ≤ β · wmax, it is possible to exploit the same arguments as above, with the following modification:

where inequality (6) holds by the same arguments exploited in the case of total costs, and inequality (7) holds because SW PER-UNIT (σ∗ ) ≥ ∑r∈X∗ cf(r,σ∗ ) r wf(r,σ∗) ≥ ∑r∈X∗ cf(r,σ∗ ) rwmax .

The following propositions show that the upper bounds to the price of anarchy provided in Theorem 3 are indeed tight.

Proposition 2. Given any β ≥ 1, there exists a SCGCS G with diversity parameter β such that PoA TOTAL (G) ≥ β.

Proposition 3. Given any β ≥ 1, there exists a SCGCS G with diversity parameter β such that PoA PER-UNIT (G) ≥ β · wmax.

6 Conclusions, Extensions and FutureWork

In this paper we have considered SCGCS, that, to the best of our knowledge, have not been studied before. Motivated by practical allocation scenarios, we initiated this study by considering a basic setting in which the latency functions are constant and players are symmetric.

We believe that there are several open interesting research directions connected to our work. Besides closing the gaps of our non-tight bounds, it would be important to consider more general settings such as asymmetric players and/or more general latency functions (for instance, polynomial latency functions), that could model practical scenarios in a more accurate way and possibly lead to a lower price of anarchy.

Moreover, while we have considered Nash equilibria, it would be nice to study also other notions of stable solutions such as strong Nash equilibria or other solutions being able to capture some form of fairness or efficiency such as the Pareto efficiency. Concerning the fairness, instead of adopting the utilitarian social welfare function (that may be extremely harsh for some agents), the egalitarian social welfare function (whose objective is that of minimizing the maximum cost among the players) could be considered. Moreover, a remarkable generalization of our model consists in considering the case in which agents have to distribute their weights among resources such that, for each i ∈ [n] and for each r ∈ [R], smin(i, r) ≤ sir ≤ smax(i, r) where smin(i, r) and smax(i, r) are integer given values: this additional assumption may be worth investigating in practical scenarios where introducing bounds on resource usage is necessary to guarantee a form of fairness among agents, i.e., to avoid situations in which one or a few agents monopolize inexpensive resources.

Another possible modification of our model is to relax the integer-splittable assumption. In this case, some of our results would still hold: an optimal solution could still be computed in polynomial time, and the price of stability would remain equal to 1. However, the results concerning convergence time and the price of anarchy would no longer carry over to this setting and require further investigation.

Finally, future work could include an experimental evaluation to better understand the convergence behavior of the dynamics and the practical performance of stable solutions.

Acknowledgments

All authors acknowledge support from the PNRR MIUR project FAIR - Future AI Research (PE00000013), Spoke 9 - Green-aware AI, WP 9.2 "Interactions of green-aware agents", cascade sub-project "Existence, Complexity and Efficiency of Stable Solutions in Green-Oriented Games" - ECOGAMES, CUP D23C24000210006.

Gianpiero Monaco and Luca Moscardelli acknowledge support from the GNCS group of INdAM.

Raffaele Mosca would like to witness that he just tries to pray a lot and is not able to do anything without that - ad laudem Domini.