The Winner Determination Problem

Daniel J. Lehmann · Rudolf Müller · Tüomas Sandholm

162 citations0/0 files storedThe MIT Press eBooks

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Auction Theory and Applications Complexity and Algorithms in Graphs Game Theory and Voting Systems

Abstract

This chapter defines and formulates a combinatorial optimization problem, called the winner determination problem, and examines its complexity properties. A range of alternative mathematical programming models including integer linear programming, weighted stable set in graphs, knapsack, and matching that covers variants of the problem related to particular bidding languages is also discussed. The chapter further highlights inapproximability results, and reviews the approximation algorithm, which is a polynomial time algorithm. It concludes that the problem, which is represented as an integer program, is NP-complete and can be tackled by applying three fundamentally different approaches, which it discusses.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 162 citations exist upstream.

References

2001Algorithmic Mechanism Design 1998Computationally Manageable Combinational Auctions 2002Truth revelation in approximately efficient combinatorial auctions 2005Combinatorial auctions with decreasing marginal utilities 2002Integer programming for combinatorial auction winner determination 2000Solving Combinatorial Auctions Using Stochastic Local Search 2002Winner determination in combinatorial auction generalizations 2003Incentive compatible multi unit combinatorial auctions

Cited by

2005Auction design with costly preference elicitation 2009A stochastic programming winner determination model for truckload procurement under shipment uncertainty 2008A Computational Analysis of Linear Price Iterative Combinatorial Auction Formats 2006Changing the Game in Strategic Sourcing at Procter & Gamble: Expressive Competition Enabled by Optimization 2008Preference Handling in Combinatorial Domains: From AI to Social Choice 2015

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.