Berlin 2005 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

SYBN: Biological and Social Networks

SYBN 3: Biologische und Soziale Netzwerke, Postersitzung

SYBN 3.31: Poster

Monday, March 7, 2005, 14:00–15:30, Poster TU E

Combinatorial auctions: A statistical physics approach — •Martin Weigt, Michele Leone, and Mauro Sellitto — Institute for Scientific Interchange, Viale S. Severo 65, I-10133 Torino, Italia

In combinatorial auctions, bidders are not only interested in bidding on single objects, but on combinations of goods. The auctioneer has to solve the problem of selecting a winning set of non-contradictory bids which maximizes his income, which is in general an NP-hard optimization problem. Using a mapping to a statistical-physics model on the network of conflicting interests between bidders, we can solve this problem analytical for the simplified case of random bidders, and we propose a message-passing algorithm to select a close-to-optimal winning set of bids also in single combinatorial auctions.