Optimality of Shapley Value Mechanism under Sybil Strategies

Authors: Bruno Mazorra Roig

Abstract:

In the realm of cost-sharing mechanisms, the vulnerability to Sybil strategies, where agents can create fake identities to manipulate outcomes, has not yet been studied. In this paper, we delve into the intricacies of different cost-sharing mechanisms proposed in the literature, highlighting its non-Sybil-resistance nature. Furthermore, we prove that under mild conditions, a Sybil-proof cost-sharing mechanism for public excludable goods is at least (n/2 + 1)−approximate. This finding reveals an exponential increase in the worst-case social cost in environments where agents are restricted from using Sybil strategies. We introduce the concept of Sybil Welfare Invariant mechanisms, where a mechanism maintains its worst-case welfare under Sybil strategies for every set of prior beliefs with full support even when the mechanism is not Sybil-proof. Finally, we prove that the Shapley value mechanism for public excludable goods holds this property and so deduce that the worst-case social cost of this mechanism is the nth harmonic number Hn under the equilibrium of the game with Sybil strategies, matching the worst-case social cost bound for cost-sharing mechanisms. This finding carries important implications for decentralized autonomous organizations (DAOs), indicating that they are capable of funding public excludable goods efficiently, even when the total number of agents is unknown.

Keywords: game theory, mechanism design, cost sharing, false-name proofness