Table of Links
Abstract and 1. Introduction
1.1 Technical Overview
1.2 Related Work
-
Model and Preliminaries and 2.1 Transaction Fee Mechanisms
2.2 The TFM Desiderata
-
Understanding OCA
3.1 The Difference Between SCP and OCA
3.2 Useful Preliminary Results for OCA-proof TFMs
-
Deterministic OCA-proof Mechanisms
-
Randomized OCA-proof Mechanisms
-
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.
:::
\
