In this work, we consider the problem of improving the efficiency 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 payoff is re-scaled up to a factor α ≥ 1. We design a specific sub-class of α-subsidy mechanisms, that can be implemented efficiently and distributedly by each resource, and evaluate their efficiency 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 p ∈ (0,1), and derive bounds on the price of anarchy that are parametrized by p and α.
Utility-Sharing Games: How to Improve the Efficiency with Limited Subsidies
Vittorio Bilo;Lucaleonardo Bove;Cosimo Vinci
2023-01-01
Abstract
In this work, we consider the problem of improving the efficiency 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 payoff is re-scaled up to a factor α ≥ 1. We design a specific sub-class of α-subsidy mechanisms, that can be implemented efficiently and distributedly by each resource, and evaluate their efficiency 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 p ∈ (0,1), and derive bounds on the price of anarchy that are parametrized by p and α.File | Dimensione | Formato | |
---|---|---|---|
3300.pdf
accesso aperto
Tipologia:
Versione editoriale
Licenza:
Creative commons
Dimensione
1.01 MB
Formato
Adobe PDF
|
1.01 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.