Show simple item record

dc.contributor.authorLai, John Kwang
dc.contributor.authorParkes, David C.
dc.date.accessioned2014-03-20T12:30:14Z
dc.date.issued2012
dc.identifier.citationLai, 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.isbn978-1-4503-1415-2en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:11956915
dc.description.abstractFaced 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.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherACM Pressen_US
dc.relation.isversionofdoi:10.1145/2229012.2229067en_US
dash.licenseOAP
dc.titleMonotone Branch-and-Bound Search for Restricted Combinatorial Auctionsen_US
dc.typeConference Paperen_US
dc.description.versionAccepted Manuscripten_US
dash.depositing.authorParkes, David C.
dc.date.available2014-03-20T12:30:14Z
dc.relation.bookProceedings of the 13th ACM Conference on Electronic Commerce (EC '12)en_US
dc.identifier.doi10.1145/2229012.2229067*
workflow.legacycommentspublisher's version has page numbersen_US
dash.contributor.affiliatedLai, John Kwang
dash.contributor.affiliatedParkes, David


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record