BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jugal Garg

Jugal Garg 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 TheoryData Structures and AlgorithmsComputational ComplexityDiscrete MathematicsMultiagent Systems

Catalog footprint

What is connected

19works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

19 published item(s)

preprint2022arXiv

A Strongly Polynomial Algorithm for Linear Exchange Markets

We present a strongly polynomial algorithm for computing an equilibrium in Arrow-Debreu exchange markets with linear utilities. Our algorithm is based on a variant of the weakly-polynomial Duan-Mehlhorn (DM) algorithm. We use the DM algorithm as a subroutine to identify revealed edges, i.e. pairs of agents and goods that must correspond to best bang-per-buck transactions in every equilibrium solution. Every time a new revealed edge is found, we use another subroutine that decides if there is an optimal solution using the current set of revealed edges, or if none exists, finds the solution that approximately minimizes the violation of the demand and supply constraints. This task can be reduced to solving a linear program (LP). Even though we are unable to solve this LP in strongly polynomial time, we show that it can be approximated by a simpler LP with two variables per inequality that is solvable in strongly polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands

We consider the Arrow--Debreu exchange market model under the assumption that the agents' demands satisfy the weak gross substitutes (WGS) property. We present a simple auction algorithm that obtains an approximate market equilibrium for WGS demands assuming the availability of a price update oracle. We exhibit specific implementations of such an oracle for WGS demands with bounded price elasticities and for Gale demand systems. As an application of our result, we obtain an efficient algorithm to find an approximate spending-restricted market equilibrium for WGS demands, a model that has been recently introduced as a continuous relaxation of the Nash social welfare (NSW) problem. This leads to a polynomial-time constant factor approximation algorithm for the NSW problem with capped additive separable piecewise linear utility functions; only a pseudopolynomial approximation algorithm was known for this setting previously.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Competitive Equilibrium with Chores: Combinatorial Algorithm and Hardness

We study the computational complexity of finding a competitive equilibrium (CE) with chores when agents have linear preferences. CE is one of the most preferred mechanisms for allocating a set of items among agents. CE with equal incomes (CEEI), Fisher, and Arrow-Debreu (exchange) are the fundamental economic models to study allocation problems, where CEEI is a special case of Fisher and Fisher is a special case of exchange. When the items are goods (giving utility), the CE set is convex even in the exchange model, facilitating several combinatorial polynomial-time algorithms (starting with the seminal work of Devanur, Papadimitriou, Saberi and Vazirani) for all of these models. In sharp contrast, when the items are chores (giving disutility), the CE set is known to be non-convex and disconnected even in the CEEI model. Further, no combinatorial algorithms or hardness results are known for these models. In this paper, we give two main results for CE with chores: 1) A combinatorial algorithm to compute a $(1-\varepsilon)$-approximate CEEI in time $\tilde{\mathcal{O}}(n^4m^2 / \varepsilon^2)$, where $n$ is the number of agents and $m$ is the number of chores. 2) PPAD-hardness of finding a $(1-1/\mathit{poly}(n))$-approximate CE in the exchange model under a sufficient condition. To the best of our knowledge, these results show the first separation between the CEEI and exchange models when agents have linear preferences, assuming PPAD $\neq $ P. Finally, we show that our new insight implies a straightforward proof of the existence of an allocation that is both envy-free up to one chore (EF1) and Pareto optimal (PO) in the discrete setting when agents have factored bivalued preferences.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Tractable Fragments of the Maximum Nash Welfare Problem

