Concave Pro-rata Games: Equilibrium payoff

Table of Links

Abstract and Introduction

1 The concave pro-rata game

1.1 Symmetric pure strict equilibrium

1.2 Uniqueness of equilibrium

1.3 Equilibrium payoff

2 Batched decentralized exchanges

2.1 Arbitrage

3 Conclusion and References

A Numerics

B Additional Numerics

C Relaxing strict concavity

D Rosen condition

1.3 Equilibrium payoff

Conditioned on each player receiving the same payoff (a fairness condition), the optimal allocation every player would get is

which is, by definition, at least as good as the equilibrium payoff:

where q > 0 is the solution to (4). In fact, we can show that the optimal fair allocation is always strictly better than the equilibrium payoff. To see this, note that, under the assumptions on f introduced above, we know sup f is achieved by some value 0 < q? < w, satisfying f 0 (q ? ) = 0. Rearranging the first order optimality condition for q in problem (4) gives

for all n > 1 since f(q) > 0. This means that q does not satisfy the optimality condition for maximizing f, so f(q) < f(q ? ) = sup f. (In fact, this says slightly more: using the concavity of f, we have that q > q? , i.e., that players ‘overpay’ at equilibria when n > 1.)

Price of anarchy. Given the same assumptions as the beginning of §1.2 on the function f, it is not difficult to show that the price of anarchy satisfies

as the number of players n becomes large for some constant C. To see this, consider the first order optimality conditions for y (4):

Note that f 0 (q) < 0 since q > 0 and f(q) > 0, so

whenever n > 1. Since f is concave, then f 0 is monotonically nonincreasing, and, since q ≤ w for every n we have that

Finally, we know that sup f is constant in the number of players, so