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 3 Conclusion We introduced concave pro-rata games and established several useful properties under relatively mild conditions. In particular, we showed the existence of a unique equilibrium that is symmetric and pure. This equilibrium can be computed efficiently by solving a single variable, unimodal optimization problem. We further established that the price of anarchy is Ω(n) in the number of players, relative to the optimal ‘fair’ allocation. We illustrated how concave pro-rata games connect to a recent proposal for a batched decentralized exchange and numerically studied the behavior of agents engaged in such a game in the iterated setting for a specific form of utility function. Future work includes further study of the optimal arbitrage problem for batched decentralized exchanges. References [1] Angeris, G., Agrawal, A., Evans, A., Chitra, T., Boyd, S.: Constant Function Market Makers: Multi-asset Trades via Convex Optimization. In: Handbook on Blockchain, p. 31. Springer, first edn. (2022) [2] Angeris, G., Evans, A., Chitra, T.: A Note on Privacy in Constant Function Market Makers (Mar 2021) [3] Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, UK; New York (2004) [4] Budish, E., Cramton, P., Shim, J.: The High-Frequency Trading Arms Race: Frequent Batch Auctions as a Market Design Response. The Quarterly Journal of Economics 130(4), 1547–1621 (Nov 2015). https://doi.org/10.1093/qje/qjv027 [5] Chitra, T., Angeris, G., Evans, A.: Differential Privacy in Constant Function Market Makers. Financial Cryptography and Data Security 2022 (2022) [6] Daian, P., Goldfeder, S., Kell, T., Li, Y., Zhao, X., Bentov, I., Breidenbach, L., Juels, A.: Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In: 2020 IEEE Symposium on Security and Privacy (SP). pp. 910–927 (2020). https://doi.org/10.1109/SP40000.2020.00040 [7] Diamond, S., Boyd, S.: CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research 17(83), 1–5 (2016) [8] O’Donoghue, B., Chu, E., Parikh, N., Boyd, S.: Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications 169(3), 1042–1068 (June 2016), http://stanford.edu/~boyd/papers/scs. html [9] Penumbra Labs: ZSwap - The Penumbra Protocol. https://protocol.penumbra.zone/main/zswap.html [10] Rosen, J.B.: Existence and Uniqueness of Equilibrium Points for Concave N-Person Games. Econometrica 33(3), 520 (Jul 1965). https://doi.org/10.2307/1911749 [11] Selten, R.: Preispolitik der Mehrproduktenunternehmung in der statischen Theorie (1970) [12] Von Neumann, J., Morgenstern, O.: Theory of games and economic behavior. In: Theory of games and economic behavior. Princeton university press (2007) [13] Walther, T.: Multi-token Batch Auctions with Uniform Clearing Prices (Jul 2018) A Numerics The results of §1 provide insight into the equilibrium behavior of concave pro-rata games. Here we explore the transient behavior of such games through simulation. Shared equilibrium. The (unique) symmetric pure equilibrium strategy is the solution to problem (4). This is easy to compute using the first order optimality conditions for problem (4) given in (6). Plugging in this particular form of f, we obtain the following quadratic equation: Shared equilibrium. For more details, the code is available at (anonymized for review). B Additional Numerics Here we expand on the simulations introduced in appendix A using a class of utility function that allows us to express many quantities of interest in closed form. Game setup. We consider the following three scenarios: Game setup. Simulation results. In our simulations, we fix β = 0.5 and γ = 0.05. We average each reported value over 100 trials. In figure 4, the intial strategy of each player is drawn uniformly at random from the interval (0, w/n), where w is a value such that f(w) = 0. Simulation results. The left plot of figure 4 illustrates that the number of iterations needed to reach the unique equilibrium, in the absence of budget constraints, scales superlinearly in the number of players. The right plot demonstrates that in the scenario of bounded strategy updates, for small values of δ, the number of iterations required to reach equilibrium increases significantly when compared to the unbounded strategy update scenario. Price of Anarchy The equilibrium payoff can easibly be found to be Price of Anarchy Similarly, it can be show that the optimal payoff conditioned on every agent receving the same payoff is given by We obtain the price of anarchy by taking the ratio of the equilibrium payoff and the optimal payoff: We again fix β = 0.5 and γ = 0.05. The left plot of figure 6 illustrates the optimal payoff function and the equilibrium payoff function as a function of the number of players n, while the right plot of figure 6 illustrates the price of anarchy as a function of n. C Relaxing strict concavity The statement above follows from the negation of both (a) and (b). This equivalence has a simple interpretation: if the point (0, 0) is collinear with any other two points on the graph of f, {(s, f(s)) | s > 0}, then the function f is a piecewise function with a linear segment starting at 0. The converse of this is that if the function f has no linear segment around 0 (i.e., every linear over estimator around 0 lies strictly above f) then any chord must lie strictly below the function. D Rosen condition 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.

The Price of Anarchy in Concave Pro-Rata Games for Decentralized Markets

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

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

Decreasing Latency for High Frequency Crypto Arbitrage Trading

Ever tried arbitrage at a crypto exchange? Here’s the deal.

How to make money on arbitrage with cryptocurrencies

Arbitrage in the Cryptocurrency Market

Make Money With Retail-Arbitrage-As-A-Service Using Amazon and AliExpress [A How To Guide]

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

Decreasing Latency for High Frequency Crypto Arbitrage Trading

Ever tried arbitrage at a crypto exchange? Here’s the deal.

How to make money on arbitrage with cryptocurrencies

Arbitrage in the Cryptocurrency Market

Make Money With Retail-Arbitrage-As-A-Service Using Amazon and AliExpress [A How To Guide]

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps