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

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.