Ascending Combinatorial Auctions with Allocation Constraints: On Game Theoretical and Computational Properties of Generic Pricing Rules

Ioannis Petrakis (), Georg Ziegler () and Martin Bichler ()
Additional contact information
Ioannis Petrakis: Decision Sciences and Systems, Department of Informatics, Technische Universität München, 80333 Munich, Germany
Georg Ziegler: Decision Sciences and Systems, Department of Informatics, Technische Universität München, 80333 Munich, Germany
Martin Bichler: Decision Sciences and Systems, Department of Informatics, Technische Universität München, 80333 Munich, Germany

Information Systems Research, 2013, vol. 24, issue 3, 768-786

Abstract: Combinatorial auctions are used in a variety of application domains, such as transportation or industrial procurement, using a variety of bidding languages and different allocation constraints. This flexibility in the bidding languages and the allocation constraints is essential in these domains but has not been considered in the theoretical literature so far. In this paper, we analyze different pricing rules for ascending combinatorial auctions that allow for such flexibility: winning levels and deadness levels. We determine the computational complexity of these pricing rules and show that deadness levels actually satisfy an ex post equilibrium, whereas winning levels do not allow for a strong game theoretical solution concept. We investigate the relationship of deadness levels and the simple price update rules used in efficient ascending combinatorial auction formats. We show that ascending combinatorial auctions with deadness level pricing rules maintain a strong game theoretical solution concept and reduce the number of bids and rounds required at the expense of higher computational effort. The calculation of exact deadness levels is a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$\Pi_2^P$\end{document} -complete problem. Nevertheless, numerical experiments show that for mid-sized auctions this is a feasible approach. The paper provides a foundation for allocation constraints in combinatorial auctions and a theoretical framework for recent Information Systems contributions in this field.

Keywords: electronic markets and auctions; economics of IS; electronic commerce; decision support systems (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/isre.1120.0452 (application/pdf)

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:inm:orisre:v:24:y:2013:i:3:p:768-786

Access Statistics for this article

More articles in Information Systems Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().