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 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 Abstract In this paper, we introduce a family of games called concave pro-rata games. In such a game, players place their assets into a pool, and the pool pays out some concave function of all assets placed into it. Each player then receives a pro-rata share of the payout; i.e., each player receives an amount proportional to how much they placed in the pool. Such games appear in a number of practical scenarios, including as a simplified version of batched decentralized exchanges, such as those proposed by Penumbra. We show that this game has a number of interesting properties, including a symmetric pure equilibrium that is the unique equilibrium of this game, and we prove that its price of anarchy is Ω(n) in the number of players. We also show some numerical results in the iterated setting which suggest that players quickly converge to an equilibrium in iterated play. Introduction Existing blockchain systems come to consensus on transactions in batches, called blocks. Yet the economic mechanisms those transactions interact with are generally designed to process each individual transaction sequentially, making their behavior reliant on the ordering of transactions within the batch. This abstraction mismatch is the primary source of miner extractible value (MEV), defined as economic value that can be captured by the block proposer (originally the miner) who selects and sequences the transactions to be included in the batch [6]. However, rather than trying to blind the block proposer, or choose a “fair” ordering (which is difficult, if not impossible, to construct in any direct sense on current systems) within a batch, we could alternatively attempt to design economic mechanisms which do not depend on the order of transactions within a block, and instead, process each batch of transactions ‘all at once’. These mechanisms would then be aligned with the actual ordering provided by the consensus mechanism, stepping from one batch of transactions to the next in the same discrete time steps in which consensus happens. One such mechanism is a ‘pro-rata mechanism’. In this mechanism, there is some known notion of value: for example, every user might want to trade some asset A for another, say B, and everyone ‘pitches in’ some amount of asset A into a pool. After everyone has placed their amounts, the pool, as a whole, is traded on an exchange for some amount of asset B, and the resulting amount of asset B is distributed back to each player, in proportion to how much of asset A each player placed in the pool. It is not difficult to show that such a mechanism has the desired property: the order in which players placed asset A into the collective pool does not change how much of asset B each player receives. Using some ideas from cryptography, this game can additionally be implemented in a way that does not reveal any one player’s contributions or identity [9], and so may be considered a simultaneous game. On the other hand, mechanisms of this form often lead to interesting phenomena as users must now consider the possible actions of other users when planning their own actions. A natural framework to study these kinds of problems, where players must reason about the strategies of other players, recursively, is via game theory and the study of the equilibria of games [12]. This paper serves to cleanly set up the game resulting from a pro-rata mechanism in a simple mathematical framework and derive a number of useful results for such games. This paper. The paper is organized as follows. We introduce the concave pro-rata game in §1 and show a few interesting properties under mild conditions. Such properties include the existence and uniqueness of a symmetric pure strategy equilibrium and an explicit way of efficiently computing this equilibrium by solving a single variable, unimodal optimization problem. We also show some simple bounds for the price of anarchy. In §2 we then describe how this type of game connects to a recent proposal for a batched decentralized exchange. We run a number of simulations in §A and §B, illustrating the price of anarchy and showing that in the iterated setting agents appear to converge quickly to the specified equilibrium. This paper is available on arxiv under CC BY 4.0 DEED license. 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 Abstract In this paper, we introduce a family of games called concave pro-rata games. In such a game, players place their assets into a pool, and the pool pays out some concave function of all assets placed into it. Each player then receives a pro-rata share of the payout; i.e., each player receives an amount proportional to how much they placed in the pool. Such games appear in a number of practical scenarios, including as a simplified version of batched decentralized exchanges, such as those proposed by Penumbra. We show that this game has a number of interesting properties, including a symmetric pure equilibrium that is the unique equilibrium of this game, and we prove that its price of anarchy is Ω(n) in the number of players. We also show some numerical results in the iterated setting which suggest that players quickly converge to an equilibrium in iterated play. Introduction Existing blockchain systems come to consensus on transactions in batches, called blocks. Yet the economic mechanisms those transactions interact with are generally designed to process each individual transaction sequentially, making their behavior reliant on the ordering of transactions within the batch. This abstraction mismatch is the primary source of miner extractible value (MEV), defined as economic value that can be captured by the block proposer (originally the miner) who selects and sequences the transactions to be included in the batch [6]. However, rather than trying to blind the block proposer, or choose a “fair” ordering (which is difficult, if not impossible, to construct in any direct sense on current systems) within a batch, we could alternatively attempt to design economic mechanisms which do not depend on the order of transactions within a block, and instead, process each batch of transactions ‘all at once’. These mechanisms would then be aligned with the actual ordering provided by the consensus mechanism, stepping from one batch of transactions to the next in the same discrete time steps in which consensus happens. One such mechanism is a ‘pro-rata mechanism’. In this mechanism, there is some known notion of value: for example, every user might want to trade some asset A for another, say B, and everyone ‘pitches in’ some amount of asset A into a pool. After everyone has placed their amounts, the pool, as a whole, is traded on an exchange for some amount of asset B, and the resulting amount of asset B is distributed back to each player, in proportion to how much of asset A each player placed in the pool. It is not difficult to show that such a mechanism has the desired property: the order in which players placed asset A into the collective pool does not change how much of asset B each player receives. Using some ideas from cryptography, this game can additionally be implemented in a way that does not reveal any one player’s contributions or identity [9], and so may be considered a simultaneous game. On the other hand, mechanisms of this form often lead to interesting phenomena as users must now consider the possible actions of other users when planning their own actions. A natural framework to study these kinds of problems, where players must reason about the strategies of other players, recursively, is via game theory and the study of the equilibria of games [12]. This paper serves to cleanly set up the game resulting from a pro-rata mechanism in a simple mathematical framework and derive a number of useful results for such games. This paper. The paper is organized as follows. We introduce the concave pro-rata game in §1 and show a few interesting properties under mild conditions. Such properties include the existence and uniqueness of a symmetric pure strategy equilibrium and an explicit way of efficiently computing this equilibrium by solving a single variable, unimodal optimization problem. We also show some simple bounds for the price of anarchy. In §2 we then describe how this type of game connects to a recent proposal for a batched decentralized exchange. We run a number of simulations in §A and §B, illustrating the price of anarchy and showing that in the iterated setting agents appear to converge quickly to the specified equilibrium. This paper. 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.

Pro-Rata Mechanisms: Game Theory Insights for Decentralized Exchanges

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

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

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

A Quick Crash Course on Crypto Economics

A Quick Crash Course on Crypto Economics

Blockchain Adoption in Developing Nations is more Realistic

Can you trust the price? What’s behind crypto’s irrational markets

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

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

A Quick Crash Course on Crypto Economics

A Quick Crash Course on Crypto Economics

Blockchain Adoption in Developing Nations is more Realistic

Can you trust the price? What’s behind crypto’s irrational markets

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps