@PhdThesis{mendoza09a,
  author =	 {Benito Mendoza Garcia},
  title =	 {Economic and Computationally Efficient Algorithms
                  for Bidding in a Distributed Combinatorial Auction},
  school =	 {University of South Carolina},
  year =	 2009,
  abstract =	 {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 myopicoptimal 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.},
  url = 	 {http://jmvidal.cse.sc.edu/library/mendoza09a.pdf}
}