Source author record

Sadra Yazdanbod

Sadra Yazdanbod appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computer Science and Game Theory Computational Complexity math.DS math.SP Populations and Evolution

Catalog footprint

What is connected

5works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Settling the Complexity of Arrow-Debreu Markets under Leontief and PLC Utilities, using the Classes FIXP and \Exists-R

This paper resolves two of the handful of remaining questions on the computability of market equilibria, a central theme within algorithmic game theory (AGT). Our results are as follows: 1. We show FIXP-hardness of computing equilibria in Arrow-Debreu markets under Leontief utility functions, and Arrow-Debreu markets under linear utility functions and Leontief production sets. We note that these are the first FIXP-hardness results ever since the introduction of the class FIXP and the hardness of 3-Nash established therein. 2. We note that for the problems stated above, the corresponding results showing membership in FIXP were established after imposing suitable sufficiency conditions to render the problems total, as is customary in economics. However, if all instances are under consideration, then in both cases we prove that the problem of deciding if a given instance admits an equilibrium is \Exists-R-complete, where \Exists-R is the class of decision problems which can be reduced in polynomial time to Existential Theory of the Reals. 3. For Arrow-Debreu markets under Leontief utility functions and a constant number of agents, we give a polynomial-time algorithm for computing an equilibrium. This settles part of an open problem of Devanur and Kannan (FOCS'08). We note that PLC utilities are about the most general utilities of interest in economics and several fundamental utility functions studied within AGT are special cases of it. Several important problems, which have been shown to be in FIXP, are waiting for proofs of FIXP-hardness. In this context, our technique of reducing from 3-Nash to Multivariate Polynomial Equations and then to the problem is likely to be useful in the future.

preprint2016arXiv

Convex Program Duality, Fisher Markets, and Nash Social Welfare

We study Fisher markets and the problem of maximizing the Nash social welfare (NSW), and show several closely related new results. In particular, we obtain: -- A new integer program for the NSW maximization problem whose fractional relaxation has a bounded integrality gap. In contrast, the natural integer program has an unbounded integrality gap. -- An improved, and tight, factor 2 analysis of the algorithm of [7]; in turn showing that the integrality gap of the above relaxation is at most 2. The approximation factor shown by [7] was $2e^{1/e} \approx 2.89$. -- A lower bound of $e^{1/e}\approx 1.44$ on the integrality gap of this relaxation. -- New convex programs for natural generalizations of linear Fisher markets and proofs that these markets admit rational equilibria. These results were obtained by establishing connections between previously known disparate results, and they help uncover their mathematical underpinnings. We show a formal connection between the convex programs of Eisenberg and Gale and that of Shmyrev, namely that their duals are equivalent up to a change of variables. Both programs capture equilibria of linear Fisher markets. By adding suitable constraints to Shmyrev's program, we obtain a convex program that captures equilibria of the spending-restricted market model defined by [7] in the context of the NSW maximization problem. Further, adding certain integral constraints to this program we get the integer program for the NSW mentioned above. The basic tool we use is convex programming duality. In the special case of convex programs with linear constraints (but convex objectives), we show a particularly simple way of obtaining dual programs, putting it almost at par with linear program duality. This simple way of finding duals has been used subsequently for many other applications.

preprint2016arXiv

New Convex Programs for Fisher's Market Model and its Generalizations

We present the following results pertaining to Fisher's market model: -We give two natural generalizations of Fisher's market model: In model M_1, sellers can declare an upper bound on the money they wish to earn (and take back their unsold good), and in model M_2, buyers can declare an upper bound on the amount to utility they wish to derive (and take back the unused part of their money). -We derive convex programs for the linear case of these two models by generalizing a convex program due to Shmyrev and the Eisenberg-Gale program, respectively. -We generalize the Arrow-Hurwicz theorem to the linear case of these two models, hence deriving alternate convex programs. -For the special class of convex programs having convex objective functions and linear constraints, we derive a simple set of rules for constructing the dual program (as simple as obtaining the dual of an LP). Using these rules we show a formal relationship between the two seemingly different convex programs for linear Fisher markets, due to Eisenberg-Gale and Shmyrev; the duals of these are the same, upto a change of variables.

preprint2015arXiv

The Complexity of Genetic Diversity

A key question in biological systems is whether genetic diversity persists in the long run under evolutionary competition or whether a single dominant genotype emerges. Classic work by Kalmus in 1945 has established that even in simple diploid species (species with two chromosomes) diversity can be guaranteed as long as the heterozygote individuals enjoy a selective advantage. Despite the classic nature of the problem, as we move towards increasingly polymorphic traits (e.g. human blood types) predicting diversity and understanding its implications is still not fully understood. Our key contribution is to establish complexity theoretic hardness results implying that even in the textbook case of single locus diploid models predicting whether diversity survives or not given its fitness landscape is algorithmically intractable. We complement our results by establishing that under randomly chosen fitness landscapes diversity survives with significant probability. Our results are structurally robust along several dimensions (e.g., choice of parameter distribution, different definitions of stability/persistence, restriction to typical subclasses of fitness landscapes). Technically, our results exploit connections between game theory, nonlinear dynamical systems, complexity theory and biology and establish hardness results for predicting the evolution of a deterministic variant of the well known multiplicative weights update algorithm in symmetric coordination games which could be of independent interest.

preprint2014arXiv

Settling Some Open Problems on 2-Player Symmetric Nash Equilibria

Over the years, researchers have studied the complexity of several decision versions of Nash equilibrium in (symmetric) two-player games (bimatrix games). To the best of our knowledge, the last remaining open problem of this sort is the following; it was stated by Papadimitriou in 2007: find a non-symmetric Nash equilibrium (NE) in a symmetric game. We show that this problem is NP-complete and the problem of counting the number of non-symmetric NE in a symmetric game is #P-complete. In 2005, Kannan and Theobald defined the "rank of a bimatrix game" represented by matrices (A, B) to be rank(A+B) and asked whether a NE can be computed in rank 1 games in polynomial time. Observe that the rank 0 case is precisely the zero sum case, for which a polynomial time algorithm follows from von Neumann's reduction of such games to linear programming. In 2011, Adsul et. al. obtained an algorithm for rank 1 games; however, it does not solve the case of symmetric rank 1 games. We resolve this problem.