Comparing SCP and OCA in Transaction Fee Mechanisms: Core Differences and Results

Table of Links

Abstract and 1. Introduction

1.1 Technical Overview

1.2 Related Work

1. Model and Preliminaries and 2.1 Transaction Fee Mechanisms

   2.2 The TFM Desiderata

2. Understanding OCA

   3.1 The Difference Between SCP and OCA

   3.2 Useful Preliminary Results for OCA-proof TFMs

3. Deterministic OCA-proof Mechanisms

4. Randomized OCA-proof Mechanisms

5. Discussion and References

   \

A. Missing Proofs

B. Non-anonymous Deterministic Mechanisms

3 Understanding OCA

3.1 The Difference Between SCP and OCA

We observe that while OCA-proofness compares the utility of every possible manipulating coalition with the joint utility of the winning coalition under the protocol’s intended allocation, SCP compares it with the counter-factual of the same coalition’s honest utility (i.e., the utility obtained without any manipulation). We formally prove this distinction in Claim 3.1.

\

\

\ We now prove Claim 3.3, which together with Claim 3.1 implies that SCP is stricter than OCA.

\

\ Now that we distinguished SCP and OCA-proofness, we turn our focus to characterizing and obtaining results for TFMs that satisfy OCA-proofness.

\

3.2 Useful Preliminary Results for OCA-proof TFMs

In this section, we derive results that hold for any (possibly randomized) mechanism, and without further qualifiers which we define later such as scale-invariant mechanisms. First, we state Myerson’s lemma for DSIC mechanisms.

\ We continue by reasoning about the single-bidder case.

\ Lemma 3.5. With a single bidder, all DSIC+1-OCA-proof single-item auctions have 0 seller revenue.

\ The above statement works for the single bidder case, but does not extend to more bidders. We demonstrate it through the example of the second-price auction:

\ Example 3.6. The second-price auction is DSIC and 1-OCA-proof (as observed in [Rou21]). First, notice that in the single bidder case, the second-price auction indeed satisfies that the payment rule equals the burn rule (both are always 0). However, with more bidders, the form of the joint utility of the winner coalition no longer resembles the form of the utility of a specified bidder, since it takes the value of the maximal bidder, depending on b (rather than any fixed bidder: This also separates the analysis of OCA-proofness from that of SCP, for which we know that DSIC+1-SCP indeed yields 0 miner revenue).

\

:::info Authors:

(1) Yotam Gafni, Weizmann Institute (yotam.gafni@gmail.com);

(2) Aviv Yaish, The Hebrew University, Jerusalem (aviv.yaish@mail.huji.ac.il).

:::

:::info This paper is available on arxiv under CC BY 4.0 DEED license.

:::

\