Utility-Sharing Games: How to Improve the Efficiency with Limited Subsidies

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 𝑝 ∈ (0, 1), and derive bounds on the price of anarchy that are parametrized by 𝑝 and 𝛼.