In this work, we consider the problem of improving the eficiency of utility-sharing games, by resorting to a limited amount of subsidies. Utility-sharing games model scenarios in which strategic and selfinterested players interact with each other by selecting resources. Each resource produces a utility that depends on the number of players selecting it, and each of these players receives an equal share of this utility. As the players' selfish behavior may lead to pure Nash equilibria whose total utility is suboptimal, previous work has resorted to subsidies, incentivizing the use of some resources, to contrast this phenomenon. In this work, we focus on the case in which the budget used to provide subsidies is bounded. We consider a class of mechanisms, called -subsidy mechanisms, that allocate the budget in such a way that each player's payof is re-scaled up to a factor ≥ 1. We design a specific sub-class of -subsidy mechanisms, that can be implemented eficiently and distributedly by each resource, and evaluate their eficiency by providing upper bounds on their price of anarchy. These bounds are parametrized by both and the underlying utility functions and are shown to be best-possible for -subsidy mechanisms. Finally, we apply our results to the particular case of monomial utility functions of degree ∈ (0, 1), and derive bounds on the price of anarchy that are parametrized by and .
In several real-life contexts arising from economics, operation research and computer science, we face the necessity of allocating a set of utility-producing resources to agents, in such a way that the total utility is maximized. For example, we could consider a scenario, connected with management engineering, in which each resource models a project or a task to be completed, and each agent is an employee of a company, or a server in a content delivery network, that can be assigned to one of the tasks. It is reasonable to assume that, the more the number of employees assigned to a task, the more the quality of the completed task (or the lower the completion time, or the higher the probability that the task will be correctly completed). Indeed, the employees assigned to the same task can work in team, and it is expected that the resulting quality improves as the working team includes new members.
When completed, each task generates a profit (i.e., a utility) that is proportional to the resulting quality, and this profit (or a percentage of it) is equally shared among the employees who contributed to the task. As the number of employees and tasks could be very high, the presence of a centralized coordinator imposing all the assignments might be impracticable. Therefore, a decentralized implementation of the system, where each worker autonomously decides which task she wants to contribute to, is a more reasonable choice. To describe the efects of decentralization, we consider a game representation of the system in which each worker acts as a player who aims at maximizing the fraction of the profit that she receives (i.e., her payof). This creates an interplay of strategic behavior, in which players compete with each other by selecting the tasks (i.e., the resources) that maximize their payof. This may lead to suboptimal outcomes, in which the total utility is lower than the one achievable by a central authority imposing an optimal assignment of players to resources.
Algorithmic game theory [
Our Contribution. Given the dificulties in coordinating the players’ strategic behavior, a
reasonable approach to convey them toward better pure Nash equilibria is that of providing
subsidies encouraging the use of certain resources. Several works [
In this work, we show how to improve the eficiency of decentralized allocation systems,
when the total amount of subsidies available to each resource is somewhat constrained by the
total utility that can be generated by the resource itself. We model allocation systems as a class
of games, called utility-sharing games, which constitutes a subclass of the general framework
of monotone valid utility games defined in [
The main novelty of this work is the design and the analysis of -subsidy mechanisms ( -SMs), a new class of subsidy allocation mechanisms that, parametrized by a value ≥ 1, allocate to each resource an amount of subsidies that is at most − 1 times the utility produced by the resource, so that the players’ payofs can be re-scaled up by a multiplicative factor .
We provide tight bounds on the price of anarchy guaranteed by -SMs for several classes of utility-sharing games. In particular, we resort to a particular sub-class of -SMs, called optimalcongestion-based -SMs, that can be computed and executed in polynomial time (Theorem 1), and we provide upper bounds on the resulting price of anarchy that depend on , the number of players , and the class of utility functions of the game (Theorem 2); we also provide simpler bounds that depend on and only (Corollary 1).
Conversely, we show that optimal-congestion-based mechanisms achieve best-possible
performances within the general class of -SMs, that is, no -SM can further lower our bounds
on the price of anarchy (Theorem 3, Corollaries 2 and 3). Finally, we apply our general results
to the specific case of utility functions representable as monomials of fixed degree ∈ [
We point out that, for any utility-sharing game and suficiently large ≥ 1, all pure Nash
equilibria induced by optimal-congestion-based -SMs maximize the total utility (Remark 1).
Thus, our approach guarantees the same performance of the subsidy allocation mechanisms
studied in [
Further Related Work. The first general game-theoretic model for decentralized resource
allocation systems with payof-maximizing players is that of monotone valid utility games
[
A work that is strictly close to ours is [17], which studies the price of anarchy of (an equivalent
model of) utility-sharing games, and provided tight bounds that are parametrized by the number
of players and the considered utility functions; tight bounds on the price of anarchy for more
general settings in which the set of available resources is player-specific is also provided. Papers
[
The problem of determining mechanisms improving the price of anarchy in utility-sharing
games (so as for their variants and/or generalizations) has been widely considered in the
literature. In [
Utility-sharing games are strictly related to the cost-minimization game-theoretic model
of congestion games [20, 21]. Congestion games are resource selection games with a finite set
of cost-minimizing players and a finite set of resources, where each player selects a subset
of resources (among a finite collection that is player-specific), and the cost of each selected
resource is a function of the number of players selecting it. In particular, utility-sharing games
can be seen as the payof-maximization version of congestion games with symmetric players
[22, 23] (that is, all players can share all resources) and singleton strategies (that is, each player
can select exactly one resource). The problem of measuring the price of anarchy of congestion
games has been a hot-topic in algorithm game theory in the last two decades [24, 25, 26, 27],
and several works have provided upper and lower bounds depending on the considered
costfunctions [28, 29, 30, 31, 32, 22, 33, 34] or the structure of the players’ strategies [35, 29, 36, 31,
37, 38, 39, 22, 23]. Furthermore, several works have also focused on the design and analysis
of mechanisms to improve the price of anarchy. The following classes of mechanisms have
been widely studied: taxation mechanisms [
Given an integer ≥ 1, let [] := {1, 2, . . . , } denote the set of the first positive integers. Given an integer ℎ ≥ 0, N≥ ℎ denotes the set of natural numbers higher or equal to ℎ, and N := N≥ 1 denotes the set of natural numbers.
Utility-Sharing Games. A utility-sharing game is formally defined as a tuple SG = (, , ()∈) where = [] is a set of players, = {1, . . . , } is a set of resources and : N≥ 0 → R≥ 0 is a non-negative (resource) utility function associated with each resource ∈ . We further assume that (i) (0) = 0, (ii) () > 0 for some ∈ N, and is (iii) non-decreasing and (iv) concave in N≥ 0; in particular, (i) holds since a resource without players does not produce any utility, (ii) has been considered to avoid the presence of resources that do not produce any utility, (iii) holds since the more the players, the higher the utility, and (iv) holds since the contribution of a player who joins a resource decreases as the congestion of that resource increases.
A strategy profile (or assignment) = ( )∈ is a configuration in which each player has
selected resource = ∈ , and denotes the strategy of player in . The congestion
( ) := |{ ∈ : = }| of resource in strategy profile is the total amount of players
selecting in . Given a strategy profile , the payof of player is defined as ( ) :=
( ( ))/ ( ). Informally, we assume that the utility achieved on each resource is
equally shared among the players selecting it, and this fraction of utility determines the payof
of each player. The total utility function SUM( ) := ∑︀∈ (( )) is equal to the sum of
all resource utilities. We have that SUM( ) = ∑︀∈ (( )) = ∑︀∈ |{ ∈ : =
}| · ( ( () )) = ∑︀∈ ( ), that is, the total utility can be seen as the sum of all payofs,
i.e., it is a social welfare function that is proportional to the overall satisfaction of all players.
Pure Nash Equilibria and Price of Anarchy. All players aim at maximizing their payofs,
regardless of the others. As a reasonable outcome of selfish behavior, we consider the notion of
pure Nash equilibrium [
A universal metric to measure the impact of selfishness on the total utility is the price of
anarchy [
OPT(SG) , that is, the worst-case ratio between the optimal total PoA(SG) = max ∈PNE(SG) SUM( ) utility and that achieved by any pure Nash equilibrium of SG. We observe that, the lower the price of anarchy, the lower the impact of selfish behavior in terms of total utility. Subsidy Mechanisms. We assume that each resource can implement a local policy that, by means of a subsidy, may increase the payofs of players selecting it, up to a maximum factor ≥ 1. We refer to this set of local policies as -subsidy mechanisms ( -SMs). In particular, an -subsidy mechanism Π takes as input a utility-sharing game SG and returns a new utility-sharing game SG = (, , (′)∈ ) that will be played in place of SG, where each utility function ′ is called perceived utility of resource , and verifies the following properties: (i) ′() = () + () for any ∈ N≥ 0, for an opportune non-negative subsidy function ; (ii) the subsidy function is locally computed by resource , based only on the knowledge of the initial game SG and the congestion ( ) of in a given strategy profile ; (iii) () ≤ ( − 1) · (), that is, ′() ≤ (), for any ∈ N≥ 0. We observe that the perceived utilities ′ lead to a new players’ payof ′( ) = ( ( ( ))+ ( ( )))/ ( ), for any strategy profile of SGΠ and player ∈ .
In the following, we provide some justifications on the above properties characterizing -SMs. Property (i) states that the perceived utility is equal to the overall value given by the utility and the additional subsidy (determined by ) assigned by the mechanism to each resource; then, both the utility and the subsidy are shared by the players selecting the resource, thus leading to new players’ payofs. Property (ii) is motivated by the fact that the mechanism can be reasonably executed in a distributed way, where each resource uses its local information on the congestion, without knowing the congestion of the other resources. Finally, property (iii) is motivated by scenarios in which the subsidies, because of some budget constraints, are limited by a factor of the utility achievable by each resource.
Given an -SM Π for SG, the price of anarchy of SG under Π is defined as PoA(SG, Π ) =
OPT(SG) , where PNE(SG ) is the set of pure Nash equilibria of the game SG max ∈PNE(SG ) SUM( ) induced by Π , OPT(SG) is the optimal total utility of the initial game SG and SUM( ) is the total utility computed according to the utility-functions of the initial game SG. Informally, the price of anarchy of a game SG under an -SM Π measures how bad is a pure Nash equilibrium of the game modified by Π compared with the optimal total utility, but considering as total utility functions those related to the initial game SG. The modelling choice for which subsidies are not taken into account in the total utility appearing in the price of anarchy is motivated by the realistic scenario in which players receive money as subsidies, and then the same amount of money is lost by the central authority (e.g., a governmental entity) who disburses them. Thus, the overall contribution to the social welfare of subsidies is null, that is, the social welfare continues to be equal to the total utility without subsidies.
In this section, we first define a specific -SM that is polynomial-time computable and executable, and then we measure its eficiency by providing bounds on the resulting price of anarchy. We ifrst provide some preliminary notation. We say that a function : N≥ 0 → R≥ 0 is payof-regular if the function defined as () := · () is a proper utility function (that is, determines the payof associated with utility function ). Given a class of payof-regular functions , let ℒ() := { : () = · · (), ∈ , > 0} denote the family of utility functions whose related payof functions, up to a scaling factor, belong to . The following proposition, whose proof is deferred to the full version of the paper, shows some useful properties of payof-regular functions.
Proposition 1. Each payof-regular function is non-increasing and positive in N.
Fix ≥ 1. Given a game SG = (, , ()∈ ) and an optimal strategy profile * of SG, let Π ( * ) be an -SM for SG that returns a new utility-sharing game SG = (, , (′)∈ ) with perceived utility functions ′ defined as follows. For any ∈ N≥ 0 and strategy profile : ′() = {︃(),
if ( ) ≥ ( * ), · (), if ( ) < ( * ). (1) Such an -SM is called optimal-congestion-based. We observe that optimal-congestion-based -SMs encourage the use of resources whose congestion in the optimal strategy profile is higher than that in the played strategy profile, and this is done by increasing the utility of such resources by a factor of .
In the following theorem, we show that optimal-based-congestion -SMs, under mild assumptions, can be computed and executed in polynomial time.
Theorem 1. Given ≥ 1 and a utility-sharing game SG with utility functions in ℒ(), with containing payof-regular functions only, we can compute and execute in polynomial time an optimal-based-congestion -SM for SG.
Sketch. We observe that, once an optimal strategy profile * of SG is computed, then the -SM Π ( * ) can be executed in polynomial time. Thus, to show the claim, it is suficient to show that an optimal strategy profile * for SG can be computed in polynomial time. To compute an optimal strategy profile * of SG, we can apply a greedy algorithm that processes all players following the ordering induced by their indices, and each processed player ∈ is assigned to obviously runs in polynomial time. under the strategy profile obtained after assigning the first the resource that minimizes the quantity (− 1, + 1) − (− 1,), where ties are broken in favor of the resource with lower index, and − 1, denotes the congestion of resource − 1 players. This greedy algorithm
The proof that the strategy profile returned by the greedy algorithm is optimal for SG is based on the concavity of the utility functions , and is deferred to the full version.
In the following, we provide an upper bound on the price of anarchy under optimal-congestionbased -SMs, that is parametrized by the considered class of utility functions; furthermore, we show that, under mild assumptions on the considered utility functions, no -SM can improve the eficiency achieved by optimal-congestion-based -SMs, that is, the latter are essentially the best possible -SMs mechanisms.
PoA Upper Bounds.
We first give some preliminary notation. Given a payof-regular function , let , ( ) :=
sup ,∈N≥ 0:≥ ≥ ≥ 0,>0
︂( () − 1 ()
︂) and () := sup∈N , (). we observe that , ( ) ≥ 1
− 1/ (indeed, it is suficient to set = in the argument of the supremum to get a value equal to 1 − 1/ ); furthermore, the denominator appearing in the righthand part of the definition is always non-zero, as each utility function () is positive in > 0 (by Proposition 1). Given a class of payof-regular functions , let , () := sup∈ , ( ) SG, we have that Theorem 2. Let be a class of payof-regular functions. Given a game SG with at most ≥ 2 players and utility functions in ℒ(), and given an optimal-congestion-based -SM Π ( * ) for PoA(SG, Π ( * )) ≤ Sketch. Let SG = (, , ()∈ ) be a utility-sharing game with utility functions in ℒ(), and let * be a social optimum of SG. Let be a pure Nash equilibrium of the game SG obtained after applying the -SM Π ( * ). Let and be the congestions of each resource ∈ in * and , respectively.
For each ∈ such that ≥ , we have that by definition of , (). On the other hand, for any ∈ such that > , we have that () − ( − ) ( + 1) ≤ () − ( − ) () = () ≤ (), integrality of and ). where ( ) ≥
( + 1) ≥ ( ) trivially holds if = 0, and holds even if > 0, since is payof-regular (thus, non-increasing by Proposition 1) and + 1 ≤ (by the (2) (3)
Now, we recall that each utility function := of SG can be written as () := · · (), with > 0 and ∈ . Thus, as is a pure Nash equilibrium in the new game SG , we observe that the value of each utility function ′ := ′ achieved when playing in SG is equal to ′() = ′ · · (), where ′ = {︃, · , if < if ≥ , ; analogously, the payof function of each player in the new game
rium is equal to ′ · (). Thus, since is an equilibrium in game SG and all payof-regular functions are non-increasing (by Proposition 1), for each pair of resources (, ℎ), we have that ′() ≥ ℎ′ℎ(ℎ + 1). deferred to the full version): Furthermore, as ∑︀∈ = | | = ∑︀∈ , we have the following equality (whose proof is ∑︁ ∈:≥ ( − ) =
∑︁ ∈:> ( − ).
By combining (5) and (6), we obtain the following inequality: ∑︁ ( − ) ′() −
∑︁ ( − ) ′( + 1) ≥ 0. :≥
:< following inequalities (a more detailed list of inequalities is deferred to the full version): By combining (2), (3) and (7), and by exploiting the definition of ′ given in (4), we get the ∑︁ ( − ) :< = ⏞′ ⏟
⎤ ( + 1)⎦ (8) (4) (5) (6) (7) (9) (10) (11) ∑︁ , ()() + () ⎦ + ⎣
∑︁ ()⎦ 1 ︂) ⎤ ⎡ ︂) ⎤ ⎤ ∑︁
︂( 1 + , ()︂) ∑︁ (),
∈ ∑︁ () +
∑︁ ( − ) ⏞′⏟ () − ⎡ 1 ⎣ :≥
1 ∑︁ (() − ( − ) ( + 1))⎦ = 1 ⎤
︂) ⎤ ︂) ⎤
⎡ :< ∑︁ :< ︂( 1 (indeed, we already observed at the beginning of this section that 1 − 1/ ≤ , ()). where (8) follows from (7), (9) follows from (2) and (3), and (10) holds since 1/ + , () ≥ 1 Therefore, from (11) we have that ∑︀∈ ( ) ≤
∑︀∈ ( ), ︂( 1
PoA(SG, Π ( * )) = ∑︀∈ () ∑︀∈ ()
∑︀∈ () = ∑︀∈ () ≤ 1 + , ().
Remark 1 (Optimal PoA via -SMs). Given a class of payof-regular functions and a game SG = (, , ()∈ ) with utility functions in ℒ(), if we apply to SG an optimal-basedcongestion SM with >
mmainx∈∈,,∈∈[[]](((())//)) , we have that the resulting pure Nash equilibrium
necessarily coincides with the optimal strategy profile * which the SM is based on (the
proof of this property is deferred to the full version). Thus, the price of anarchy becomes 1, and
we re-obtain the optimal performance of the subsidy mechanisms considered in [
The following corollary of Theorem 2 provides a tight bound on the price of anarchy that depends on the number of players only, under mild assumptions on the considered utility functions. based -SM Π ( * ) for SG, we have that Corollary 1. Let SG be a utility-sharing game with at most ≥ in a class ℒ(), with containing payof-regular functions only. For any optimal-congestion2 players and utility functions PoA(SG, Π ( * )) ≤ 1 + 1 (︂
1 )︂ 1 − ≤ 1 + .
1 Proof. To prove the claim it is suficient to show that Indeed, by combining the previous inequality with Theorem 2, we get (︀ () − 1 ())︀
If = 0, inequality (12) trivially holds. If ≥ 1, we have that proper utility functions only) and (13) holds since ≥ 1 and ≤ . where the first inequality follows from the fact that the functions of the type · () are necessarily non-decreasing (as they belong to a class ℒ() that contains, by assumptions, (12) (13) PoA Lower Bounds. In the following theorem, whose full proof is deferred to the full version, we show that no -SM can outperform the worst-case eficiency achieved by optimal-basedcongestion -SMs.
Theorem 3. Let be a class of payof-regular functions. For any > 0 and ∈ N≥ 2, there exists a utility-sharing game SG with at most players such that, for any -SM Π for SG, the price of anarchy of SG under Π is higher than 1/ + , () − .
Sketch. Fix > 0 and ∈ N≥ 2. By definition of supremum, we have that there exist , ∈ N0 with ≥ ≥ and > 0, and ∈ such that 1 + Consider a game SG = (, , ()∈) with = | | ≤ players and a set of − + 1 resources. Set ′ := ∖ {1} = {2, . . . , − +1}. The utility function of resource 1 is 1() := 1 · · (), with 1 := 1, while the utility function of each resource ∈ ′ is () := 2() =: 2 · · (), with 2 := (1)
() . One can show that, for any -SM Π , the ratio between the total utilities of * and , the claim follows. strategy profile in which all players choose resource 1 is a pure Nash equilibrium under the application of Π . Now, let * be the strategy profile in which players choose resource 1, while each of the remaining − players chooses a diferent resource in ′. By estimating the
We also have the following corollary of Theorem 3, that provides a lower bound that does not depend on the maximum number of players (the proof is deferred to the full version). Corollary 2. Let be a class of payof-regular functions. For any > 0, there exists a utilitysharing game SG such that, for any -SM Π for SG, the price of anarchy of SG under Π is higher than 1/ + () − .
Finally, the following corollary of Theorem 3 and Corollary 2 shows that the upper bound provided in Corollary 1 is tight (the proof is deferred to the full version). such that, for any -SM Π for SG, the price of anarchy of SG under Π is at least 1+ 1 (︀ 1 Corollary 3. (i) For any ∈ N≥ 2, there exists a utility-sharing game SG with at most players − 1 )︀ . (ii) Furthermore, for any >
0, there exists a game SG such that the price of anarchy of SG under Π is higher than 1 + 1 − .
Remark 2 (PoA without subsidies). If = 1, an optimal-congestion-based -SM does not change
the utility functions of the original game. Thus, the tight bounds provided in Theorems 2-3
and Corollaries 1-3 with = 1 are also tight bounds on the price of anarchy of utility-sharing
games without the use of any subsidy mechanism, that is, we can re-obtain the tight bounds on
the price of anarchy provided in [
In the following result, we apply Theorems 2 and 3 to characterize the price of anarchy under optimal-congestion-based -SMs of games with monomial utility-functions of fixed degree ∈ (0, 1) (the proof is deferred to the full version). 1.8 1.6
1, the price of anarchy under optimal-based-congestion -SMs for games when the underlying utility functions are not specified (Corollaries 1 and 3), while the blue line represents the price of anarchy of games whose utility functions are monomials of degree 1/2 (a case of Theorem 4). From this comparison, we observe that the bounds on the price of anarchy that depend on the specific class of utility functions (Theorems 2 and 3) may be definitely more precise than the bounds which depend on only (Corollaries 1 and 3). have PoA(SG, Π ( * )) ≤ achieve, in general, a better price of anarchy.
1 − Theorem 4. . Given ∈ (0, 1), a utility-sharing game SG with utility functions of type () = · for some > 0 and an optimal-congestion-based -SM Π ( * ) for SG, we + , with = min {︁( ) 1− 1 , 1}︁ . Furthermore, no -SM can Remark 3 (PoA without subsidies (cont.)). For = 1, the tight bounds provided in Corollary 4 are also tight bounds on the price of anarchy of utility-sharing games with monomial profit functions without the use of any -SM, that is, we can re-obtain the tight bounds on the price of anarchy provided in [17].
In the following example we show an application of Theorem 4 with = 12 . 4 2+4 for <
2, and equal to 1 for ≥ over ≥ 1, and we compare it with the case of general functions.
Example 1. By applying Theorem 4, we have that the price of anarchy under optimal-congestionbased -SMs of games SG with monomial utility functions of type () = · 1/2 is equal to 2. In Figure 1, we see how the price of anarchy varies
In this work, we have shown how to reduce the price of anarchy in a large class of resourceselection games with utility-maximizing players, by resorting to a limited amount of subsidies that can be distributed among resources and is subsequently shared among the players who use them.
Our work leaves several research directions on the problem of improving the eficiency in utility sharing games via limited subsidies.
First of all, our subsidy mechanisms dynamically depend on the actual congestion of each resource. Thus, it would be interesting to show how the eficiency can be improved if subsidies do not depend on the current game configuration. Another research direction could be that of finding subsidy (or taxing) mechanisms with limited budget for more general variants of utility-sharing games, where players can also be cost-minimizers (as in congestion games [21]) and/or have diferent weights and/or can select diferent subsets of resources).
Finally, still with the aim of improving the eficiency of the considered games, it would be also interesting to consider other mechanisms than subsidy disbursements (e.g., Stackelberg strategies [47]). [15] M. X. Goemans, L. E. Li, V. S. Mirrokni, M. Thottan, Market sharing games applied to content distribution in ad hoc networks, IEEE J. Sel. Areas Commun. 24 (2006) 1020–1033. [16] S. Gollapudi, K. Kollias, D. Panigrahi, V. Pliatsika, Profit sharing and eficiency in utility games, in: 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, pp. 43:1–43:14. [17] J. R. Marden, T. Roughgarden, Generalized eficiency bounds in distributed resource allocation, IEEE Trans. Autom. Control. 59 (2014) 571–584. [18] J. R. Marden, A. Wierman, Distributed welfare games, Oper. Res. 61 (2013) 155–168. [19] E. Anshelevich, A. Dasgupta, J. M. Kleinberg, É. Tardos, T. Wexler, T. Roughgarden, The price of stability for network design with fair cost allocation, SIAM Journal on Computing 38 (2008) 1602–1623. [20] V. Bilò, C. Vinci, Coping with Selfishness in Congestion Games - Analysis and Design via LP Duality, Monographs in Theoretical Computer Science. An EATCS Series, Springer, 2023. [21] R. W. Rosenthal, A class of games possessing pure-strategy Nash equilibria, International
Journal of Game Theory 2 (1973) 65–67. [22] D. Fotakis, Stackelberg strategies for atomic congestion games, Theory of Computing
Systems 47 (2010) 218–249. [23] T. Lücking, M. Mavronicolas, B. Monien, M. Rode, A new model for selfish routing,
Theoretical Computer Science 406 (2008) 187–2006. [24] B. Awerbuch, Y. Azar, A. Epstein, The price of routing unsplittable flow, in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), 2005, pp. 57–66. [25] V. Bilò, A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games, Theory of Computing Systems 62 (2018) 1288–1317. [26] G. Christodoulou, E. Koutsoupias, The price of anarchy of finite congestion games, in: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), 2005, pp. 67–73. [27] T. Roughgarden, E. Tardos, How bad is selfish routing?, Journal of ACM 49 (2002) 236–259. [28] S. Aland, D. Dumrauf, M. Gairing, B. Monien, F. Schoppmann, Exact price of anarchy for polynomial congestion games, SIAM Journal on Computing 40 (2011) 1211–1233. [29] K. Bhawalkar, M. Gairing, T. Roughgarden, Weighted congestion games: price of anarchy, universal worst-case examples, and tightness, ACM Transactions on Economics and Computation 2 (2014) 1–23. [30] V. Bilò, G. Monaco, L. Moscardelli, C. Vinci, Nash social welfare in selfish and online load balancing, ACM Trans. Econ. Comput. 10 (2022). [31] V. Bilò, C. Vinci, On the impact of singleton strategies in congestion games, in: Proceedings of the 25th Annual European Symposium on Algorithms (ESA), 2017, pp. 17:1–17:14. [32] V. Bilò, On the robustness of the approximate price of anarchy in generalized congestion games, Theoretical Computer Science 906 (2022) 94–113. [33] P. Kleer, Price of anarchy for parallel link networks with generalized mean objective, OR
Spectr. 45 (2023) 27–55. [34] T. Roughgarden, Intrinsic robustness of the price of anarchy, Journal of ACM 62 (2015) 32:1–32:42. [35] F. Benita, V. Bilò, B. Monnot, G. Piliouras, C. Vinci, Data-driven models of selfish routing: Why price of anarchy does depend on network topology, in: Proceedings of the 16th International Conference on Web and Internet Economics (WINE), 2020, pp. 252–265. [36] V. Bilò, L. Moscardelli, C. Vinci, Uniform mixed equilibria in network congestion games with link failures, in: Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP), 2018, pp. 146:1–146:14. [37] V. Bilò, C. Vinci, The price of anarchy of afine congestion games with similar strategies,
Theoretical Computer Science 806 (2020) 641–654. [38] I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos, L. Moscardelli, Tight bounds for selfish and greedy load balancing, Algorithmica 61 (2011) 606–637. [39] J. Correa, J. de Jong, B. de Keijzer, M. Uetz, The ineficiency of nash and subgame perfect equilibria for network routing, Mathematics of Operations Research 44 (2019) 1286–1303. [40] V. Bilò, C. Vinci, Dynamic taxes for polynomial congestion games, ACM Transantions on
Economics and Computation 7 (2019) 15:1–15:36. [41] I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, Taxes for linear atomic congestion games,
ACM Transactions on Algorithms 7 (2010) 13:1–13:31. [42] R. Cole, Y. Dodis, T. Roughgarden, How much can taxes help selfish routing?, Journal of
Computer and System Sciences 72 (2006) 444–467. [43] D. Paccagnan, R. Chandan, B. L. Ferguson, R. J. Marden, Optimal taxes in atomic congestion games, ACM Transactions on Economics and Computation 9 (2021) 19:1–19:33. [44] D. Paccagnan, M. Gairing, In congestion games, taxes achieve optimal approximation, in: Proceedings of the 22nd ACM Conference on Economics and Computation (EC), 2021, pp. 743–744. [45] V. Ravindran Vijayalakshmi, A. Skopalik, Improving approximate pure nash equilibria in congestion games, in: Proceedings of the 16th International Conference of Web and Internet Economics (WINE), 2020, pp. 280–294. [46] V. Bilò, C. Vinci, On stackelberg strategies in afine congestion games, Theory of Computing
Systems 63 (2019) 1228–1249. [47] T. Roughgarden, Stackelberg scheduling strategies, SIAM Journal on Computing 33 (2004) 332–350. [48] N. Stein, T. Tamir, Stackelberg strategies for weighted load balancing games, in: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, FedCSIS 2022, Sofia, Bulgaria, September 4-7, 2022, 2022, pp. 373–382. [49] I. Caragiannis, V. Gkatzelis, C. Vinci, Coordination mechanisms, cost-sharing, and approximation algorithms for scheduling, in: Proceedings of the 13th International Conference on Web and Internet Economics (WINE), 2017, pp. 74–87. [50] G. Christodoulou, E. Koutsoupias, A. Nanavati, Coordination mechanisms, Theoretical
Computer Science 410 (2009) 3327–3336. [51] R. Cole, J. Correa, V. Gkatzelis, V. Mirrokni, N. Olver, Decentralized utilitarian mechanisms for scheduling games, Games and Economic Behavior 92 (2014) 306–326. [52] P. von Falkenhausen, T. Harks, Optimal cost sharing for resource selection games, Mathematics of Operations Research 38 (2013) 184–208. [53] V. Gkatzelis, K. Kollias, T. Roughgarden, Optimal cost-sharing in general resource selection games, Operations Research 64 (2016) 1230–1238.