Foundational Models for DSIC, MMIC, and OCA‑Proof Cryptoeconomic Mechanisms

Table of Links

Abstract and 1. Introduction

1.1 Technical Overview

1.2 Related Work

2. Model and Preliminaries and 2.1 Transaction Fee Mechanisms

   2.2 The TFM Desiderata

3. Understanding OCA

   3.1 The Difference Between SCP and OCA

   3.2 Useful Preliminary Results for OCA-proof TFMs

4. Deterministic OCA-proof Mechanisms

5. Randomized OCA-proof Mechanisms

6. Discussion and References

A. Missing Proofs

B. Non-anonymous Deterministic Mechanisms

2 Model and Preliminaries

We follow the standard model used by the literature for TFMs [LSZ19; Rou21; Rou20; CS23; SCW23]. The main technical assumption we make, which we use to simplify the discussion, is that the auction is a single-item auction, i.e., that the block size is 1. We interchangeably use the terms auction, mechanism, or TFM to refer to the object of our discussion, depending on what is most appropriate in the context. Some missing proofs are in Appendix A.

2.1 Transaction Fee Mechanisms

Payment & burn

The payment and burn rules respectively define the amount of fees paid by each transaction when included in a block, and how much of each payment is “burnt” and taken out of circulation instead of being given to the miner, with both rules enforced by the mechanism.

Basic definitions

We proceed with several definitions that are used throughout our analysis.

Definition 2.7 (Basic Auction Properties). We say an auction is:

Throughout the text, we assume the basic auction properties hold. The only exception to it is in Appendix B where we explore removing the anonymity assumption.

We follow with Claim 2.8, which is a useful “helper” result. We provide the proof in Appendix A.

2.2 The TFM Desiderata

We now go over the literature’s standard desiderata for “good” TFMs, which includes the DSIC and MMIC properties. These properties are usually augmented by some collusion resistance notion, i.e., either OCA-proofness or SCP.

Collusion Notions

A coalition of users and the miner may collude to increase their joint utility (as given in Def. 2.6). Their collusion can entail any kind of deviation from the “honest” protocol, i.e., users may bid untruthfully, and the miner can deviate from the intended allocation rule.

The OCA-proofness notion, introduced by Roughgarden [Rou21], compares the colluding coalition with the coalition comprised of the miner and the winning bidders of the canonical outcome, produced by following the mechanism’s intended allocation. The traditional definition given by [Rou21] does not include a c identifier for the amount of bidders in the coalition, but we add it since it allows considering how explicitly well-coordinated the collusion has to be in order to succeed.

We show in Claim 2.13 that the condition for c-OCA-proofness takes a nice form when it holds for any value of c. Due to space considerations, the proof is given in Appendix A.

The line of works started by Chung and Shi [CS23] use the SCP collusion notion, which compares the aggregate utility of the colluding coalition with the same coalition’s “honest” aggregate utility, i.e., the coalition’s utility if they were to act honestly.