Utility-Sharing Games: How to Improve the Eficiency with Limited Subsidies (short paper)

Abstract

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 self-interested 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 sub-optimal, 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 .

Keywords

• eol>Utility Games
• Resource Allocation
• Subsidy Mechanisms
• Pure Nash Equilibrium
• Price of Anarchy

1. Introduction

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 [ 2 ] ofers several tools to describe how the strategic choices of the players may afect the total utility achieved by all resources. First, the notion of pure Nash equilibrium [ 3 ], that is an outcome in which no player can increase her payof by unilaterraly deviating to another strategic choice, is used to model stable solutions arising from selfish behavior. Then, the Price of Anarchy [ 4 ], which compares the total utility of any pure Nash equilibrium against the optimal total utility achievable in a centralized and coordinated environment, is adopted to quantify the lack of cooperation and coordination.

2. 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 [ 5, 6, 7, 8, 9, 10, 11, 12 ] showed the efectiveness of this idea, by designing ad-hoc subsidy allocation mechanisms that are able to improve the price of anarchy. The amount of subsidies that these mechanisms require, however, can be very high, thus limiting their applicability to most real-life contexts, where budgets are usually severely constrained.

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 [ 13 ], and is similar and/or equivalent to other game classes studied in [ 14, 15, 16, 17, 9, 18, 19 ]. In utility-sharing games, we have a finite set of players, a finite set of resources available to the players, and each resource is associated with a certain utility function whose value is equally shared among the players selecting it. Each player aims at maximizing her payof , given by the fraction of utility she receives.

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 resource, so that the players’ payofs can be re-scaled up by a multiplicative factor . each resource an amount of subsidies that is at most − 1 times the utility produced by the

2.1. Eficiency of -SMs for General Utility Functions

We provide tight bounds on the price of anarchy guaranteed by -SMs for several classes of utility-sharing games. In particular, the obtained results hold for payof-regular functions, which are very general payof functions whose related utility functions satisfy some weak regularity properties (e.g., monotonicity and concavity). ∈ N and a payof-regular function , let

To improve the eficiency of utility-sharing games with payof-regular functions, we consider a sub-class of -SMs, called optimal-congestion-based -SMs, that can be computed and executed in polynomial time. In particular, an optimal-congestion-based -SM Π ( * ) assigns to each resource a subsidy that depends on the congestion of under a given optimal strategy prolfie * and the strategy profile played in the game. In the following theorem, 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. We first give some preliminary notations. Given ≥ 1, , ( ) :=

sup ,∈N≥ 0:≥ ≥ ≥ 0,>0 () − ︂( 1

︂) () ( ())− 1; () := sup∈N , (). furthermore, given a class of payof-regular functions , let , () := sup∈ , ( ) and we have that PoA(SG, Π ( * )) ≤ + , () ≤

+ (). 1 1 Theorem 1. Let be a class of payof-regular functions. Given a game SG with at most ≥ 2 players and payof functions in , and given an optimal-congestion-based -SM Π ( * ) for SG,

We also show that optimal-congestion-based mechanisms achieve the best-possible performances within the general class of -SMs, that is, no -SM can further lower our bounds on the price of anarchy.

Theorem 2. Let be a class of payof-regular functions. For any > exists a utility-sharing game SG with at most players and payof functions in 0 and ∈ N≥ 2, there such that, for any -SM Π for SG, the price of anarchy of SG under Π is higher than 1/ + , () − .

Finally, the following corollary of Theorem 1 and 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.

︂(

1 )︂ Corollary 1. Let SG be a utility-sharing game with at most ≥ regular functions. For any optimal-congestion-based -SM Π ( * ) for SG, we have that 2 players and payofPoA(SG, Π ( * )) ≤ 1 + 1 1

− ≤ 1 + 1 . Furthermore, no -SM can achieve, for general payof-regular functions, a better price of anarchy. 1.8 1.6 1.2 A o

1, the price of anarchy under optimal-based-congestion -SMs for games when the underlying utility functions are not specified (Corollaries 1), while the blue line represents the price of anarchy of games whose utility functions are monomials of degree 1/2 (a case of Theorem 3).

We have that, for any utility-sharing game and suficiently large ≥ 1, all pure Nash equilibria induced by optimal-congestion-based -SMs maximize the total utility. Thus, our approach guarantees the same performance of the subsidy allocation mechanisms studied in [ 9 ], that, diferently from ours, may fail under some budget limitations. Furthermore, for = 1, we re-obtain the tight bounds on the price of anarchy for utility-sharing games without subsidies, already shown in [ 9, 18 ].

2.2. The Case of Monomial Utility Functions

As a case study, we apply our general results to the specific case of utility functions representable as monomials of fixed degree ∈ [ 0, 1 ]. have PoA(SG, Π ( * )) ≤ achieve, in general, a better price of anarchy.

1 − Theorem 3. . 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

As an example, we consider the case of = 12 . By Theorem 3, we have that the price of anarchy under optimal-congestion-based -SMs of games SG with monomial utility functions of type () = · 1/2 is equal to 2+4 for < 4 2, and equal to 1 for ≥ 2. In Figure 1, we functions. see how the price of anarchy varies over ≥ 1, and we compare it with the case of general

3. Further Related Work

An extended version of the results presented in this work appeared in [20].

The first general game-theoretic model for decentralized resource allocation systems with payof-maximizing players is that of monotone valid utility games [ 13 ], where the payof functions satisfy some mild assumptions, such as monotonicity and submodularity w.r.t. the selected resources. In this seminal paper, a tight bound of 2 on the price of anarchy of monotone valid utility games is provided. Subsequently, several (sub)classes of monotone valid utility games have been introduced and studied. A work that is strictly close to ours is [18], 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 [ 15, 9 ] model strategic project selection as specific instantiations of monotone valid utility games, and provide more specific bounds on the price of anarchy and other eficiency metrics (such as the price of stability [ 21]). In [17, 19], the eficiency of specific monotone valid utility games where, diferently from our model of utility-sharing games the sharing rules do not necessarily split each resource utility in an equal way among the players selecting it, has been considered.

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 [ 9 ], it is shown how to assign a credit (i.e., a subsidy) to each project, so as to guarantee that any pure Nash equilibrium is an optimal strategy profile. A considerable amount of work [ 6, 7, 8, 10, 11, 12 ] shows how to modify the payofs of the players participating in utility-sharing games (e.g., via subsidies), with the purpose of improving the eficiency of pure Nash equilibria; in particular, tight bounds on the resulting price of anarchy, that depend on the considered class of utility functions, are provided.

Utility-sharing games are strictly related to the cost-minimization game-theoretic model of congestion games [22, 23]. 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. 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 cost-functions [28, 29, 30, 31, 32, 33, 34, 35] or the structure of the players’ strategies [36, 29, 37, 31, 38, 39, 40, 33, 41]. Furthermore, several works have also focused on the design and analysis of mechanisms to improve the price of anarchy, e.g., taxation mechanisms [ 42, 43, 44, 8, 45, 46, 47 ], Stackelberg strategies [48, 33, 49, 50], coordinationmechanisms [51, 52, 53] and cost-sharing mechanisms [51, 54, 55].

4. Future Works

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 [23]) 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 [49]). trafic routing and auctions, in: Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS), 2002, pp. 416–425. [14] J. Augustine, N. Chen, E. Elkind, A. Fanelli, N. Gravin, D. Shiryaev, Dynamics of profitsharing games, Internet Math. 11 (2015) 1–22. [15] V. Bilò, L. Gourvès, J. Monnot, Project games, Theor. Comput. Sci. 940 (2023) 97–111. [16] 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. [17] 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. [18] J. R. Marden, T. Roughgarden, Generalized eficiency bounds in distributed resource allocation, IEEE Trans. Autom. Control. 59 (2014) 571–584. [19] J. R. Marden, A. Wierman, Distributed welfare games, Oper. Res. 61 (2013) 155–168. [20] V. Bilò, L. Bove, C. Vinci, Utility-sharing games: How to improve the eficiency with limited subsidies, in: Proceedings of the 24th Italian Conference on Theoretical Computer Science, ICTCS, 2023. To appear. [21] 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. [22] 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. [23] R. W. Rosenthal, A class of games possessing pure-strategy Nash equilibria, International

Journal of Game Theory 2 (1973) 65–67. [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] D. Fotakis, Stackelberg strategies for atomic congestion games, Theory of Computing

Systems 47 (2010) 218–249. [34] P. Kleer, Price of anarchy for parallel link networks with generalized mean objective, OR

Spectr. 45 (2023) 27–55. [35] T. Roughgarden, Intrinsic robustness of the price of anarchy, Journal of ACM 62 (2015) 32:1–32:42. [36] 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. [37] 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. [38] V. Bilò, C. Vinci, The price of anarchy of afine congestion games with similar strategies,

Theoretical Computer Science 806 (2020) 641–654. [39] I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos, L. Moscardelli, Tight bounds for selfish and greedy load balancing, Algorithmica 61 (2011) 606–637. [40] 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. [41] T. Lücking, M. Mavronicolas, B. Monien, M. Rode, A new model for selfish routing,

Theoretical Computer Science 406 (2008) 187–2006. [42] V. Bilò, C. Vinci, Dynamic taxes for polynomial congestion games, ACM Transantions on

Economics and Computation 7 (2019) 15:1–15:36. [43] I. Caragiannis, C. Kaklamanis, P. Kanellopoulos, Taxes for linear atomic congestion games,

