File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Simple and nearly optimal multi-item auctions

TitleSimple and nearly optimal multi-item auctions
Authors
Issue Date2013
Citation
Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2013, p. 564-577 How to Cite?
AbstractWe provide a Polynomial Time Approximation Scheme (PTAS) for the Bayesian optimal multi-item multi-bidder auction problem under two conditions. First, bidders are independent, have additive valuations and are from the same population. Second, every bidder's value distributions of items are independent but not necessarily identical monotone hazard rate (MHR) distributions. For non-i.i.d. bidders, we also provide a PTAS when the number of bidders is small. Prior to our work, even for a single bidder, only constant factor approximations are known. Another appealing feature of our mechanism is the simple allocation rule. Indeed, the mechanism we use is either the second-price auction with reserve price on every item individually, or VCG allocation with a few outlying items that requires additional treatments. It is surprising that such simple allocation rules suffice to obtain nearly optimal revenue. Copyright © SIAM.
Persistent Identifierhttp://hdl.handle.net/10722/188506
References

 

DC FieldValueLanguage
dc.contributor.authorCai, Yen_US
dc.contributor.authorHuang, Zen_US
dc.date.accessioned2013-09-03T04:08:46Z-
dc.date.available2013-09-03T04:08:46Z-
dc.date.issued2013en_US
dc.identifier.citationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2013, p. 564-577en_US
dc.identifier.urihttp://hdl.handle.net/10722/188506-
dc.description.abstractWe provide a Polynomial Time Approximation Scheme (PTAS) for the Bayesian optimal multi-item multi-bidder auction problem under two conditions. First, bidders are independent, have additive valuations and are from the same population. Second, every bidder's value distributions of items are independent but not necessarily identical monotone hazard rate (MHR) distributions. For non-i.i.d. bidders, we also provide a PTAS when the number of bidders is small. Prior to our work, even for a single bidder, only constant factor approximations are known. Another appealing feature of our mechanism is the simple allocation rule. Indeed, the mechanism we use is either the second-price auction with reserve price on every item individually, or VCG allocation with a few outlying items that requires additional treatments. It is surprising that such simple allocation rules suffice to obtain nearly optimal revenue. Copyright © SIAM.en_US
dc.languageengen_US
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_US
dc.titleSimple and nearly optimal multi-item auctionsen_US
dc.typeConference_Paperen_US
dc.identifier.emailHuang, Z: hzhiyi@cis.upenn.eduen_US
dc.identifier.authorityHuang, Z=rp01804en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-84876069858en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-84876069858&selection=ref&src=s&origin=recordpageen_US
dc.identifier.spage564en_US
dc.identifier.epage577en_US
dc.identifier.scopusauthoridCai, Y=35110971200en_US
dc.identifier.scopusauthoridHuang, Z=55494568500en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats