We study the inefficiency of equilibria of resource buying games, i.e., congestion games with arbitrary cost-sharing. Under arbitrary cost-sharing, players do not only declare the resources they will use, they also declare and submit a payment per resource. If the total payments on a resource cover its cost, the resource is activated, otherwise it remains unavailable to the players. Equilibrium existence and inefficiency under arbitrary cost-sharing is very well understood in certain models, such as network design games, where the joint cost of every resource (edge) is constant. In the case of congestion-dependent costs the understanding is not yet complete. For increasing per player cost functions, it is known that the optimal solution can be cast as a Nash equilibrium with the appropriate selection of payments and, hence, the price of stability is 1. In this work we initially focus on the price of anarchy for linear congestion games and prove that (in the direct generalization of the arbitrary cost-sharing model to congestion-dependent costs) it grows to infinity as the number of players grows large. However, we also show that with a natural modification to the cost-sharing model, the price of anarchy becomes 17/3. Turning our attention to strong Nash equilibria, we show that the worst-case inefficiency of the best and worst stable outcomes remains the same as for Nash equilibria, with the strong price of stability staying at ] and the strong price of anarchy staying at 17/3. These results imply arbitrary cost-sharing is comparable to fair cost-sharing as it has a better best-case scenario and a (slightly) worse worst-case scenario. We also study models with restricted strategy sets (uniform matroid congestion games) and properties of best response dynamics with arbitrary cost-sharing.
展开▼
