Access Restriction

Author Christodoulou, George ♦ Kovcs, Annamria ♦ Schapira, Michael
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Mechanism design ♦ Combinatorial auctions ♦ Game theory ♦ Simultaneous item-bidding auctions
Abstract We study the following simple Bayesian auction setting: $\textit{m}$ items are sold to $\textit{n}$ selfish bidders in $\textit{m}$ independent second-price auctions. Each bidder has a $\textit{private}$ valuation function that specifies his or her complex preferences over $\textit{all}$ subsets of items. Bidders only have $\textit{beliefs}$ about the valuation functions of the other bidders, in the form of probability distributions. The objective is to allocate the items to the bidders in a way that provides a good approximation to the optimal social welfare value. We show that if bidders have submodular or, more generally, fractionally subadditive (aka XOS) valuation functions, every Bayes-Nash equilibrium of the resulting game provides a 2-approximation to the optimal social welfare. Moreover, we show that in the full-information game, a pure Nash always exists and can be found in time that is polynomial in both $\textit{m}$ and $\textit{n}.$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-04-07
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 2
Page Count 19
Starting Page 1
Ending Page 19

Open content in new tab

   Open content in new tab
Source: ACM Digital Library