A price trajectory algorithm for solving iterative auction problems

Many types of auctions are discussed in the literature such as single item auctions, sequential auctions, and combinatorial auctions. Proxy bidding has proven useful in solving iterative auction problems in many real-world auction formats. In this dissertation, I propose a new type of iterative auction called the Simple Combinatorial Proxy Auction. A popular method for solving the iterative proxy auction problems is simulating the incremental bidding decisions of the agents. However, this approach has some disadvantages. In this dissertation, I present a new approach called the Price Trajectory Algorithm to solve iterative auction problems. This approach computes the agents' allocation of their attention across the bundles only at points---the points at which agents change their behavior. The proposed algorithm tracks the behavior of agents and the competitive allocations of items in order to establish a connection between them. With the allocation of agents' attention, one can compute the slopes of price curves to get the bundle prices and speed up the computation by jumping from one inflection point to the next. The price trajectory algorithm can be applied to the Ascending Package Auction, the Ascending k-Bundle Auction, and the Simple Combinatorial Proxy Auction. The price trajectory algorithm has several advantages over other alternatives: (1) The price trajectory algorithm computes exact solutions. (2) The solutions are independent of the bid increment or tie-breaking rules. (3) The solutions are invariant to the magnitude of the bids. To ensure security, I present a cryptographic protocol for the price trajectory algorithm. The cryptographic protocol guarantees that only the auctioneer obtains the correct and necessary information from the agents.