Approximate mechanisms and algorithms for combinatorial auctions

Combinatorial auctions are auction formats that allow agents to submit single bids for a set of distinct items and as such economic efficiency may be enhanced. Mechanisms for combinatorial auctions may be the basis for distributed resource allocation of multiple items with many applications ranging from transportation procurement to telecommunications resource allocation. However, with M distinct items there are 2M −1 − 1 possible bundles (set of items) and thus a bidder must face the task of possibly evaluating an exponential number of bundles. In addition, the auctioneer faces a non-trivial computational task in winner determination and must solve a NP-hard problem weighted set packing. In the first part of the thesis I propose an extension of an economically efficient iterative mechanism for combinatorial auctions to enable endogenous bid determination. Endogenous bidding entails dynamically discovering new bundles through item prices so that explicit evaluation of bundles can be avoided. A pricing linear program is developed that is unique in satisfying a normative set of properties for item prices. The main theoretical result states that endogenous bidding is more efficient than the equivalent problem restricted to a set of a priori determined set of bundles under reasonable competitive environments. In the second part of the thesis I propose an approximation algorithm for the winner determination problem. Real world instances of combinatorial auctions may involve thousands of items and thus an inordinate number of possible bundles. Computing optimal winner determination solutions may require too much time. In real time settings e.g. the Internet time may be an important element. Thus, approximation strategies become important. I present a fast non-exact method that employs a primal-dual approximation (greedy method) for a first phase and then attempts to improve on the greedy solution by using dual information. Novel ex ante and ex post optimality bounds are derived that are non-trivial and that may offer better assessments of optimality compared to those from duality gaps or best known ex ante bounds. Empirical results indicate that the approximation strategy is effective in producing near optimal solutions in reasonable time