Jump to ContentJump to Main Navigation
Combinatorial Auctions$
Users without a subscription are not able to see the full content.
Combinatorial Auctions

Peter Cramton, Yoav Shoham, and Richard Steinberg

Print publication date: 2005

Print ISBN-13: 9780262033428

Published to MIT Press Scholarship Online: August 2013

DOI: 10.7551/mitpress/9780262033428.001.0001

ContentsFRONT MATTER
Show Summary Details
Page of

PRINTED FROM MIT PRESS SCHOLARSHIP ONLINE (www.mitpress.universitypressscholarship.com). (c) Copyright The MIT Press, 2022. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in MITSO for personal use.date: 07 July 2022

Tractable Cases of the Winner Determination Problem

Tractable Cases of the Winner Determination Problem

Chapter:
(p.319) 13 Tractable Cases of the Winner Determination Problem
Source:
Combinatorial Auctions
Author(s):

Rudolf Müller

Publisher:
The MIT Press
DOI:10.7551/mitpress/9780262033428.003.0014

This chapter offers information on several approaches used for making the winner determination problem (WDP) solvable by putting restrictions on the bid prices. It begins with integer linear programming formulations of WDP in order to get a tractable case for the winner determination problem. The chapter then focuses on another approach that is used for making WDP a combinatorial optimization problem by using the intersection graph of bids. As reported, the latter approach leads to faster algorithms in comparison with the linear programming approach. The chapter further explains how other models such as restricting bid sets or bid values can become suitable methods for showing tractability. Limitations that can hamper the performance of these approaches including economic inefficiencies, incentive problems, and exposure problems.

Keywords:   winner determination problem, bid prices, integer linear programming, algorithms, economic inefficiencies, exposure problems

MIT Press Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs, and if you can't find the answer there, please contact us.