We study the problem of maximizing Nash welfare (MNW) while allocating indivisible goods to asymmetric agents. The Nash welfare of an allocation is the weighted geometric mean of agents' utilities, and the allocation with maximum Nash welfare is known to satisfy several desirable fairness and efficiency properties. However, computing such an MNW allocation is NP-hard, even for two agents with identical, additive valuations. Hence, we aim to identify tractable classes that either admit a PTAS, an FPTAS, or an exact polynomial-time algorithm. To this end, we design a PTAS for finding an MNW allocation for the case of asymmetric agents with identical, additive valuations, thus generalizing a similar result for symmetric agents. Our techniques can also be adapted to give a PTAS for the problem of computing the optimal $p$-mean welfare. We also show that an MNW allocation can be computed exactly in polynomial time for identical agents with $k$-ary valuations when $k$ is a constant, where every agent has at most $k$ different values for the goods. Next, we consider the special case where every agent finds at most two goods valuable, and show that this class admits an efficient algorithm, even for general monotone valuations. In contrast, we note that when agents can value three or more goods, maximizing Nash welfare is NP-hard, even when agents are symmetric and have additive valuations, showing our algorithmic result is essentially tight. Finally, we show that for constantly many asymmetric agents with additive valuations, the MNW problem admits an FPTAS.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Improving EFX Guarantees through Rainbow Cycle Number

We study the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of EFX allocations has not been settled and is one of the most important problems in fair division. Towards resolving this problem, many impressive results show the existence of its relaxations, e.g., the existence of $0.618$-EFX allocations, and the existence of EFX at most $n-1$ unallocated goods. The latter result was recently improved for three agents, in which the two unallocated goods are allocated through an involved procedure. Reducing the number of unallocated goods for arbitrary number of agents is a systematic way to settle the big question. In this paper, we develop a new approach, and show that for every $\varepsilon \in (0,1/2]$, there always exists a $(1-\varepsilon)$-EFX allocation with sublinear number of unallocated goods and high Nash welfare. For this, we reduce the EFX problem to a novel problem in extremal graph theory. We introduce the notion of rainbow cycle number $R(\cdot)$. For all $d \in \mathbb{N}$, $R(d)$ is the largest $k$ such that there exists a $k$-partite digraph $G =(\cup_{i \in [k]} V_i, E)$, in which 1) each part has at most $d$ vertices, i.e., $\lvert V_i \rvert \leq d$ for all $i \in [k]$, 2) for any two parts $V_i$ and $V_j$, each vertex in $V_i$ has an incoming edge from some vertex in $V_j$ and vice-versa, and 3) there exists no cycle in $G$ that contains at most one vertex from each part. We show that any upper bound on $R(d)$ directly translates to a sublinear bound on the number of unallocated goods. We establish a polynomial upper bound on $R(d)$, yielding our main result. Furthermore, our approach is constructive, which also gives a polynomial-time algorithm for finding such an allocation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Competitive Allocation of a Mixed Manna

