Optimization in electronic markets: examples in combinatorial auctions

Stan van Hoesel () and Rudolf Müller
Additional contact information
Stan van Hoesel: University of Maastricht

Netnomics, 2001, vol. 3, issue 1, 23-33

Abstract: Abstract Combinatorial auctions provide an important tool for mechanism design in multi-agent systems. When implemented they require to solve combinatorial optimization problems such as set packing and partitioning problems. We present in this paper an analysis of the complexity of the problem to assign bids to bidders in combinatorial auctions. We show that the case of identical assets can be solved in polynomial time. The case of non-identical assets is in its general version NP-hard. Extra structure, like a complete ordering of assets, or mild side conditions make the problem solvable. Finally, we present an algorithm to solve small and medium sized instances in a limited time using standard software.

Keywords: multi-agent systems; combinatorial auctions; combinatorial optimization; set packing problem; dynamic (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009940607600 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kap:netnom:v:3:y:2001:i:1:d:10.1023_a:1009940607600

Ordering information: This journal article can be ordered from
http://www.springer. ... ry/journal/11066/PS2

DOI: 10.1023/A:1009940607600

Access Statistics for this article

Netnomics is currently edited by Stefan Voß

More articles in Netnomics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().