Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Solution to Exchanges 7.1 puzzle: combinatorial auction winner determination

Solution to Exchanges 7.1 puzzle: combinatorial auction winner determination Solution to Exchanges 7.1 Puzzle: Combinatorial Auction Winner Determination JOHANNA Y. HE Tech. Univ. Munich This is a solution to the editor’s puzzle from Issue 7.1 of SIGecom Exchanges. The puzzle is about solving an instance of the winner determination problem and providing a proof of optimality. The full puzzle [Conitzer] can be found online at http://www.sigecom.org/exchanges/volume 7/1/puzzle.pdf. The puzzle asks us to determine the optimal allocation for a combinatorial auction with 5 items, A, B, C, D, E, and 12 (single-minded) bids. Let j = 1, . . . , 12 stand for the submitted bids, and xj = 1, 0, if bid j is accepted if bid j is rejected j = 1, . . . , 12 Then the standard winner determination problem can be written as the integer linear program: max 5x1 +10x2 +24x3 +51x4 +13x5 +27x6 +43x7 +29x8 +25x9 +48x10 +14x11 + 23x12 x1 + x2 + x3 + x4 ¤1 x1 + x5 + x6 + x7 + x8 ¤1 (1) x2 + x3 + x4 + x5 + x6 + x9 + x10 ¤1 x3 + x4 + x6 + x7 + x9 + x10 + x11 ¤1 x4 + x7 http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM SIGecom Exchanges Association for Computing Machinery

Solution to Exchanges 7.1 puzzle: combinatorial auction winner determination

He, Johanna Y.
ACM SIGecom Exchanges , Volume 9 (1) – Jun 1, 2010
Download PDF
3 pages

Loading next page...
 
/lp/association-for-computing-machinery/solution-to-exchanges-7-1-puzzle-combinatorial-auction-winner-uCs8v1otNY
Publisher
Association for Computing Machinery
Copyright
Copyright © 2010 by ACM Inc.
ISSN
1551-9031
DOI
10.1145/1980534.1980544
Publisher site
See Article on Publisher Site

Abstract

Solution to Exchanges 7.1 Puzzle: Combinatorial Auction Winner Determination JOHANNA Y. HE Tech. Univ. Munich This is a solution to the editor’s puzzle from Issue 7.1 of SIGecom Exchanges. The puzzle is about solving an instance of the winner determination problem and providing a proof of optimality. The full puzzle [Conitzer] can be found online at http://www.sigecom.org/exchanges/volume 7/1/puzzle.pdf. The puzzle asks us to determine the optimal allocation for a combinatorial auction with 5 items, A, B, C, D, E, and 12 (single-minded) bids. Let j = 1, . . . , 12 stand for the submitted bids, and xj = 1, 0, if bid j is accepted if bid j is rejected j = 1, . . . , 12 Then the standard winner determination problem can be written as the integer linear program: max 5x1 +10x2 +24x3 +51x4 +13x5 +27x6 +43x7 +29x8 +25x9 +48x10 +14x11 + 23x12 x1 + x2 + x3 + x4 ¤1 x1 + x5 + x6 + x7 + x8 ¤1 (1) x2 + x3 + x4 + x5 + x6 + x9 + x10 ¤1 x3 + x4 + x6 + x7 + x9 + x10 + x11 ¤1 x4 + x7

Journal

ACM SIGecom Exchanges – Association for Computing Machinery

Published: Jun 1, 2010

There are no references for this article.