We study the fair division problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bads that everyone dislikes, as well as items that some like and others dislike. The seminal work of Bogomolnaia et al. [Econometrica'17] argue why allocating a mixed manna is genuinely more complicated than a good or a bad manna, and why competitive equilibrium is the best mechanism. They also provide the existence of equilibrium and establish its peculiar properties (e.g., non-convex and disconnected set of equilibria even under linear utilities), but leave the problem of computing an equilibrium open. This problem remained unresolved even for only bad manna under linear utilities. Our main result is a simplex-like algorithm based on Lemke's scheme for computing a competitive allocation of a mixed manna under SPLC utilities, a strict generalization of linear. Experimental results on randomly generated instances suggest that our algorithm will be fast in practice. The problem is known to be PPAD-hard for the case of good manna, and we also show a similar result for the case of bad manna. Given these PPAD-hardness results, designing such an algorithm is the only non-brute-force (non-enumerative) option known, e.g., the classic Lemke-Howson algorithm (1964) for computing a Nash equilibrium in a 2-player game is still one of the most widely used algorithms in practice. Our algorithm also yields several new structural properties as simple corollaries. We obtain a (constructive) proof of existence for a far more general setting, membership of the problem in PPAD, rational-valued solution, and odd number of solutions property. The last property also settles the conjecture of Bogomolnaia et al. in the affirmative.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores

We study the chore division problem where a set of agents needs to divide a set of chores (bads) among themselves fairly and efficiently. We assume that agents have linear disutility (cost) functions. Like for the case of goods, competitive division is known to be arguably the best mechanism for the bads as well. However, unlike goods, there are multiple competitive divisions with very different disutility value profiles in bads. Although all competitive divisions satisfy the standard notions of fairness and efficiency, some divisions are significantly fairer and efficient than the others. This raises two important natural questions: Does there exist a competitive division in which no agent is assigned a chore that she hugely dislikes? Are there simple sufficient conditions for the existence and polynomial-time algorithms assuming them? We investigate both these questions in this paper. We show that the first problem is strongly NP-hard. Further, we derive a simple sufficient condition for the existence, and we show that finding a competitive division is PPAD-hard assuming the condition. These results are in sharp contrast to the case of goods where both problems are strongly polynomial-time solvable. To the best of our knowledge, these are the first hardness results for the chore division problem, and, in fact, for any economic model under linear preferences.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

EFX Exists for Three Agents

We study the problem of distributing a set of indivisible items among agents with additive valuations in a $\mathit{fair}$ manner. The fairness notion under consideration is Envy-freeness up to any item (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this paper, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture by Caragiannis et al. by showing an instance with three agents for which there is a partial EFX allocation (some items are not allocated) with higher Nash welfare than that of any complete EFX allocation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fair and Efficient Allocations under Subadditive Valuations

We study the problem of allocating a set of indivisible goods among agents with subadditive valuations in a fair and efficient manner. Envy-Freeness up to any good (EFX) is the most compelling notion of fairness in the context of indivisible goods. Although the existence of EFX is not known beyond the simple case of two agents with subadditive valuations, some good approximations of EFX are known to exist, namely $\tfrac{1}{2}$-EFX allocation and EFX allocations with bounded charity. Nash welfare (the geometric mean of agents' valuations) is one of the most commonly used measures of efficiency. In case of additive valuations, an allocation that maximizes Nash welfare also satisfies fairness properties like Envy-Free up to one good (EF1). Although there is substantial work on approximating Nash welfare when agents have additive valuations, very little is known when agents have subadditive valuations. In this paper, we design a polynomial-time algorithm that outputs an allocation that satisfies either of the two approximations of EFX as well as achieves an $\mathcal{O}(n)$ approximation to the Nash welfare. Our result also improves the current best-known approximation of $\mathcal{O}(n \log n)$ and $\mathcal{O}(m)$ to Nash welfare when agents have submodular and subadditive valuations, respectively. Furthermore, our technique also gives an $\mathcal{O}(n)$ approximation to a family of welfare measures, $p$-mean of valuations for $p\in (-\infty, 1]$, thereby also matching asymptotically the current best known approximation ratio for special cases like $p =-\infty$ while also retaining the fairness properties.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings

We study the problem of approximating maximum Nash social welfare (NSW) when allocating m indivisible items among n asymmetric agents with submodular valuations. The NSW is a well-established notion of fairness and efficiency, defined as the weighted geometric mean of agents' valuations. For special cases of the problem with symmetric agents and additive(-like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with factor independent of m is known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(-like) valuations. In this paper, we extend our understanding of the NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations respectively. Both algorithms are simple to understand and involve non-trivial modifications of a greedy repeated matchings approach. Allocations of high valued items are done separately by un-matching certain items and re-matching them, by processes that are different in both algorithms. We show that these approaches achieve approximation factors of O(n) and O(n log n) for additive and submodular case respectively, which is independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envy-free up to one item (EF1). Furthermore, we show that the NSW problem under submodular valuations is strictly harder than all currently known settings with an e/(e-1) factor of the hardness of approximation, even for constantly many agents. For this case, we provide a different approximation algorithm that achieves a factor of e/(e-1), hence resolving it completely.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Ascending-Price Algorithms for Unknown Markets

We design a simple ascending-price algorithm to compute a $(1+\varepsilon)$-approximate equilibrium in Arrow-Debreu exchange markets with weak gross substitute (WGS) property, which runs in time polynomial in market parameters and $\log 1/\varepsilon$. This is the first polynomial-time algorithm for most of the known tractable classes of Arrow-Debreu markets, which is easy to implement and avoids heavy machinery such as the ellipsoid method. In addition, our algorithm can be applied in unknown market setting without exact knowledge about the number of agents, their individual utilities and endowments. Instead, our algorithm only relies on queries to a global demand oracle by posting prices and receiving aggregate demand for goods as feedback. When demands are real-valued functions of prices, the oracles can only return values of bounded precision based on real utility functions. Due to this more realistic assumption, precision and representation of prices and demands become a major technical challenge, and we develop new tools and insights that may be of independent interest. Furthermore, our approach also gives the first polynomial-time algorithm to compute an exact equilibrium for markets with spending constraint utilities, a piecewise linear concave generalization of linear utilities. This resolves an open problem posed by Duan and Mehlhorn (2015).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Computing Equilibria in Markets with Budget-Additive Utilities

We present the first analysis of Fisher markets with buyers that have budget-additive utility functions. Budget-additive utilities are elementary concave functions with numerous applications in online adword markets and revenue optimization problems. They extend the standard case of linear utilities and have been studied in a variety of other market models. In contrast to the frequently studied CES utilities, they have a global satiation point which can imply multiple market equilibria with quite different characteristics. Our main result is an efficient combinatorial algorithm to compute a market equilibrium with a Pareto-optimal allocation of goods. It relies on a new descending-price approach and, as a special case, also implies a novel combinatorial algorithm for computing a market equilibrium in linear Fisher markets. We complement these positive results with a number of hardness results for related computational questions. We prove that it is NP-hard to compute a market equilibrium that maximizes social welfare, and it is PPAD-hard to find any market equilibrium with utility functions with separate satiation points for each buyer and each good.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market

We present an improved combinatorial algorithm for the computation of equilibrium prices in the linear Arrow-Debreu model. For a market with $n$ agents and integral utilities bounded by $U$, the algorithm runs in $O(n^7 \log^3 (nU))$ time. This improves upon the previously best algorithm of Ye by a factor of $\tOmega(n)$. The algorithm refines the algorithm described by Duan and Mehlhorn and improves it by a factor of $\tOmega(n^3)$. The improvement comes from a better understanding of the iterative price adjustment process, the improved balanced flow computation for nondegenerate instances, and a novel perturbation technique for achieving nondegeneracy.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Rational Convex Program for Linear Arrow-Debreu Markets

We give a new, flow-type convex program describing equilibrium solutions to linear Arrow-Debreu markets. Whereas convex formulations were previously known [Nenakov, Primak 83; Jain 07; Cornet '89], our program exhibits several new features. It gives a simple necessary and sufficient condition and a concise proof of the existence and rationality of equilibria, settling an open question raised by Vazirani. As a consequence we also obtain a simple new proof of Mertens's result that the equilibrium prices form a convex polyhedral set.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On Computability of Equilibria in Markets with Production

Although production is an integral part of the Arrow-Debreu market model, most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. This paper takes a significant step towards understanding computational aspects of markets with production. We first define the notion of separable, piecewise-linear concave (SPLC) production by analogy with SPLC utility functions. We then obtain a linear complementarity problem (LCP) formulation that captures exactly the set of equilibria for Arrow-Debreu markets with SPLC utilities and SPLC production, and we give a complementary pivot algorithm for finding an equilibrium. This settles a question asked by Eaves in 1975 of extending his complementary pivot algorithm to markets with production. Since this is a path-following algorithm, we obtain a proof of membership of this problem in PPAD, using Todd, 1976. We also obtain an elementary proof of existence of equilibrium (i.e., without using a fixed point theorem), rationality, and oddness of the number of equilibria. We further give a proof of PPAD-hardness for this problem and also for its restriction to markets with linear utilities and SPLC production. Experiments show that our algorithm runs fast on randomly chosen examples, and unlike previous approaches, it does not suffer from issues of numerical instability. Additionally, it is strongly polynomial when the number of goods or the number of agents and firms is constant. This extends the result of Devanur and Kannan (2008) to markets with production. Finally, we show that an LCP-based approach cannot be extended to PLC (non-separable) production, by constructing an example which has only irrational equilibria.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Bilinear Games: Polynomial Time Algorithms for Rank Based Subclasses

Motivated by the sequence form formulation of Koller et al. (GEB'96), this paper defines {\em bilinear games}, and proposes efficient algorithms for its rank based subclasses. Bilinear games are two-player non-cooperative single-shot games with compact polytopal strategy sets and two payoff matrices (A,B) such that when (x,y) is the played strategy profile, the payoffs of the players are xAy and xBy respectively. We show that bilinear games are very general and capture many interesting classes of games like bimatrix games, two player Bayesian games, polymatrix games, two-player extensive form games with perfect recall etc. as special cases, and hence are hard to solve in general. Existence of a (symmetric) Nash equilibrium for (symmetric) bilinear games follow directly from the known results. For a given bilinear game, we define its {\em Best Response Polytopes} (BRPs) and characterize the set of Nash equilibria as {\em fully-labeled} pairs in the BRPs. We consider a rank based hierarchy of bilinear games, where rank of a game (A,B) is defined as rank(A+B). In this paper, we give polynomial time algorithms to compute Nash equilibrium for special classes of bilinear games: (i) Rank-1 games (i.e., rank(A+B)=1). (ii) FPTAS for constant rank games (i.e., rank(A+B) is constant). (iii) When rank(A) or rank(B) is constant. This improves the results by Lipton et al. (EC'03) and Kannan et al. (ET'09), for bimatrix games with low rank matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Nash equilibria in Fisher market

Much work has been done on the computation of market equilibria. However due to strategic play by buyers, it is not clear whether these are actually observed in the market. Motivated by the observation that a buyer may derive a better payoff by feigning a different utility function and thereby manipulating the Fisher market equilibrium, we formulate the {\em Fisher market game} in which buyers strategize by posing different utility functions. We show that existence of a {\em conflict-free allocation} is a necessary condition for the Nash equilibria (NE) and also sufficient for the symmetric NE in this game. There are many NE with very different payoffs, and the Fisher equilibrium payoff is captured at a symmetric NE. We provide a complete polyhedral characterization of all the NE for the two-buyer market game. Surprisingly, all the NE of this game turn out to be symmetric and the corresponding payoffs constitute a piecewise linear concave curve. We also study the correlated equilibria of this game and show that third-party mediation does not help to achieve a better payoff than NE payoffs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Rank-1 Bi-matrix Games: A Homeomorphism and a Polynomial Time Algorithm

Given a rank-1 bimatrix game (A,B), i.e., where rank(A+B)=1, we construct a suitable linear subspace of the rank-1 game space and show that this subspace is homeomorphic to its Nash equilibrium correspondence. Using this homeomorphism, we give the first polynomial time algorithm for computing an exact Nash equilibrium of a rank-1 bimatrix game. This settles an open question posed in Kannan and Theobald (SODA 2007) and Theobald (2007). In addition, we give a novel algorithm to enumerate all the Nash equilibria of a rank-1 game and show that a similar technique may also be applied for finding a Nash equilibrium of any bimatrix game. This technique also proves the existence, oddness and the index theorem of Nash equilibria in a bimatrix game. Further, we extend the rank-1 homeomorphism result to a fixed rank game space, and give a fixed point formulation on $[0,1]^k$ for solving a rank-k game. The homeomorphism and the fixed point formulation are piece-wise linear and considerably simpler than the classical constructions.

0 citations0 reviewsNo code linkedOpen access