On the Efficiency of Markets with Two-Sided Proportional Allocation Mechanisms

We analyze the performance of resource allocation mechanisms for markets in which there is competition amongst both consumers and suppliers (namely, two-sided markets). Specifically, we examine a natural generalization of both Kelly’s proportional allocation mechanism for demand-competitive markets [9] and Johari and Tsitsiklis’ proportional allocation mechanism for supply-competitive markets [7].

We first consider the case of a market for one divisible resource. Assuming that marginal costs are convex, we derive a tight bound on the price of anarchy of about 0.5887. This worst case bound is achieved when the demand-side of the market is highly competitive and the supply-side consists of a duopoly. As more firms enter the market, the price of anarchy improves to 0.64. In contrast, on the demand side, the price of anarchy improves when the number of consumers decreases, reaching a maximum of 0.7321 in a monopsony setting. When the marginal cost functions are concave, the above bound smoothly degrades to zero as the marginal costs tend to constants. For monomial cost functions of the form

$C(x)= cx^{1+\frac{1}{d}}$

, we show that the price of anarchy is

$\Omega(\frac{1}{d^2})$

.

We complement these guarantees by identifying a large class of two-sided single-parameter market-clearing mechanisms among which the proportional allocation mechanism uniquely achieves the optimal price of anarchy. We also prove that our worst case bounds extend to general multi-resource markets, and in particular to bandwidth markets over arbitrary networks.