Title: The Weighted Proportional Allocation Mechanism

Abstract

We consider a simple mechanism for allocation of resources to users that allows for discrimination of users by a revenue-maximizing provider. The mechanism is a natural extension of the well known proportional allocation by allocating proportional to weighted bids. The mechanism can be applied by providers whose resource constraints are described by general polyhedrons, which allows for complex resources such as, for example, networks of processors or links, data centres, and sponsored search.

We study a competitive system where users strategically choose their individual bids trying to maximize their payoffs and the provider aims at maximizing the revenue. We consider the revenue earned by the provider and the social welfare. Specifically, we find that the revenue under price anticipating users is lower bounded by k/(k+1) times the revenue under standard third-degree price discrimination with a set of k users excluded. Under price anticipating users with linear utility functions, we find that the social welfare is at least 1/(1+2/\sqrt{3}) 100 \approx 46% of the maximum social welfare, and this bound is tight. We extend this result to a broad class of utility functions, which accommodated many utility functions found in literature, and to an oligopoly of multiple competing providers.

Our results indicate that the weighted proportional allocation simultaneously achieves competitive revenue and social welfare, under selfish users and selfish providers.