Algorithms for recognizing economic properties in matrix bid combinatorial auctions

Algorithms for recognizing economic properties in matrix bid combinatorial auctions

0.00 Avg rating0 Votes
Article ID: iaor20105631
Volume: 22
Issue: 3
Start Page Number: 339
End Page Number: 352
Publication Date: Jun 2010
Journal: INFORMS Journal on Computing
Authors: , ,
Keywords: auctions, combinatorial auction
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 (2004). 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.

Reviews

Required fields are marked *. Your email address will not be published.