ACM Transactions on Algorithms 7 (2010) 13:1–13:31. [44] R. Cole, Y. Dodis, T. Roughgarden, How much can taxes help selfish routing?, Journal of

Computer and System Sciences 72 (2006) 444–467. [45] 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. [46] 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. [47] 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. [48] V. Bilò, C. Vinci, On stackelberg strategies in afine congestion games, Theory of Computing

Systems 63 (2019) 1228–1249. [49] T. Roughgarden, Stackelberg scheduling strategies, SIAM Journal on Computing 33 (2004) 332–350. [50] 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. [51] 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. [52] G. Christodoulou, E. Koutsoupias, A. Nanavati, Coordination mechanisms, Theoretical

Computer Science 410 (2009) 3327–3336. [53] R. Cole, J. Correa, V. Gkatzelis, V. Mirrokni, N. Olver, Decentralized utilitarian mechanisms for scheduling games, Games and Economic Behavior 92 (2014) 306–326. [54] P. von Falkenhausen, T. Harks, Optimal cost sharing for resource selection games, Mathematics of Operations Research 38 (2013) 184–208. [55] V. Gkatzelis, K. Kollias, T. Roughgarden, Optimal cost-sharing in general resource selection games, Operations Research 64 (2016) 1230–1238.

References

[1] R. De Benedictis , M. Castiglioni , D. Ferraioli , V. Malvone , E. S. Marco Maratea , L. Serafini , I. Serina , E. Tosello , A. Umbrico , M. Vallati , Preface to the Italian Workshop on Planning and Scheduling , RCRA Workshop on Experimental evaluation of algorithms for solving problems with combinatorial explosion, and SPIRIT Workshop on Strategies, Prediction, Interaction, and Reasoning in Italy (IPS-RCRA-SPIRIT 2023 ), in: Proceedings of the Italian Workshop on Planning and Scheduling , RCRA Workshop on Experimental evaluation of algorithms for solving problems with combinatorial explosion, and SPIRIT Workshop on Strategies, Prediction, Interaction, and Reasoning in Italy (IPS-RCRA-SPIRIT 2023) co-located with 22th International Conference of the Italian Association for Artificial Intelligence (AI* IA 2023 ), 2023 .

[2] N. Nisan , T. Roughgarden , E. Tardos , V. V. Vazirani (Eds.), Algorithmic Game Theory , Cambridge University Press, 2007 .

[3] J. F. Nash , Equilibrium points in -person games, Proceedings of the National Academy of Science 36 ( 1950 ) 48 - 49 .

[4] E. Koutsoupias , C. Papadimitriou , Worst-case equilibria , in: Proceedings of the 16th Annual Conference on Theoretical Aspects of Computer Science (STACS) , 1999 , pp. 404 - 413 .

[5] J. Augustine , I. Caragiannis , A. Fanelli , C. Kalaitzis , Enforcing eficient equilibria in network design games via subsidies , Algorithmica 72 ( 2015 ) 44 - 82 .

[6] R. Chandan , D. Paccagnan , J. R. Marden , When smoothness is not enough: Toward exact quantification and optimization of the price-of-anarchy , in: 58th IEEE Conference on Decision and Control , CDC 2019 , Nice, France, December 11-13 , 2019 , IEEE, 2019 , pp. 4041 - 4046 .

[7] R. Chandan , D. Paccagnan , J. R. Marden , Tractable mechanisms for computing near-optimal utility functions , in: AAMAS '21: 20th International Conference on Autonomous Agents and Multiagent Systems , Virtual Event, United Kingdom, May 3- 7 , 2021 , ACM, 2021 , pp. 306 - 313 .

[8] B. L. Ferguson , P. N. Brown , J. R. Marden , The efectiveness of subsidies and taxes in atomic congestion games , IEEE Control Systems Letters 6 ( 2022 ) 614 - 619 .

[9] J. M. Kleinberg , S. Oren , Mechanisms for (mis)allocating scientific credit , Algorithmica 84 ( 2022 ) 344 - 378 .

[10] D. Paccagnan , R. Chandan , J. R. Marden , Utility design for distributed resource allocation - part I: characterizing and optimizing the exact price of anarchy , IEEE Trans. Autom. Control . 65 ( 2020 ) 4616 - 4631 .

[11] D. Paccagnan , R. Chandan , J. R. Marden , Utility and mechanism design in multi-agent systems: An overview , Annu. Rev. Control . 53 ( 2022 ) 315 - 328 .

[12] D. Paccagnan , J. R. Marden , Utility design for distributed resource allocation - part II: applications to submodular, covering, and supermodular problems , IEEE Trans. Autom. Control . 67 ( 2022 ) 618 - 632 .

[13] A. Vetta , Nash equilibria in competitive societies, with applications to facility location,