Problem Description
In several settings such as combinatorial auctions and public-excludable goods funding, achieving both, dominant-strategy truthfulness and Sybil-proofness, forces the designer to accept a large efficiency loss. To reach acceptable performance in practice, one often relaxes at least one of these two goals.
- In combinatorial auctions, a simple greedy allocation with pay-as-you-bid payments is Sybil-proof but not strategy-proof. Its efficiency still declines as the number of items grows, but this decline is slower than when both conditions are imposed.
- In public-goods funding, enforcing both truthfulness and Sybil-proofness makes the welfare loss rise linearly with community size. In contrast, allowing Sybils limits that loss, which then scales only logarithmically with the number of participants.
This leads to the key question:
Under what conditions, and with which mechanisms, is it better (on terms of welfare loss) to give up strategy-proofness or Sybil-proofness in exchange for smaller welfare losses?
