File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/1.9781611973082.57
- Scopus: eid_2-s2.0-79955727359
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Bayesian incentive compatibility via fractional assignments
Title | Bayesian incentive compatibility via fractional assignments |
---|---|
Authors | |
Issue Date | 2011 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), San Francisco, CA, 23-25 January 2011. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, p. 720-733 How to Cite? |
Abstract | Very 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 Identifier | http://hdl.handle.net/10722/188491 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Bei, X | en_US |
dc.contributor.author | Huang, Z | en_US |
dc.date.accessioned | 2013-09-03T04:08:42Z | - |
dc.date.available | 2013-09-03T04:08:42Z | - |
dc.date.issued | 2011 | en_US |
dc.identifier.citation | Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), San Francisco, CA, 23-25 January 2011. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, p. 720-733 | en_US |
dc.identifier.uri | http://hdl.handle.net/10722/188491 | - |
dc.description.abstract | Very 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.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 | Bayesian incentive compatibility via fractional assignments | 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.9781611973082.57 | - |
dc.identifier.scopus | eid_2-s2.0-79955727359 | en_US |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-79955727359&selection=ref&src=s&origin=recordpage | en_US |
dc.identifier.spage | 720 | en_US |
dc.identifier.epage | 733 | en_US |
dc.identifier.scopusauthorid | Bei, X=35104347500 | en_US |
dc.identifier.scopusauthorid | Huang, Z=55494568500 | en_US |