2024/07/19 by M. Pan, Pan, Minghao, Mazorra, Bruno +3 · 2 citations
Computer Science · #Advanced Authentication Protocols Security #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.2407.14485
openalex publication_date 2024/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.