This content originally appeared on HackerNoon and was authored by Pro Rata Technologies
:::info 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
1.1 Symmetric pure strict equilibrium
2 Batched decentralized exchanges
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
\
\
\ \
:::info This paper is available on arxiv under CC BY 4.0 DEED license.
:::
\
This content originally appeared on HackerNoon and was authored by Pro Rata Technologies
Pro Rata Technologies | Sciencx (2025-04-29T09:25:46+00:00) How Concave Payoff Functions Shape Equilibrium in Strategic Games. Retrieved from https://www.scien.cx/2025/04/29/how-concave-payoff-functions-shape-equilibrium-in-strategic-games/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.