Truthful, Credible, and Optimal Auctions for Matroids via Blockchains and Commitments
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918085181571072 |
|---|---|
| author | Ganesh, Aadityan Zhang, Qianfan |
| author_facet | Ganesh, Aadityan Zhang, Qianfan |
| contents | We consider a revenue-optimizing auctioneer in single-dimensional environments with matroid feasibility constraints. Akbarpour and Li (2020) argue that any revenue-optimal, truthful, and credible mechanism requires unbounded communication. Recent works (Ferreira and Weinberg, 2020; Essaidi et al., 2022; Chitra et al., 2024) circumvent their impossibility for the single-item setting through the use of cryptographic commitments and blockchains. We extend their results to matroid feasibility constraints.
At a high level, the two-round Deferred-Revelation Auction (DRA) discussed by Ferreira and Weinberg (2020) and Chitra et al., (2024) requires each bidder to submit a deposit, which is slashed upon presenting verifiable evidence indicating a deviation from the behaviour prescribed by the mechanism. We prove that the DRA satisfies truthfulness, credibility and revenue-optimality for all matroid environments when bidders' values are drawn from $α$-strongly regular distributions for $α> 0$. Further, we argue that the DRA is not credible for any feasibility constraint beyond matroids and for any smaller deposits than suggested by previous literature even in single-item environments.
Finally, we modify the Ascending Deferred-Revelation Auction (ADRA) for single-item settings proposed by Essaidi et al., (2022) for arbitrary bidder value distributions. We implement a deferred-revelation variant of the deferred-acceptance auction for matroids due to Bikhchandani et al., (2011), which requires the same bounded communication as the ADRA. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04592 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Truthful, Credible, and Optimal Auctions for Matroids via Blockchains and Commitments Ganesh, Aadityan Zhang, Qianfan Computer Science and Game Theory Data Structures and Algorithms We consider a revenue-optimizing auctioneer in single-dimensional environments with matroid feasibility constraints. Akbarpour and Li (2020) argue that any revenue-optimal, truthful, and credible mechanism requires unbounded communication. Recent works (Ferreira and Weinberg, 2020; Essaidi et al., 2022; Chitra et al., 2024) circumvent their impossibility for the single-item setting through the use of cryptographic commitments and blockchains. We extend their results to matroid feasibility constraints. At a high level, the two-round Deferred-Revelation Auction (DRA) discussed by Ferreira and Weinberg (2020) and Chitra et al., (2024) requires each bidder to submit a deposit, which is slashed upon presenting verifiable evidence indicating a deviation from the behaviour prescribed by the mechanism. We prove that the DRA satisfies truthfulness, credibility and revenue-optimality for all matroid environments when bidders' values are drawn from $α$-strongly regular distributions for $α> 0$. Further, we argue that the DRA is not credible for any feasibility constraint beyond matroids and for any smaller deposits than suggested by previous literature even in single-item environments. Finally, we modify the Ascending Deferred-Revelation Auction (ADRA) for single-item settings proposed by Essaidi et al., (2022) for arbitrary bidder value distributions. We implement a deferred-revelation variant of the deferred-acceptance auction for matroids due to Bikhchandani et al., (2011), which requires the same bounded communication as the ADRA. |
| title | Truthful, Credible, and Optimal Auctions for Matroids via Blockchains and Commitments |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.04592 |