Problem Description
On the theory side, the most important (and maybe the only) additional dimension that permissionless systems bring to mechanism design is the Sybils problem: we cannot verify who participates in a mechanism and which real agent is hiding behind which identity. In other words, we have Sybils and Shills (aka the Auctioneer’s very own Sybils) which might undermine the guarantees that mechanism design otherwise would give. Many mechanisms and principles that have stand the test of time in the classical mechanism design world (VCG, Shapley, plurality voting, Lotteries in all shapes and forms) become vulnerable to Sybils in the permissionless context. It is not a co-incidence that the OG protocol that started Blockchain as a field of research, i.e. the Bitcoin protocol, has as one of its core components a Sybil-resistance mechanism, namely Proof of Work.
Therefore, we should develop the theory of mechanism design with Sybils:
Various questions are natural: is there a revelation principle for Sybils and when not? What is a reasonable notion of “Bayesian Sybil-Proofness”? Can we characterize the set of IC and Sybil-proof mechanisms? How bad (or good) can we make the Price of Anarchy of Sybil-Proof mechanisms?
Related Notes
So far, we have characterized the set of non-wasteful, IC and Sybil-proof mechanisms in a single-parameter MD setting for the “dominant strategy” notion of Sybil proofness. We have interesting examples and research questions for a Bayesian notion of Sybil-proofness. And we have inquired costly Sybils.
- ‣
