Economic and computationally efficient algorithms for bidding in a distributed combinatorial auction

Combinatorial auctions (CAs)---auctions that allow bids for bundles of items---have generated significant interest as automated mechanisms for buying and selling bundles of scarce resources, since they provide a great way of allocating multiple distinguishable items amongst bidders whose perceived valuations for combinations of those items differ. However, CAs require the establishment of a central auctioneer who receives the bids and carries out all the computation to find the optimal allocation of items to bidders--an NP-complete problem.;The motivation for this dissertation was the vision of distributed combinatorial auctions as incentive compatible peer-to-peer mechanisms to solve the allocation problem, where the bidders are the ones who carry out the needed computation to solve the problem; consequently, there is no need for a central auctioneer. The core contributions of this dissertation consist on a set of bidding algorithms for distributed combinatorial auctions. I have developed two type of bidding algorithms: myopic-optimal, which optimally find the set of bids that maximize the bidders utility at a certain time with no consideration about the future; and heuristic-approximate, which are not guaranteed to find the utility-maximizing set of bids but require only a small fraction of the others' computational time. These algorithms have shown that it is feasible to implement distributed combinatorial auctions.;Experimental results indicate that the approximate algorithms are a realistic tool for the development of large-scale distributed combinatorial auctions. Furthermore, the outcome of a game theoretical analysis indicates that they are dominant strategies over the myopic-optimal ones, since in addition to be faster, they provide higher bidder's utility (although the seller's revenue is not optimal). Empirical analyzes over different problem domains show that these algorithms find highly (allocative) efficient solutions. This makes them suitable to solve, effectively and distributively, complex coordination problems such as multirobot task allocation, automated negotiation in B2B electronic commerce, automated supply chains, and routing mechanisms.