File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/1.9781611973105.41
- Scopus: eid_2-s2.0-84876069858
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Simple and nearly optimal multi-item auctions
Title | Simple and nearly optimal multi-item auctions |
---|---|
Authors | |
Issue Date | 2013 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), New Orleans, LA, 6-8 January 2013. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2013, p. 564-577 How to Cite? |
Abstract | We 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 Identifier | http://hdl.handle.net/10722/188506 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cai, Y | en_US |
dc.contributor.author | Huang, Z | en_US |
dc.date.accessioned | 2013-09-03T04:08:46Z | - |
dc.date.available | 2013-09-03T04:08:46Z | - |
dc.date.issued | 2013 | en_US |
dc.identifier.citation | 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), New Orleans, LA, 6-8 January 2013. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2013, p. 564-577 | en_US |
dc.identifier.uri | http://hdl.handle.net/10722/188506 | - |
dc.description.abstract | We 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.language | eng | en_US |
dc.publisher | Society for Industrial and Applied Mathematics. | - |
dc.relation.ispartof | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms | en_US |
dc.title | Simple and nearly optimal multi-item auctions | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.email | Huang, Z: hzhiyi@cis.upenn.edu | en_US |
dc.identifier.authority | Huang, Z=rp01804 | en_US |
dc.description.nature | link_to_OA_fulltext | en_US |
dc.identifier.doi | 10.1137/1.9781611973105.41 | - |
dc.identifier.scopus | eid_2-s2.0-84876069858 | en_US |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-84876069858&selection=ref&src=s&origin=recordpage | en_US |
dc.identifier.spage | 564 | en_US |
dc.identifier.epage | 577 | en_US |
dc.identifier.scopusauthorid | Cai, Y=35110971200 | en_US |
dc.identifier.scopusauthorid | Huang, Z=55494568500 | en_US |