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

市场均衡是经济学中的一个核心解决方案概念，在许多领域都有应用。它甚至在不涉及任何货币交换而只要求均衡具有显著的公平性和效率性的非市场环境中也有令人惊讶的应用。 这些应用包括调度、机制设计、公平分配等。设计快速算法计算市场均衡对于许多应用都是至关重要的，对于一些经典的具有可分商品的市场设置，计算均衡归结为最大化代理人效用的几何平均值，称为纳什社会福利。纳什社会福利也被认为是在非市场环境下分配稀缺资源的重要公平概念。最近，人们对找到这种分配不可分割的货物的兴趣激增。然而，即使只有两个代理商的附加值的问题是NP难的，因此设计快速和接近最优的近似算法是在这一领域的关键问题。PI的目的是获得快速算法计算基本市场模型及其扩展的均衡，纳什福利问题。其中许多问题归结为网络流问题，这是在运输和通信等众多应用中出现的核心优化问题。尽管在平衡计算和网络流方面做了大量的工作，但为这些市场模型设计一个强多项式时间算法一直是开放的。该项目的第一个主要目标是在解决这些未决问题方面取得进展。需要开发新的算法技术和工具以及结构性见解来解决这些问题。最近的工作纳什福利问题至关重要地使用市场模型的扩展和他们的连接流问题。该项目的第二个主要目标是获得纳什福利问题的改进近似算法。该项目将支持和聘请两名博士生和一名本科生实现所设计的算法，并测试它们的实际效率。在这个项目中开发的新算法技术将被纳入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.