Integer programming for combinatorial auction winner determination

被引：127

作者：

Andersson, A ^{[1
]}

Tenhunen, M ^{[1
]}

Ygge, F ^{[1
]}

机构：

[1] Uppsala Univ, Dept Comp Sci, SE-75105 Uppsala, Sweden

来源：

FOURTH INTERNATIONAL CONFERENCE ON MULTIAGENT SYSTEMS, PROCEEDINGS | 2000年

关键词：

D O I：

10.1109/ICMAS.2000.858429

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Combinatorial auctions are important as they enable bidders to place bids on combinations of items; compared to other auction mechanisms, they often increase the efficiency of the auction, while keeping risks for bidders low. However the determination of an optimal winner combination in combinatorial auctions is a complex computational problem. In this paper we (i) compare recent algorithms for winner determination to traditional algorithms, (ii) present and benchmark a mixed integer programming approach to the problem, which enables very general auctions to be treated efficiently by standard integer programming algorithms (and hereby also by commercially available software), and (iii) discuss the impact of the probability distributions chosen for benchmarking.

引用

页码：39 / 46

页数：8

共 10 条

[1] SET PARTITIONING - SURVEY [J].

BALAS, E ;

PADBERG, MW .

SIAM REVIEW, 1976, 18 (04) :710-760

[2]

Fujishima Y, 1999, IJCAI-99: PROCEEDINGS OF THE SIXTEENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOLS 1 & 2, P548

[3] SET-PARTITIONING PROBLEM - SET COVERING WITH EQUALITY CONSTRAINTS [J].

GARFINKEL, RS ;

NEMHAUSER, GL .

OPERATIONS RESEARCH, 1969, 17 (05) :848-+

[4]

NISAN N, 1999, 1999 NWU MICR WORKSH

[5]

PARKES DC, 1999, P 1 ACM C EL COMM, P148

[6] A COMBINATORIAL AUCTION MECHANISM FOR AIRPORT TIME SLOT ALLOCATION [J].

RASSENTI, SJ ;

SMITH, VL ;

BULFIN, RL .

BELL JOURNAL OF ECONOMICS, 1982, 13 (02) :402-417

[7] Computationally manageable combinational auctions [J].

Rothkopf, MH ;

Pekec, A ;

Harstad, RM .

MANAGEMENT SCIENCE, 1998, 44 (08) :1131-1147

[8]

Salkin H.M., 1975, Integer programming

[9]

Sandholm T, 1999, IJCAI-99: PROCEEDINGS OF THE SIXTEENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOLS 1 & 2, P542

[10]

[No title captured]

← 1 →