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.