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.1 Symmetric pure strict equilibrium
There is a strict, pure equilibrium where all players have equal strategies, given by x = (q/n)1 where q is the optimizer of the following problem:
with variable q ∈ R. We will show some properties of this result first and then show that the pure strategy x = (q/n)1 is, indeed, an equilibrium.
Discussion. It may appear that the condition placed on f is very strong, but in fact, any f not satisfying the above condition has only trivial (or no) equilibria. In particular, since f is concave, if f does not satisfy the above condition, either (a) f is strictly positive everywhere except at f(0) = 0, (b) f is strictly negative everywhere except at f(0) = 0, or (c) f = 0. In the first case, there is no equilibrium as any player can improve their payoff by increasing their strategy. In the second case, any player who plays a nonzero strategy receives negative payoff (whereas playing the zero strategy would give 0 payoff). While, in the third case, any strategy is an equilibrium.
Equilibrium properties. The collection of strategies x = (q/n)1 is clearly pure and symmetric. To see that x = (q/n)1 is a strict equilibrium, note that the best response for any player i, when every other player plays strategy q/n is:
Next, note that q > 0 must satisfy the first order optimality conditions of (4):
1.2 Uniqueness of equilibrium
Positivity of equilibria. First we will show that f(v) > 0 for every 0 < v < w. To see this, note that the function f is bounded from below by all of its chords, as it is a concave function. Note that the chord with endpoints (0, 0) and (z, f(z)) lies above the x-axis, except at (0, 0), while the chord with endpoints (z, f(z)) and (w, f(w)) = (w, 0) lies above the x-axis, except at (w, 0), which leads to the final result.
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
