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

本研究针对二部匹配问题的有效演算法进行设计与分析。研究了加权和未加权问题，以及基于有序偏好的稳定匹配变量。动态变量也被考虑；这里的目标是在输入发生微小变化时快速更新最优解决方案。加权二部匹配与一类被称为单位需求拍卖的组合拍卖之间有着密切的联系。例如，在密封投标单位需求拍卖中分配和定价项目的一个基本方法涉及在相应的二部图中计算最大权重匹配。本项目针对多轮投标的单位需求拍卖进行设计与分析。这种“动态”拍卖比密封拍卖更难分析，但具有重要的实际优势。某些调度问题也与二部匹配密切相关。该项目解决了二部匹配问题的调度相关变体的算法设计和分析。尽管对组合拍卖进行了数十年的研究，但公众拍卖消费品的主要拍卖形式仍然是由eBay推广的单件动态第二价格形式。这项研究解决了一个可扩展的基础设施的设计，以支持更具表现力的动态单位需求拍卖。这种基础设施的关键潜在好处是提高了经济效率，也就是说，提高了拍卖项目与最看重它们的竞标者的匹配程度。这种效率的提高给社会带来了直接的好处。此外，在本项目中解决的匹配和调度问题本质上是基本的，并有许多实际应用。

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.