Algorithm for optimal winner determination in combinatorial auctions

DOI10.1016/S0004-3702(01)00159-XzbMath0984.68039MaRDI QIDQ5958538

Tuomas W. Sandholm

Publication date: 3 March 2002

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

multiagent systemsauctioncombinatorial auctiondidding with synergiesmulti-item auctionmulti-object auctionwinner determination

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (63)

Emerging multiple issue e-auctions ⋮ Co-evolutionary Agents in Combinatorial Sealed-bid Auctions for Spectrum Licenses Markets ⋮ Constrained multi-object auctions and \(b\)-matching ⋮ Computing leximin-optimal solutions in constraint networks ⋮ Fair imposition ⋮ An options-based solution to the sequential auction problem ⋮ An abstraction-refinement methodology for reasoning about network games ⋮ An effective discrete dynamic convexized method for solving the winner determination problem ⋮ Look-ahead strategies for dynamic pickup and delivery problems ⋮ Optimal bidding in auctions from a game theory perspective ⋮ An interactive approach for bi-attribute multi-item auctions ⋮ Strong activity rules for iterative combinatorial auctions ⋮ Influence of non-price and environmental sustainability factors on truckload procurement process ⋮ Comparing multiagent systems research in combinatorial auctions and voting ⋮ Computing optimal outcomes under an expressive representation of settings with externalities ⋮ Coalition structure generation: a survey ⋮ A hybrid exact algorithm for complete set partitioning ⋮ Winner determination in geometrical combinatorial auctions ⋮ Information-theoretic approaches to branching in search ⋮ A taxonomy of exact methods for partial Max-SAT ⋮ Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs ⋮ Expressive markets for donating to charities ⋮ Truthful randomized mechanisms for combinatorial auctions ⋮ The complexity of deciding reachability properties of distributed negotiation schemes ⋮ Exact methods for combinatorial auctions. (Abstract of Thesis) ⋮ The Complexity Landscape of Outcome Determination in Judgment Aggregation ⋮ Limitations of VCG-based mechanisms ⋮ Inapproximability results for combinatorial auctions with submodular utility functions ⋮ Enabling assisted strategic negotiations in actual-world procurement scenarios ⋮ Trading grid services - a multi-attribute combinatorial approach ⋮ Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions ⋮ A model and heuristic algorithms for multi-unit nondiscriminatory combinatorial auction ⋮ PUSH: A generalized operator for the maximum vertex weight clique problem ⋮ Exact algorithms for the matrix bid auction ⋮ Combinatorial auctions ⋮ The clock proxy auction for allocating radio spectrum licenses ⋮ Equilibria of Greedy Combinatorial Auctions ⋮ Data dependent worst case bounds for weighted set packing ⋮ Permutation betting markets: singleton betting with extra information ⋮ Heuristics for a bidding problem ⋮ Multiagent resource allocation in \(k\)-additive domains: preference representation and complexity ⋮ Computer science and decision theory ⋮ Multiple unit auctions with economies and diseconomies of scale ⋮ Side constraints and non-price attributes in markets ⋮ Automated Design of Revenue-Maximizing Combinatorial Auctions ⋮ An information-theoretic framework for the lossy compression of link streams ⋮ Algorithmic mechanism design with investment ⋮ A fast approximation algorithm for solving the complete set packing problem ⋮ Collective decision making ⋮ On the Approximability of Combinatorial Exchange Problems ⋮ Truthful approximation mechanisms for restricted combinatorial auctions ⋮ Representing Utility Functions via Weighted Goals ⋮ A desired load distribution model for scheduling of unrelated parallel machines ⋮ Algorithms as Mechanisms: The Price of Anarchy of Relax and Round ⋮ Modeling the Pre Auction Stage The Truckload Case ⋮ Combinatorial auctions for electronic business ⋮ Metaheuristic Approaches for the Winner Determination Problem in Combinatorial Auction ⋮ Iterative Dutch combinatorial auctions ⋮ BOB: Improved winner determination in combinatorial auctions and generalizations ⋮ Average-case analysis of best-first search in two representative directed acyclic graphs ⋮ Distributed algorithms for matching in hypergraphs ⋮ Solving Multi-Mode Resource-Constrained Multi-Project Scheduling Problem with Combinatorial Auction Mechanisms ⋮ Fast Core Pricing for Rich Advertising Auctions

Uses Software

• CABOB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient bounds for the stable set, vertex cover and set packing problems
• Depth-first iterative-deepening: An optimal admissible tree search
• Leveled commitment contracts with myopic and strategic agents
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Coalition structure generation with worst case guarantees
• Computationally Manageable Combinational Auctions
• A Combinatorial Auction with Multiple Winners for Universal Service
• An algorithm for finding a maximum weighted independent set in an arbitrary graph
• Multi-Object Auctions: Sequential vs. Simultaneous Sales
• An algorithm for the maximum internally stable set in a weighted graph
• Incentives in Teams
• Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
• The Set-Partitioning Problem: Set Covering with Equality Constraints
• Leveled commitment contracts and strategic breach

This page was built for publication: Algorithm for optimal winner determination in combinatorial auctions