Ktl-icon-tai-lieu

free-rider

Được đăng lên bởi tien06051992
Số trang: 6 trang   |   Lượt xem: 1949 lần   |   Lượt tải: 0 lần
A New Mechanism for the Free-rider Problem
Sujay Sanghavi

Bruce Hajek

Electrical and Computer Engineering and the
Coordinated Science Laboratory, UIUC

Electrical and Computer Engineering and the
Coordinated Science Laboratory, UIUC

sanghavi@uiuc.edu

b-hajek@uiuc.edu

ABSTRACT

usage is non-exclusionary: it can be used simultaneously and
equally by all users. This is in contrast to a private good,
which has to be divided up among the users, each of whom
has exclusive access to its portion after the auction. Common examples of public goods in everyday life are television
/ radio broadcasts, weather reports and public works such
as libraries.
In proposing the mechanisms described in this paper we
are motivated by public goods in modern communication
and computation systems. Consider for example a large distributed database, containing information available to all
users, without exclusion. Each user contributes towards the
building / maintenance of this database, either in direct
monetary terms or through contributed storage resources.
Since the information in the database is assumed to be freely
available to all users, each user has an incentive to minimize
the amount of resources it contributes. However, if every
user acts according to these selfish considerations, the net
result could be a possibly severe under-provisioning of the
resource. This is the classic “free-rider problem:” improper
provisioning of a public good – the database – due to selfish
behavior. Other examples of public resources are community wireless data access, and file distribution and storage
in peer-to-peer networks.
Mechanisms for the production of public goods proceed
as follows. Users are asked to submit bids to the producer.
Based on the received bids the producer then decides, according to a pre-specified and globally known rule, the quantity of the public good to be produced and the contributions
to be made by each of the users. Groves and Loeb [1] proposed a generic model capturing the free-rider problem in
the production of a real-valued amount of a public good.
The mechanism they proposed for solving the problem was
one of the earliest instances of what later came to be known
as the general class of VCG mechanisms. This paper proposes alternative mechanism designs for the same resource
allocation problem as formulated in [1].
It is well known (see e.g. [2]) that VCG mechanisms are
the only ones that ensure efficient production as dominant
strategy outcomes in a wide variety of...
A New Mechanism for the Free-rider Problem
Sujay Sanghavi
Electrical and Computer Engineering and the
Coordinated Science Laboratory, UIUC
sanghavi@uiuc.edu
Bruce Hajek
Electrical and Computer Engineering and the
Coordinated Science Laboratory, UIUC
b-hajek@uiuc.edu
ABSTRACT
The free-rider problem arises in the provisioning of pub-
lic 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 in-
dividual contributions leading to inefficient levels of pro-
duction of the resource. Groves and Loeb formulated a clas-
sic 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 com-
munication constraints, or in decentralized settings, imple-
menting this mechanism places an unrealistic communica-
tion 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 author-
ity. 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 exten-
sion to multiple public goods with inter-related valuations
is also presented.
Categories and Subject Descriptors
G.1.6 [Optimization] Mechansim Design, Non-cooperative
Games
General Terms
Economics, Algorithms, Theory
1. INTRODUCTION
This paper proposes a new class of mechanisms for ad-
dressing the free-rider problem that arises in the production
of public goods. By public good we refer to a resource whose
0
This work was supported by grants NSF ANI 99-80544 and
DARPA F30602-00-2-0542.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
SIGCOMM’05 Workshops, August 22–26, 2005, Philadelphia, PA, USA.
Copyright 2005 ACM 1-59593-026-4/05/0008 ...
$5.00.
usage is non-exclusionary: it can be used simultaneously and
equally by all users. This is in contrast to a private good,
which has to be divided up among the users, each of whom
has exclusive access to its portion after the auction. Com-
mon examples of public goods in everyday life are television
/ radio broadcasts, weather reports and public works such
as libraries.
In proposing the mechanisms described in this paper we
are motivated by public goods in modern communication
and computation systems. Consider for example a large dis-
tributed database, containing information available to all
users, without exclusion. Each user contributes towards the
building / maintenance of this database, either in direct
monetary terms or through contributed storage resources.
Since the information in the database is assumed to be freely
available to all users, each user has an incentive to minimize
the amount of resources it contributes. However, if every
user acts according to these selfish considerations, the net
result could be a possibly severe under-provisioning of the
resource. This is the classic “free-rider problem:” improper
provisioning of a public good the database due to selfish
behavior. Other examples of public resources are commu-
nity wireless data access, and file distribution and storage
in peer-to-peer networks.
Mechanisms for the production of public goods proceed
as follows. Users are asked to submit bids to the producer.
Based on the received bids the producer then decides, ac-
cording to a pre-specified and globally known rule, the quan-
tity of the public good to be produced and the contributions
to be made by each of the users. Groves and Loeb [1] pro-
posed a generic model capturing the free-rider problem in
the production of a real-valued amount of a public good.
The mechanism they proposed for solving the problem was
one of the earliest instances of what later came to be known
as the general class of VCG mechanisms. This paper pro-
poses alternative mechanism designs for the same resource
allocation problem as formulated in [1].
It is well known (see e.g. [2]) that VCG mechanisms are
the only ones that ensure efficient production as dominant
strategy outcomes in a wide variety of resource allocation
problems. It is also increasingly apparent that in many
settings the implementation of VCG mechanisms places a
heavy communication and computational demand on the
auctioneer and agents, to the extent that they are deemed in-
feasible to implement. Another criticism of the VCG mecha-
nism is that it asks for detailed private information, namely
the entire set of user preferences, to be made public for the
purposes of resource allocation. Even when bids may be
122
free-rider - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
free-rider - Người đăng: tien06051992
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
6 Vietnamese
free-rider 9 10 698