| Summary: | <p>This thesis addresses computational questions arising in auctions with multiple goods available in multiple quantities, with a focus on establishing the tractability of auction mechanisms used in practice. It presents algorithms and hardness results for solving these auctions with the goal of maximising social welfare or revenue, and develops procedures to facilitate participating agents in expressing their preferences in the auction's bidding language.</p>
<p>The 'strong-substitutes product-mix auction' was originally designed for the Bank of England by Paul Klemperer and continues to be run at least monthly. It introduces a novel bidding language, which allows agents to submit sealed-bid strong-substitutes preferences over an arbitrary number of goods available in multiple discrete units. We study this language geometrically and computationally, and establish connections to related bidding languages in the literature.</p>
<p>In order to solve the strong-substitutes product-mix auction for social welfare, we develop the first efficient algorithms to find market-clearing prices and envy-free allocations of supply to participating bidders. The latter, in particular, requires solving a novel constrained matching problem. By contrast, we show that solving the auction for maximum revenue is APX-hard even in special cases, and present initial algorithms for this.</p>
<p>Agents participating in this auction may have trouble expressing their preferences in the auction's bidding language when faced with a large number of goods or non-trivial demand. Instead, they may be able to answer queries about their value of a given bundle or their demand at given prices. We propose algorithms that learn a bidder's preferences, assuming access to a demand or valuation oracle. In a special case currently implemented by the Bank of England, we present a linear-time algorithm. We also show super-polynomial lower bounds on the query complexity in the general case. Our algorithms constitute the first approach for bidders to express non-trivial preferences in these languages, lowering the barrier for participation in the strong-substitutes product-mix auction.</p>
<p>In the related 'arctic product-mix market', originally designed for the Icelandic government by Klemperer, buyers use a conceptually similar bidding language to express preferences across multiple divisible goods in conjunction with monetary budgets. In this setting we present a new coincidence of the solution concepts of competitive equilibrium and optimal revenue: market-clearing prices are unique, and these prices maximise not only social welfare but also revenue. We also provide an algorithm to identify these prices.</p>
|
|---|