On Sybil-proof Mechanisms
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914315046486016 |
|---|---|
| author | Pan, Minghao Mazorra, Bruno Schlegel, Christoph Mamageishvili, Akaki |
| author_facet | Pan, Minghao Mazorra, Bruno Schlegel, Christoph Mamageishvili, Akaki |
| contents | We show that in the single-parameter mechanism design environment, the only non-wasteful, symmetric, incentive compatible and Sybil-proof direct mechanism is a second price auction with symmetric tie-breaking. Thus, if there is private information, lotteries or other mechanisms that do not always allocate to a highest-value bidder are not Sybil-proof or not incentive compatible. Moreover, we show that our main (im)possibility result extends beyond linear valuations, but not to multi-unit object allocation with capacity constrained bidders.
We also provide examples of mechanisms (with higher interim payoff for the bidders than a second price auction) that satisfy all of the other axioms and a weaker, Bayesian notion of Sybil-proofness. Thus, our (im)possibility result does not generalize to the Bayesian setting and we have a larger design space: With Sybil constraints, equivalence between dominant strategy and Bayesian implementation (that holds in classical single-parameter mechanism design without Sybils) no longer holds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_14485 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Sybil-proof Mechanisms Pan, Minghao Mazorra, Bruno Schlegel, Christoph Mamageishvili, Akaki Computer Science and Game Theory We show that in the single-parameter mechanism design environment, the only non-wasteful, symmetric, incentive compatible and Sybil-proof direct mechanism is a second price auction with symmetric tie-breaking. Thus, if there is private information, lotteries or other mechanisms that do not always allocate to a highest-value bidder are not Sybil-proof or not incentive compatible. Moreover, we show that our main (im)possibility result extends beyond linear valuations, but not to multi-unit object allocation with capacity constrained bidders. We also provide examples of mechanisms (with higher interim payoff for the bidders than a second price auction) that satisfy all of the other axioms and a weaker, Bayesian notion of Sybil-proofness. Thus, our (im)possibility result does not generalize to the Bayesian setting and we have a larger design space: With Sybil constraints, equivalence between dominant strategy and Bayesian implementation (that holds in classical single-parameter mechanism design without Sybils) no longer holds. |
| title | On Sybil-proof Mechanisms |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2407.14485 |