Combinatorial and exchange markets: Algorithms, complexity, and applications

Abstract

In today's world, globalization and the Internet have resulted in the creation of enormously many different kinds of marketplaces. The marketplaces naturally tend to find an equilibrium in terms of prices and interaction of agents. Therefore, understanding the equilibria results in better understanding and prediction of the marketplaces. In this thesis, we study two broad classes of equilibria. The first one is called market price equilibria, which can explain and predict prices within a market. The second one is Nash equilibria (NE), which is arguably the most important and well-studied solution concept within game theory. NE helps us to explain and predict the interactions between agents within a market.

- Market price equilibria. We introduce a new class of combinatorial markets in which agents have covering constraints over resources required and are interested in delay minimization. Our market model is applicable to several settings including scheduling and communicating over a network. We give a proof of the existence of equilibria and a polynomial time algorithm for finding one, drawing heavily on techniques from LP duality and submodular minimization. Next, we show FIXP-hardness of computing equilibria in Arrow-Debreu exchange markets under Leontief utility functions, and Arrow-Debreu markets under linear utility functions and Leontief production sets, thereby settling these open questions of Vazirani and Yannakakis (2011). As a consequence of the results stated above, and the fact that membership in FIXP has been established for PLC utilities, the entire computational difficulty of Arrow-Debreu markets under PLC utility functions lies in the Leontief utility subcase. Finally, we give a polynomial time algorithm for finding an equilibrium in Arrow-Debreu exchange markets under Leontief utility functions provided the number of agents is a constant.

- Nash equilibria. The complexity of 2-player Nash equilibrium is by now well understood. Our contribution is on settling the complexity of finding equilibria with special properties on multi-player games. We show that the following decision versions of 3-Nash are EXISTS-R-complete: checking whether 1. there are two or more equilibria, 2. there exists an equilibrium in which each player gets at least h payoff, where $h$ is a rational number, 3. a given set of strategies are played with non-zero probability, and 5. all the played strategies belong to a given set. EXISTS-R is the class of decision problems which can be reduced in polynomial time to Existential Theory of the Reals. Next, we give a reduction from 3-Nash to symmetric 3-Nash.