Cost Sharing Mechanisms for Fair Pricing of Resource Usage

摘要

We propose a simple and intuitive cost mechanism which assigns costs for the competitive usage of m resources by n selfish agents. Each agent has an individual demand; demands are drawn according to some probability distribution. The cost paid by an agent for a resource it chooses is the total demand put on the resource divided by the number of agents who chose that same resource. So, resources charge costs in an equitable, fair way, while each resource makes no profit out of the agents. We call our model the Fair Pricing model. Its fair cost mechanism induces a non-cooperative game among the agents. To evaluate the Nash equilibria of this game, we introduce the Diffuse Price of Anarchy, as an extension of the Price of Anarchy that takes into account the probability distribution on the demands. We prove: