Publication: Monotone Branch-and-Bound Search for Restricted Combinatorial Auctions
Open/View Files
Date
2012
Authors
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
ACM Press
The Harvard community has made this article openly available. Please share how this access benefits you.
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.
Research Data
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.
Description
Other Available Sources
Keywords
Terms of Use
This article is made available under the terms and conditions applicable to Open Access Policy Articles (OAP), as set forth at Terms of Service