Monotone Branch-and-Bound Search for Restricted Combinatorial Auctions

DSpace/Manakin Repository

Monotone Branch-and-Bound Search for Restricted Combinatorial Auctions

Citable link to this page


Title: Monotone Branch-and-Bound Search for Restricted Combinatorial Auctions
Author: Lai, John Kwang; Parkes, David C.

Note: Order does not necessarily reflect citation order of authors.

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.
Full Text & Related Files:
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.
Published Version: doi:10.1145/2229012.2229067
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search