File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: The sample complexity of auctions with side information

TitleThe sample complexity of auctions with side information
Authors
KeywordsMyerson's auction
Sample complexity
Issue Date2016
PublisherACM Press.
Citation
The 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), Cambridge, MA., 19-21 June 2016. In Conference Proceedings, 2016, p. 426-439 How to Cite?
AbstractTraditionally, the Bayesian optimal auction design problem has been considered either when the bidder values are i.i.d, or when each bidder is individually identifiable via her value distribution. The latter is a reasonable approach when the bidders can be classified into a few categories, but there are many instances where the classification of bidders is a continuum. For example, the classification of the bidders may be based on their annual income, their propensity to buy an item based on past behavior, or in the case of ad auctions, the click through rate of their ads. We introduce an alternate model that captures this aspect, where bidders are a priori identical, but can be distinguished based (only) on some side information the auctioneer obtains at the time of the auction. We extend the sample complexity approach of Dhangwatnotai et al. and Cole and Roughgarden to this model and obtain almost matching upper and lower bounds. As an aside, we obtain a revenue monotonicity lemma which may be of independent interest. We also show how to use Empirical Risk Minimization techniques to improve the sample complexity bound of Cole and Roughgarden for the nonidentical but independent value distribution case.
Persistent Identifierhttp://hdl.handle.net/10722/232174
ISBN

 

DC FieldValueLanguage
dc.contributor.authorDevanur, NR-
dc.contributor.authorHuang, Z-
dc.contributor.authorPsomas, CA-
dc.date.accessioned2016-09-20T05:28:14Z-
dc.date.available2016-09-20T05:28:14Z-
dc.date.issued2016-
dc.identifier.citationThe 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), Cambridge, MA., 19-21 June 2016. In Conference Proceedings, 2016, p. 426-439-
dc.identifier.isbn978-1-4503-4132-5-
dc.identifier.urihttp://hdl.handle.net/10722/232174-
dc.description.abstractTraditionally, the Bayesian optimal auction design problem has been considered either when the bidder values are i.i.d, or when each bidder is individually identifiable via her value distribution. The latter is a reasonable approach when the bidders can be classified into a few categories, but there are many instances where the classification of bidders is a continuum. For example, the classification of the bidders may be based on their annual income, their propensity to buy an item based on past behavior, or in the case of ad auctions, the click through rate of their ads. We introduce an alternate model that captures this aspect, where bidders are a priori identical, but can be distinguished based (only) on some side information the auctioneer obtains at the time of the auction. We extend the sample complexity approach of Dhangwatnotai et al. and Cole and Roughgarden to this model and obtain almost matching upper and lower bounds. As an aside, we obtain a revenue monotonicity lemma which may be of independent interest. We also show how to use Empirical Risk Minimization techniques to improve the sample complexity bound of Cole and Roughgarden for the nonidentical but independent value distribution case.-
dc.languageeng-
dc.publisherACM Press.-
dc.relation.ispartofProceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016-
dc.rightsAuthor holds the copyright-
dc.subjectMyerson's auction-
dc.subjectSample complexity-
dc.titleThe sample complexity of auctions with side information-
dc.typeConference_Paper-
dc.identifier.emailHuang, Z: zhiyi@cs.hku.hk-
dc.identifier.authorityHuang, Z=rp01804-
dc.description.naturelink_to_OA_fulltext-
dc.identifier.doi10.1145/2897518.2897553-
dc.identifier.scopuseid_2-s2.0-84979226427-
dc.identifier.hkuros263133-
dc.identifier.spage426-
dc.identifier.epage439-
dc.publisher.placeUnited States-
dc.customcontrol.immutablesml 161114-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats