dc.contributor.author | Lai, John Kwang | |
dc.contributor.author | Parkes, David C. | |
dc.date.accessioned | 2014-03-20T12:30:14Z | |
dc.date.issued | 2012 | |
dc.identifier.citation | Lai, John, and David Parkes. 2012. Monotone branch-and-bound search for restricted combinatorial auctions. Proceedings of the 13th ACM Conference on Electronic Commerce (EC ’12), June 4-8, 2012, Valencia, Spain, 705-722. New York, NY: ACM Press. | en_US |
dc.identifier.isbn | 978-1-4503-1415-2 | en_US |
dc.identifier.uri | http://nrs.harvard.edu/urn-3:HUL.InstRepos:11956915 | |
dc.description.abstract | Faced with an intractable optimization problem, a common approach to computational mechanism design seeks a polynomial time approximation algorithm with an approximation guarantee. Rather than adopt this worst-case viewpoint, we introduce a new paradigm that seeks to obtain good performance on typical instances through a modification to the branch-and-bound search paradigm. Incentive compatibility in single-dimensional domains requires that an outcome improves monotonically for an agent as the agent's reported value increases. We obtain a monotone search algorithm by coupling an explicit sensitivity analysis on the decisions made during search with a correction to the outcome to ensure monotonicity. Extensive computational experiments on single-minded combinatorial auctions show better welfare performance than that available from existing approximation algorithms. | en_US |
dc.description.sponsorship | Engineering and Applied Sciences | en_US |
dc.language.iso | en_US | en_US |
dc.publisher | ACM Press | en_US |
dc.relation.isversionof | doi:10.1145/2229012.2229067 | en_US |
dash.license | OAP | |
dc.title | Monotone Branch-and-Bound Search for Restricted Combinatorial Auctions | en_US |
dc.type | Conference Paper | en_US |
dc.description.version | Accepted Manuscript | en_US |
dash.depositing.author | Parkes, David C. | |
dc.date.available | 2014-03-20T12:30:14Z | |
dc.relation.book | Proceedings of the 13th ACM Conference on Electronic Commerce (EC '12) | en_US |
dc.identifier.doi | 10.1145/2229012.2229067 | * |
workflow.legacycomments | publisher's version has page numbers | en_US |
dash.contributor.affiliated | Lai, John Kwang | |
dash.contributor.affiliated | Parkes, David | |