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

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

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.