Paper Info
Title
Algorithms for Recognizing Economic Properties in Matrix Bid Combinatorial Auctions
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.
Year
DOI
Venue
2010
10.1287/ijoc.1090.0336
INFORMS Journal on Computing
Keywords
Field
DocType
matrix bid combinatorial auctions,available item,expressing preference,matrix bids work,compact representation,bidding language,combinatorial auction,ordered matrix bid,matrix bid,ph.d. thesis,college park,recognizing economic properties,expressiveness,subadditivity
English auction,Bid shading,Mathematical optimization,Mathematical economics,Vickrey auction,Unique bid auction,Combinatorial auction,Algorithm,Generalized second-price auction,Vickrey–Clarke–Groves auction,Proxy bid,Mathematics
Journal
Volume
Issue
ISSN
22
3
1091-9856
Citations 
PageRank 
References 
3
0.45
21
Authors
3
Name
Order
Citations
PageRank
Dries R. Goossens112915.88
Rudolf Müller2516.14
Frits C. R. Spieksma359158.84