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)