The Weighted Proportional Allocation Mechanism

We consider a weighted proportional allocation of resources that allows providers to discriminate usage of resources by users. This framework is a generalization of well-known proportional allocation accommodating allocation of resources proportional to weighted bids or proportional to submitted bids but with weighted payments.

We study a competition game where everyone is selfish: providers choose discrimination weights aiming at maximizing their individual revenues while users choose their bids aiming at maximizing their individual payoffs. We analyze revenue and social welfare of this game. We find that the revenue is lower bounded by k/(k+1) times the revenue under standard price discrimination scheme, where a set of k users is excluded. For users with linear utility functions, we find that the social welfare is at least 1/(1+2/√3) of the maximum social welfare (approx. 46%) and that this bound is tight. We extend the efficiency result to a broad class of utility functions and to multiple competing providers. We also describe an algorithm used by the provider to adjust the user discrimination weights without a prior knowledge of user utility functions and establish convergence to equilibrium points of our game.

Our results show that, in many cases, weighted proportional sharing achieves competitive revenue and social welfare, despite the fact that everyone is selfish. The mechanism allows for resource constraints described by general polyhedrons, thus accommodating a variety of resources, including bandwidth of communication networks, systems of computing resources, and sponsored search ad slots.