TY - GEN
T1 - A new mechanism for the free-rider problem
AU - Sanghavi, Sujay
AU - Hajek, Bruce
PY - 2005
Y1 - 2005
N2 - The free-rider problem arises in the provisioning of public resources, when users of the resource have to contribute towards the cost of production, Selfish users may have a tendency to misrepresent preferences - so as to minimize individual contributions - leading to inefficient levels of production of the resource. Groves and Loeb formulated a classic model capturing this problem, and proposed (what later came to be known as) the VCG mechanism as a solution. However, in the presence of heterogeneous users and communication constraints, or in decentralized settings, implementing this mechanism places an unrealistic communication burden. In this paper we propose a class of alternative mechanisms for the same problem as considered by Groves and Loeb, but with the added constraint of severely limited communication between users and the provisioning authority. When these mechanisms are used, efficient production is ensured as a Nash equilibrium outcome, for a broad class of users. Furthermore, a natural bid update strategy is shown to globally converge to efficient Nash equilibria. An extension to multiple public goods with inter-related valuations is also presented.
AB - The free-rider problem arises in the provisioning of public resources, when users of the resource have to contribute towards the cost of production, Selfish users may have a tendency to misrepresent preferences - so as to minimize individual contributions - leading to inefficient levels of production of the resource. Groves and Loeb formulated a classic model capturing this problem, and proposed (what later came to be known as) the VCG mechanism as a solution. However, in the presence of heterogeneous users and communication constraints, or in decentralized settings, implementing this mechanism places an unrealistic communication burden. In this paper we propose a class of alternative mechanisms for the same problem as considered by Groves and Loeb, but with the added constraint of severely limited communication between users and the provisioning authority. When these mechanisms are used, efficient production is ensured as a Nash equilibrium outcome, for a broad class of users. Furthermore, a natural bid update strategy is shown to globally converge to efficient Nash equilibria. An extension to multiple public goods with inter-related valuations is also presented.
KW - Algorithms
KW - Economics
KW - Theory
UR - http://www.scopus.com/inward/record.url?scp=29244472821&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=29244472821&partnerID=8YFLogxK
U2 - 10.1145/1080192.1080200
DO - 10.1145/1080192.1080200
M3 - Conference contribution
AN - SCOPUS:29244472821
SN - 1595930264
SN - 9781595930262
T3 - Proceedings of ACM SIGCOMM 2005 Workshops: Conference on Computer Communications
SP - 122
EP - 127
BT - Proceedings of ACM SIGCOMM 2005 Workshops
PB - Association for Computing Machinery
T2 - ACM SIGCOMM 2005 Workshops: Conference on Computer Communications
Y2 - 22 August 2005 through 26 August 2005
ER -