CRII: AF: Strongly Polynomial Algorithms for Market Equilibria with Applications to Network Flows and Nash Social Welfare

市场均衡是经济学中的一个核心解决方案概念，在各种领域都有应用。它发现了几个令人惊讶的应用，即使在非市场环境中，不涉及任何货币交换，但只需要均衡的显着公平和效率属性。这些应用包括调度、机制设计、公平分配等。设计计算市场均衡的快速算法对于它们的许多应用是至关重要的，对于许多具有可分商品的经典市场环境，计算均衡归结为最大化代理人效用的几何平均值，称为纳什社会福利。纳什社会福利也被认为是在非市场环境中配置稀缺资源的一个重要的公平理念。最近，人们对寻找这样一种不可分割的商品分配的兴趣激增。然而，即使只有两个代理具有加性估值，该问题也是NP难的，因此设计快速且接近最优的逼近算法是该领域的一个关键问题。PI旨在获得计算基本市场模型及其扩展中的均衡以及Nash福利问题的快速算法。其中许多问题归结为网络流问题，这是在许多应用中出现的中心优化问题，如交通和通信。尽管在均衡计算和网络流方面做了大量工作，但为这些市场模型中的许多模型设计强多项式时间算法一直是悬而未决的。该项目的第一个主旨是在解决这些悬而未决的问题方面取得进展。将需要开发新的算法技术和工具以及结构洞察力来解决这些问题。最近关于纳什福利问题的研究关键地使用了市场模型的扩展及其与流动问题的联系。这个项目的第二个主旨是获得纳什福利问题的改进的近似算法。该项目将支持和聘请两名博士生和一名本科生来实现所设计的算法，并测试它们的实际效率。在这个项目中开发的新算法技术将被纳入PI教授的关于游戏和市场的研究生课程。所有教育和实施材料都将在网上免费提供。

Market equilibrium is a central solution concept in economics with applications in a variety of domains. It has found several surprising applications even in non-market settings which do not involve any exchange of money but only require the remarkable fairness and efficiency properties of equilibria. These applications include scheduling, mechanism design, fair division, and others. Designing fast algorithms for computing equilibria in markets is vital for their many applications.For a number of classical market settings with divisible goods, computing an equilibrium reduces to maximizing the geometric mean of agents' utilities, called the Nash social welfare. Nash social welfare is also considered an important fairness notion in allocating scarce resources in a non-market setting. Recently there has been a surge of interest in finding such an allocation with indivisible goods. However, the problem is NP-hard even when there are only two agents with additive valuations, and hence designing fast and near-optimal approximation algorithms is a crucial problem in this domain.The PI aims to obtain fast algorithms for computing equilibria in fundamental market models and their extensions, and for the Nash welfare problem. Many of these reduce to network flow problems, which are central optimization problems that arise in numerous applications such as transportation and communication. Despite the extensive work on equilibrium computation and network flows, designing a strongly polynomial time algorithm for many of these market models has been long open. The first main thrust of this project is to make progress towards settling these open questions. New algorithmic techniques and tools, as well as structural insights will need to be developed to solve them. Recent work on the Nash welfare problem crucially uses the market model extensions and their connections with the flow problems. The second main thrust of this project is to obtain improved approximation algorithms for the Nash welfare problem.The project will support and engage two PhD students, and an undergraduate student to implement the designed algorithms and test them for their practical efficiency. The new algorithmic techniques developed in this project will be incorporated into a graduate course on Games and Markets that the PI teaches. All the educational and implementation material will be made freely available online.