AF: Small: Algorithms for Matching, Auction, and Scheduling Problems

点击翻译按钮获取中文摘要

This research addresses the design and analysis of efficient algorithms for bipartite matching problems. Weighted and unweighted problems are investigated, as well as stable matching variants based on ordinal preferences. Dynamic variants are also considered; here the goal is to rapidly update an optimal solution when a small change is made to the input.There is an intimate connection between weighted bipartite matching and a class of combinatorial auctions known as unit-demand auctions. For example, one fundamental approach to the problem of allocating and pricing items in a sealed-bid unit-demand auction involves computing a maximum-weight matching in a corresponding bipartite graph. This project addresses the design and analysis of unit-demand auctions with multiple rounds of bidding. Such "dynamic" auctions are substantially more difficult to analyze than their sealed-bid counterparts, but offer important practical advantages.Certain scheduling problems are also closely related to bipartite matching. This project addresses the design and analysis of algorithms for scheduling-related variants of bipartite matching problems.In spite of decades of research on combinatorial auctions, the predominant auction format available to the general public for auctioning consumer goods remains the single-item dynamic second-price format, as popularized by eBay. This research addresses the design of a scalable infrastructure for supporting the more expressive class of dynamic unit-demand auctions. The key potential benefit of such an infrastructure is enhanced economic efficiency, that is, improved matching of auction items to the bidders who value them the most. Such enhanced efficiency offers direct benefits to society. In addition, the matching and scheduling problems addressed in this project are fundamental in nature and have numerous practical applications.