File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Bayesian incentive compatibility via fractional assignments

TitleBayesian incentive compatibility via fractional assignments
Authors
Issue Date2011
Citation
Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2011, p. 720-733 How to Cite?
AbstractVery recently, Hartline and Lucier [14] studied single- parameter mechanism design problems in the Bayesian setting. They proposed a black-box reduction that converted Bayesian approximation algorithms into Bayesian-Incentive- Compatible (BIC) mechanisms while preserving social welfare. It remains a major open question if one can find similar reduction in the more important multi-parameter setting. In this paper, we give positive answer to this question when the prior distribution has finite and small support. We propose a black-box reduction for designing BIC multi-parameter mechanisms. The reduction converts any algorithm into an ε-BIC mechanism with only marginal loss in social welfare. As a result, for combinatorial auctions with sub-additive agents we get an ε-BIC mechanism that achieves constant approximation.
Persistent Identifierhttp://hdl.handle.net/10722/188491
References

 

DC FieldValueLanguage
dc.contributor.authorBei, Xen_US
dc.contributor.authorHuang, Zen_US
dc.date.accessioned2013-09-03T04:08:42Z-
dc.date.available2013-09-03T04:08:42Z-
dc.date.issued2011en_US
dc.identifier.citationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 2011, p. 720-733en_US
dc.identifier.urihttp://hdl.handle.net/10722/188491-
dc.description.abstractVery recently, Hartline and Lucier [14] studied single- parameter mechanism design problems in the Bayesian setting. They proposed a black-box reduction that converted Bayesian approximation algorithms into Bayesian-Incentive- Compatible (BIC) mechanisms while preserving social welfare. It remains a major open question if one can find similar reduction in the more important multi-parameter setting. In this paper, we give positive answer to this question when the prior distribution has finite and small support. We propose a black-box reduction for designing BIC multi-parameter mechanisms. The reduction converts any algorithm into an ε-BIC mechanism with only marginal loss in social welfare. As a result, for combinatorial auctions with sub-additive agents we get an ε-BIC mechanism that achieves constant approximation.en_US
dc.languageengen_US
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_US
dc.titleBayesian incentive compatibility via fractional assignmentsen_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-79955727359en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-79955727359&selection=ref&src=s&origin=recordpageen_US
dc.identifier.spage720en_US
dc.identifier.epage733en_US
dc.identifier.scopusauthoridBei, X=35104347500en_US
dc.identifier.scopusauthoridHuang, Z=55494568500en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats