Algorithms for Recognizing Economic Properties in Matrix Bid Combinatorial Auctions
Dries R. Goossens, Rudolf Müller, Frits C. R. Spieksma
INFORMS Journal on Computing · 2010 · Volume 22 · Issue 3
Abstract
A combinatorial auction is an auction where multiple items are for sale simultaneously to a set of buyers. Furthermore, buyers are allowed to place bids on subsets of the available items. This paper focuses on a combinatorial auction where a bidder can express his preferences by means of a so-called ordered matrix bid . Ordered matrix bids are a bidding language that allows a compact representation of a bidder's preferences and was developed by Day [Day, R. W. 2004. Expressing preferences with price-vector agents in combinatorial auctions. Ph.D. thesis, University of Maryland, College Park]. We give an overview of how a combinatorial auction with matrix bids works. We discuss the relevance of recognizing whether a given matrix bid has properties related to elements of economic theory such as free disposal, subadditivity, submodularity, and the gross substitutes property. We show that verifying whether a matrix bid has these properties can be done in polynomial time by solving one or more shortest-path problems. Finally, we investigate to what extent randomly generated matrix bids satisfy these properties.
Keywords
combinatorial auction, matrix bids, free disposal, subadditivity, submodularity, gross substitutes, expressiveness
Enable JavaScript for citation tools and additional paper interactions.