Authors:
(1) Nicholas A. G. Johnson (nagj@mit.edu);
(2) Theo Diamandis (tdiamand@mit.edu);
(3) Alex Evans (aevans@baincapital.com);
(4) Henry de Valence (hdevalence@penumbra.zone);
(5) Guillermo Angeris (gangeris@baincapital.com). Authors: Authors: (1) Nicholas A. G. Johnson (nagj@mit.edu); (2) Theo Diamandis (tdiamand@mit.edu); (3) Alex Evans (aevans@baincapital.com); (4) Henry de Valence (hdevalence@penumbra.zone); (5) Guillermo Angeris (gangeris@baincapital.com). Table of Links Abstract and Introduction Abstract and Introduction 1 The concave pro-rata game 1 The concave pro-rata game 1.1 Symmetric pure strict equilibrium 1.1 Symmetric pure strict equilibrium 1.2 Uniqueness of equilibrium 1.2 Uniqueness of equilibrium 1.3 Equilibrium payoff 1.3 Equilibrium payoff 2 Batched decentralized exchanges 2 Batched decentralized exchanges 2.1 Arbitrage 2.1 Arbitrage 3 Conclusion and References 3 Conclusion and References A Numerics A Numerics B Additional Numerics B Additional Numerics C Relaxing strict concavity C Relaxing strict concavity D Rosen condition 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. Discussion 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: Equilibrium properties. 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. Positivity of equilibria. 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 Price of anarchy. 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 This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

How Concave Payoff Functions Shape Equilibrium in Strategic Games

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Concave Pro-rata Games: The concave pro-rata game

Algorand and the Blockchain Trilemma

Beginner’s Guide to Game Theory

The Science Behind the Fun: Why Game Analytics Matter in Modern Game Development

Bitcoin Core Bug CVE-2018–17144: An Analysis

Concave Pro-rata Games: The concave pro-rata game

Algorand and the Blockchain Trilemma

Beginner’s Guide to Game Theory

The Science Behind the Fun: Why Game Analytics Matter in Modern Game Development

Bitcoin Core Bug CVE-2018–17144: An Analysis

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps