Ruta Mehta

AAMAS Conference 2026 Conference Paper

Online Fair Division With Subsidy: When Do Envy-Free Allocations Exist, and at What Cost?

• Pooja Kulkarni
• Ruta Mehta
• Vishnu V. Narayan
• Tomasz Ponitka

We study the problem of fairly allocating 𝑚 indivisible items arriving online, among 𝑛 (offline) agents. Although envy-freeness has emerged as the archetypal fairness notion, envy-free (EF) allocations need not exist with indivisible items. To bypass this, a prominent line of research demonstrates that there exist allocations that can be made envy-free by allowing a subsidy. Extensive work in the offline setting has focused on finding such envy-freeable allocationswithboundedsubsidy. Weextendthisliteraturetoanonline setting where items arrive one at a time and must be immediately and irrevocably allocated. Our contributions are two-fold: • Maintaining EF Online: We show that envy-freeability cannot always be preserved online when the valuations are submodular or supermodular, even with binary marginals. In contrast, we design online algorithms that maintain envy-freeability at every step for the class of additive valuations, and for its superclasses including 𝑘-demand valuations and SPLC valuations. • Ensuring Low Subsidy: We investigate the quantity of subsidy required to guarantee envy-freeness online. Surprisingly, even for additive valuations, the minimum subsidy may be as large as Ω(𝑚𝑛), incontrasttotheofflinesetting, wheretheboundis𝑂(𝑛). On the positive side, we identify valuation classes where the minimum subsidy is small (i. e. , does not depend on𝑚), including 𝑘-valued, rank-one, restricted additive, and identical valuations, and we obtain (mostly) tight subsidy bounds for these classes.

STOC Conference 2025 Conference Paper

Monotone Contractions

• Eleni Batziou
• John Fearnley
• Spencer Gordon
• Ruta Mehta
• Rahul Savani

AAMAS Conference 2025 Conference Paper

On the Structure of EFX Orientations on Graphs

• Jinghan A. Zeng
• Ruta Mehta

Discrete Fair division is the problem of allocating a set of indivisible items among agents in a fair manner. Envy-freeness up to any good (EFX) has emerged as one of the strongest fairness guarantees for this problem, however, its existence remains unknown. Christodoulou, Fiat, Koutsoupias, and Sgouritsa (EC 2023) introduced graphical valuations represented by a graph, where nodes represent agents and edges are items valued only by its endpoints, and under these showed that EFX allocation exist. They showed that such an allocation need not be efficient–in the sense that every edge is assigned (oriented) to one of its endpoints–and proved that determining whether an EFX orientation exists is NP-hard. They left the characterization of graphs admitting EFX orientation as an important open question. Towards this question, we introduce the notion of strongly EFXorientable graphs, defined as graphs that have an EFX orientation for any valuation assignment. We establish a surprising connection between this property and the chromatic number of the graph. Specifically: • Graphs with chromatic number 𝜒(𝐺) ≤ 2 are strongly EFXorientable. • Graphs with 𝜒(𝐺) ≥ 4 are not strongly EFX-orientable. • For graphs with 𝜒(𝐺) = 3, we identify both strongly EFXorientable and non-strongly EFX-orientable examples, demonstrating the sharpness of our characterization. For binary valuations, we provide a complete characterization.

ICML Conference 2025 Conference Paper

You Get What You Give: Reciprocally Fair Federated Learning

• Aniket Murhekar
• Jiaxin Song
• Parnian Shahkar
• Bhaskar Ray Chaudhury
• Ruta Mehta

Federated learning (FL) is a popular collaborative learning paradigm, whereby agents with individual datasets can jointly train an ML model. While higher data sharing improves model accuracy and leads to higher payoffs, it also raises costs associated with data acquisition or loss of privacy, causing agents to be strategic about their data contribution. This leads to undesirable behavior at a Nash equilibrium (NE) such as free-riding, resulting in sub-optimal fairness, data sharing, and welfare. To address this, we design $\mathcal{M}^{Shap}$, a budget-balanced payment mechanism for FL, that admits Nash equilibria under mild conditions, and achieves reciprocal fairness: where each agent’s payoff equals her contribution to the collaboration, as measured by the Shapley share. In addition to fairness, we show that the NE under $\mathcal{M}^{Shap}$ has desirable guarantees in terms of accuracy, welfare, and total data collected. We validate our theoretical results through experiments, demonstrating that $\mathcal{M}^{Shap}$ outperforms baselines in terms of fairness and efficiency.

AAAI Conference 2024 Conference Paper

1/2-Approximate MMS Allocation for Separable Piecewise Linear Concave Valuations

• Chandra Chekuri
• Pooja Kulkarni
• Rucha Kulkarni
• Ruta Mehta

We study fair distribution of a collection of m indivisible goods among a group of n agents, using the widely recognized fairness principles of Maximin Share (MMS) and Any Price Share (APS). These principles have undergone thorough investigation within the context of additive valuations. We explore these notions for valuations that extend beyond additivity. First, we study approximate MMS under the separable (piecewise-linear) concave (SPLC) valuations, an important class generalizing additive, where the best known factor was 1/3-MMS. We show that 1/2-MMS allocation exists and can be computed in polynomial time, significantly improving the state-of-the-art. We note that SPLC valuations introduce an elevated level of intricacy in contrast to additive. For instance, the MMS value of an agent can be as high as her value for the entire set of items. We use a relax-and-round paradigm that goes through competitive equilibrium and LP relaxation. Our result extends to give (symmetric) 1/2-APS, a stronger guarantee than MMS. APS is a stronger notion that generalizes MMS by allowing agents with arbitrary entitlements. We study the approximation of APS under submodular valuation functions. We design and analyze a simple greedy algorithm using concave extensions of submodular functions. We prove that the algorithm gives a 1/3-APS allocation which matches the best-known factor. Concave extensions are hard to compute in polynomial time and are, therefore, generally not used in approximation algorithms. Our approach shows a way to utilize it within analysis (while bypassing its computation), and hence might be of independent interest.

AAMAS Conference 2024 Conference Paper

Approximating APS Under Submodular and XOS Valuations with Binary Marginals

• Pooja Kulkarni
• Rucha Kulkarni
• Ruta Mehta

We study the problem of fairly dividing indivisible goods among a set of agents under the fairness notion of Any Price Share (APS). APS is known to dominate the widely studied Maximin share (MMS). Since an exact APS allocation may not exist, the focus has traditionally been on the computation of approximate APS allocations. [4] studied the problem under additive valuations, and asked (𝑖) how large can the APS value be compared to the MMS value? and (𝑖𝑖) what guarantees can one achieve beyond additive functions. We partly answer these questions by considering valuations beyond additive, namely submodular and XOS functions, with binary marginals. For the submodular functions with binary marginals, also known as matroid rank functions (MRFs), we show that APS is exactly equal to MMS. Consequently, following [5] we show that an exact APS allocation exists and can be computed efficiently while maximizing the social welfare. Complementing this result, we show that it is NP-hard to compute the APS value within a factor of 5/6 for submodular valuations with three distinct marginals of {0, 1 2, 1}. We then consider binary XOS functions, which are immediate generalizations of binary submodular functions in the complement free hierarchy. In contrast to the MRFs setting, MMS and APS values are not equal under this case. Nevertheless, we can show that they are only a constant factor apart. In particular, we show that under binary XOS valuations, MMS ≤ APS ≤ 2 · MMS + 1. Further, we show that this is almost the tightest bound we can get using MMS, by giving an instance where APS ≥ 2 · MMS. The upper bound on APS, combined with [17], implies a 0. 1222-approximation for APS under binary XOS valuations. And the lower bound implies the nonexistence of better than 0. 5-APS even when agents have identical valuations, which is in sharp contrast to the guaranteed existence of exact MMS allocation when agent valuations are identical.

ICML Conference 2024 Conference Paper

Fair Federated Learning via the Proportional Veto Core

• Bhaskar Ray Chaudhury
• Aniket Murhekar
• Zhuowen Yuan
• Bo Li 0026
• Ruta Mehta
• Ariel D. Procaccia

Previous work on fairness in federated learning introduced the notion of core stability, which provides utility-based fairness guarantees to any subset of participating agents. However, these guarantees require strong assumptions on agent utilities that render them impractical. To address this shortcoming, we measure the quality of output models in terms of their ordinal rank instead of their cardinal utility, and use this insight to adapt the classical notion of proportional veto core (PVC) from social choice theory to the federated learning setting. We prove that models that are PVC-stable exist in very general learning paradigms, even allowing non-convex model sets, as well as non-convex and non-concave loss functions. We also design Rank-Core-Fed, a distributed federated learning algorithm, to train a PVC-stable model. Finally, we demonstrate that Rank-Core-Fed outperforms baselines in terms of fairness on different datasets.

SODA Conference 2024 Conference Paper

Minimization is Harder in the Prophet World

• Vasilis Livanos
• Ruta Mehta

AAMAS Conference 2024 Conference Paper

On the existence of EFX under picky or non-differentiative agents

• Maya Viswanathan
• Ruta Mehta

In this paper, we consider the fair division of indivisible goods under arguably the strongest envy-based fairness notion of envy-free up to any item (EFX). Extending the long line of work on special cases of additive valuations, we show existence of EFX for the following two cases: (𝑖) instances where agents are very picky, i. e. , each agent likes at most four items positively. (𝑖𝑖) ternary instances where the value of an agent for an item is 0, 𝑎, or 𝑏 for 0 < 𝑎 < 𝑏 ≤ 2𝑎. In both cases, the existence is shown by designing an efficient algorithm to find an EFX allocation.

IJCAI Conference 2023 Conference Paper

Fair and Efficient Allocation of Indivisible Chores with Surplus

• Hannaneh Akrami
• Bhaskar Ray Chaudhury
• Jugal Garg
• Kurt Mehlhorn
• Ruta Mehta

We study fair division of indivisible chores among n agents with additive disutility functions. Two well-studied fairness notions for indivisible items are envy-freeness up to one/any item (EF1/EFX) and the standard notion of economic efficiency is Pareto optimality (PO). There is a noticeable gap between the results known for both EF1 and EFX in the goods and chores settings. The case of chores turns out to be much more challenging. We reduce this gap by providing slightly relaxed versions of the known results on goods for the chores setting. Interestingly, our algorithms run in polynomial time, unlike their analogous versions in the goods setting. We introduce the concept of k surplus in the chores setting which means that up to k more chores are allocated to the agents and each of them is a copy of an original chore. We present a polynomial-time algorithm which gives EF1 and PO allocations with n-1 surplus. We relax the notion of EFX slightly and define tEFX which requires that the envy from agent i to agent j is removed upon the transfer of any chore from the i's bundle to j's bundle. We give a polynomial-time algorithm that in the chores case for 3 agents returns an allocation which is either proportional or tEFX. Note that proportionality is a very strong criterion in the case of indivisible items, and hence both notions we guarantee are desirable.

NeurIPS Conference 2023 Conference Paper

Incentives in Federated Learning: Equilibria, Dynamics, and Mechanisms for Welfare Maximization

• Aniket Murhekar
• Zhuowen Yuan
• Bhaskar Ray Chaudhury
• Bo Li
• Ruta Mehta

Federated learning (FL) has emerged as a powerful scheme to facilitate the collaborative learning of models amongst a set of agents holding their own private data. Although the agents benefit from the global model trained on shared data, by participating in federated learning, they may also incur costs (related to privacy and communication) due to data sharing. In this paper, we model a collaborative FL framework, where every agent attempts to achieve an optimal trade-off between her learning payoff and data sharing cost. We show the existence of Nash equilibrium (NE) under mild assumptions on agents' payoff and costs. Furthermore, we show that agents can discover the NE via best response dynamics. However, some of the NE may be bad in terms of overall welfare for the agents, implying little incentive for some fraction of the agents to participate in the learning. To remedy this, we design a budget-balanced mechanism involving payments to the agents, that ensures that any $p$-mean welfare function of the agents' utilities is maximized at NE. In addition, we introduce a FL protocol FedBR-BG that incorporates our budget-balanced mechanism, utilizing best response dynamics. Our empirical validation on MNIST and CIFAR-10 substantiates our theoretical analysis. We show that FedBR-BG outperforms the basic best-response-based protocol without additional incentivization, the standard federated learning protocol FedAvg, as well as a recent baseline MWFed in terms of achieving superior $p$-mean welfare.

AAMAS Conference 2023 Conference Paper

Maximin Share Allocations for Assignment Valuations

• Pooja Kulkarni
• Rucha Kulkarni
• Ruta Mehta

In this paper, we initiate the study of fairly dividing a set of indivisible resources under the fairness notion of Maximin share (MMS), for the setting where the agents have assignment or OXS valuation functions. These are a popular subclass of functions that lie between the well-studied submodular and additive function classes.

AAMAS Conference 2022 Conference Paper

(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna

• Vasilis Livanos
• Ruta Mehta
• Aniket Murhekar

We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents, where each item may be a good (positively valued) for some agents and a bad (negatively valued) for others, i. e. , a mixed manna. As fairness notions, we consider arguably the strongest possible relaxations of envy-freeness and proportionality, namely envy-free up to any item (EFX and EFX0), and proportional up to the maximin good or any bad (PropMX and PropMX0). Our efficiency notion is Pareto-optimality (PO). We study two types of instances: (i) Separable, where the item set can be partitioned into goods and bads, and (ii) Restricted mixed goods (RMG), where for each item j, every agent has either a nonpositive value for j, or values j at the same vj > 0. We obtain polynomial-time algorithms for the following: • Separable instances: PropMX0 allocation. • RMG instances: Let pure bads be the set of items that everyone values negatively. – PropMX allocation for general pure bads. – EFX+PropMX allocation for identically-ordered pure bads. – EFX+PropMX+PO allocation for identical pure bads. Finally, if the RMG instances are further restricted to binary mixed goods where all the vj ’s are the same, we strengthen the results to guarantee EFX0 and PropMX0 respectively.

NeurIPS Conference 2022 Conference Paper

Fairness in Federated Learning via Core-Stability

• Bhaskar Ray Chaudhury
• Linyi Li
• Mintong Kang
• Bo Li
• Ruta Mehta

Federated learning provides an effective paradigm to jointly optimize a model benefited from rich distributed data while protecting data privacy. Nonetheless, the heterogeneity nature of distributed data, especially in the non-IID setting, makes it challenging to define and ensure fairness among local agents. For instance, it is intuitively ``unfair" for agents with data of high quality to sacrifice their performance due to other agents with low quality data. Currently popular egalitarian and weighted equity-based fairness measures suffer from the aforementioned pitfall. In this work, we aim to formally represent this problem and address these fairness issues using concepts from co-operative game theory and social choice theory. We model the task of learning a shared predictor in the federated setting as a fair public decision making problem, and then define the notion of core-stable fairness: Given $N$ agents, there is no subset of agents $S$ that can benefit significantly by forming a coalition among themselves based on their utilities $U_N$ and $U_S$ (i. e. , $ (|S|/ N) U_S \geq U_N$). Core-stable predictors are robust to low quality local data from some agents, and additionally they satisfy Proportionality (each agent gets at least $1/n$ fraction of the best utility that she can get from any predictor) and Pareto-optimality (there exists no model that can increase the utility of an agent without decreasing the utility of another), two well sought-after fairness and efficiency notions within social choice. We then propose an efficient federated learning protocol CoreFed to optimize a core stable predictor. CoreFed determines a core-stable predictor when the loss functions of the agents are convex. CoreFed also determines approximate core-stable predictors when the loss functions are not convex, like smooth neural networks. We further show the existence of core-stable predictors in more general settings using Kakutani's fixed point theorem. Finally, we empirically validate our analysis on two real-world datasets, and we show that CoreFed achieves higher core-stability fairness than FedAvg while maintaining similar accuracy.

JAAMAS Journal 2022 Journal Article

Online revenue maximization for server pricing

• Shant Boodaghians
• Federico Fusco
• Ruta Mehta

Abstract Efficient and truthful mechanisms to price resources on servers/machines have been the subject of much work in recent years due to the importance of the cloud market. This paper considers revenue maximization in the online stochastic setting with non-preemptive jobs and a unit capacity server. One agent/job arrives at every time step, with parameters drawn from the underlying distribution. We design a posted-price mechanism which can be efficiently computed and is revenue-optimal in expectation and in retrospect, up to additive error. The prices are posted prior to learning the agent’s type, and the computed pricing scheme is deterministic, depending only on the length of the allotted time interval and on the earliest time the server is available. We also prove that the proposed pricing strategy is robust to imprecise knowledge of the job distribution and that a distribution learned from polynomially many samples is sufficient to obtain a near-optimal truthful pricing strategy.

SODA Conference 2022 Conference Paper

Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores

• Shant Boodaghians
• Bhaskar Ray Chaudhury
• Ruta Mehta

Competitive equilibrium with equal income (CEEI ) is considered one of the best mechanisms to allocate a set of items among agents fairly and efficiently. In this paper, we study the computation of CEEI when items are chores that are disliked (negatively valued) by agents, under 1-homogeneous and concave utility functions which includes linear functions as a subcase. It is well-known that, even with linear utilities, the set of CEEI may be non-convex and disconnected, and the problem is PPAD-hard in the more general exchange model. In contrast to these negative results, we design a FPTAS: A polynomial-time algorithm to compute ∊ -approximate CEEI where the running-time depends polynomially on. Our algorithm relies on the recent characterization due to Bogomolnaia et al. (2017) of the CEEI set as exactly the KKT points of a non-convex minimization problem that have all coordinates non-zero. Due to this non-zero constraint, naïve gradient-based methods fail to find the desired local minima as they are attracted towards zero. We develop an exterior-point method that alternates between guessing non-zero KKT points and maximizing the objective along supporting hyperplanes at these points. We show that this procedure must converge quickly to an approximate KKT point which then can be mapped to an approximate CEEI; this exterior point method may be of independent interest. When utility functions are linear, we give explicit procedures for finding the exact iterates, and as a result show that a stronger form of approximate CEEI can be found in polynomial time. Finally, we note that our algorithm extends to the setting of un-equal incomes (CE), and to mixed manna with linear utilities where each agent may like (positively value) some items and dislike (negatively value) others.

SODA Conference 2021 Conference Paper

Competitive Allocation of a Mixed Manna

• Bhaskar Ray Chaudhury
• Jugal Garg
• Peter McGlaughlin
• Ruta Mehta

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. [14] 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. 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 [24], 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-enumerative option known. 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 [14] in the affirmative.

AAAI Conference 2021 Conference Paper

Fair and Efficient Allocations under Subadditive Valuations

• Bhaskar Ray Chaudhury
• Jugal Garg
• Ruta Mehta

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 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 O(n) approximation to the Nash welfare. Our result also improves the current best-known approximation of O(n log n) and O(m) to Nash welfare when agents have submodular and subadditive valuations, respectively. Furthermore, our technique also gives an O(n) approximation to a family of welfare measures, p-mean of valuations for p ∈ (−∞, 1], thereby also matching asymptotically the current best approximation ratio for special cases like p = −∞ while also retaining the remarkable fairness properties.

AAAI Conference 2021 Conference Paper

On the PTAS for Maximin Shares in an Indivisible Mixed Manna

• Rucha Kulkarni
• Ruta Mehta
• Setareh Taki

We study fair allocation of indivisible items, both goods and chores, under the popular fairness notion of maximin share (MMS). The problem is well-studied when there are only goods (or chores), where a PTAS to compute the MMS values of agents is well-known. In contrast, for the mixed manna, a recent result showed that finding even an approximate MMS value of an agent up to any approximation factor in (0, 1] is NP-Hard for general instances. In this paper, we complement the hardness result by obtaining a PTAS to compute the MMS value, when its absolute value is at least 1/p times either the total value of all the goods or total cost of all the chores, for some constant p valued at least 1.

TCS Journal 2020 Journal Article

An incentive compatible, efficient market for air traffic flow management

• Ruta Mehta
• Vijay V. Vazirani

We present a market-based approach to the Air Traffic Flow Management (ATFM) problem. The goods in our market are delays and buyers are airline companies; the latter pay money to the Federal Aviation Administration (FAA) to buy away the desired amount of delay on a per flight basis. We give a notion of equilibrium for this market and an LP whose every optimal solution gives an equilibrium allocation of flights to landing slots as well as equilibrium prices for the landing slots. Via a reduction to matching, we show that this equilibrium can be computed combinatorially in strongly polynomial time. Moreover, there is a special set of equilibrium prices, which can be computed easily, that is identical to the VCG solution, and therefore the market is incentive compatible (truthful) in dominant strategy.

IJCAI Conference 2020 Conference Paper

Online Revenue Maximization for Server Pricing

• Shant Boodaghians
• Federico Fusco
• Stefano Leonardi
• Yishay Mansour
• Ruta Mehta

Efficient and truthful mechanisms to price time on remote servers/machines have been the subject of much work in recent years due to the importance of the cloud market. This paper considers online revenue maximization for a unit capacity server, when jobs are non preemptive, in the Bayesian setting: at each time step, one job arrives, with parameters drawn from an underlying distribution. We design an efficiently computable truthful posted price mechanism, which maximizes revenue in expectation and in retrospect, up to additive error. The prices are posted prior to learning the agent's type, and the computed pricing scheme is deterministic. We also show the pricing mechanism is robust to learning the job distribution from samples, where polynomially many samples suffice to obtain near optimal prices.

NeurIPS Conference 2019 Conference Paper

Multiclass Performance Metric Elicitation

• Gaurush Hiranandani
• Shant Boodaghians
• Ruta Mehta
• Oluwasanmi Koyejo

Metric Elicitation is a principled framework for selecting the performance metric that best reflects implicit user preferences. However, available strategies have so far been limited to binary classification. In this paper, we propose novel strategies for eliciting multiclass classification performance metrics using only relative preference feedback. We also show that the strategies are robust to both finite sample and feedback noise.

SODA Conference 2018 Conference Paper

A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications

• Nikhil R. Devanur
• Jugal Garg
• Ruta Mehta
• Vijay V. Vazirani
• Sadra Yazdanbod

AAMAS Conference 2018 Conference Paper

Nash Equilibrium Computation in Resource Allocation Games

• Shivam Gupta
• Ruta Mehta

STOC Conference 2018 Conference Paper

Sum-of-squares meets nash: lower bounds for finding any equilibrium

• Pravesh K. Kothari
• Ruta Mehta

Computing Nash equilibrium (NE) in two-player game is a central question in algorithmic game theory. The main motivation of this work is to understand the power of sum-of-squares method in computing equilibria, both exact and approximate. Previous works in this context have focused on hardness of approximating “best” equilibria with respect to some natural quality measure on equilibria such as social welfare. Such results, however, do not directly relate to the complexity of the problem of finding any equilibrium. In this work, we propose a framework of roundings for the sum-of-squares algorithm (and convex relaxations in general) applicable to finding approximate/exact equilbria in two player bimatrix games. Specifically, we define the notion of oblivious roundings with verification oracle (OV). These are algorithms that can access a solution to the degree d SoS relaxation to construct a list of candidate (partial) solutions and invoke a verification oracle to check if a candidate in the list gives an (exact or approximate) equilibrium. This framework captures most known approximation algorithms in combinatorial optimization including the celebrated semi-definite programming based algorithms for Max-Cut, Constraint-Satisfaction Problems, and the recent works on SoS relaxations for Unique Games/Small-Set Expansion, Best Separable State, and many problems in unsupervised machine learning. Our main results are strong unconditional lower bounds in this framework. Specifically, we show that for є = Θ(1/ poly ( n )), there’s no algorithm that uses a o ( n )-degree SoS relaxation to construct a 2 o ( n ) -size list of candidates and obtain an є-approximate NE. For some constant є, we show a similar result for degree o (log( n )) SoS relaxation and list size n o (log( n )) . Our results can be seen as an unconditional confirmation, in our restricted algorithmic framework, of the recent Exponential Time Hypothesis for PPAD. Our proof strategy involves constructing a family of games that all share a common sum-of-squares solution but every (approximate) equilibrium of any game is far from every equilibrium of any other game in the family (in either player’s strategy). Along the way, we strengthen the classical unconditional lower bound against enumerative algorithms for finding approximate equilibria due to Daskalakis-Papadimitriou and the classical hardness of computing equilibria due to Gilbow-Zemel.

NeurIPS Conference 2018 Conference Paper

Universal Growth in Production Economies

• Simina Branzei
• Ruta Mehta
• Noam Nisan

We study a simple variant of the von Neumann model of an expanding economy, in which multiple producers make goods according to their production function. The players trade their goods at the market and then use the bundles received as inputs for the production in the next round. The decision that players have to make is how to invest their money (i. e. bids) in each round. We show that a simple decentralized dynamic, where players update their bids on the goods in the market proportionally to how useful the investments were, leads to growth of the economy in the long term (whenever growth is possible) but also creates unbounded inequality, i. e. very rich and very poor players emerge. We analyze several other phenomena, such as how the relation of a player with others influences its development and the Gini index of the system.

STOC Conference 2017 Conference Paper

Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria

• Jugal Garg
• Ruta Mehta
• Vijay V. Vazirani
• Sadra Yazdanbod

ECAI Conference 2016 Conference Paper

Get Me to My GATE on Time: Efficiently Solving General-Sum Bayesian Threat Screening Games

• Aaron Schlenker
• Matthew Brown 0002
• Arunesh Sinha
• Milind Tambe
• Ruta Mehta

Threat Screening Games (TSGs) are used in domains where there is a set of individuals or objects to screen with a limited amount of screening resources available to screen them. TSGs are broadly applicable to domains like airport passenger screening, stadium screening, cargo container screening, etc. Previous work on TSGs focused only on the Bayesian zero-sum case and provided the MGA algorithm to solve these games. In this paper, we solve Bayesian general-sum TSGs which we prove are NP-hard even when exploiting a compact marginal representation. We also present an algorithm based upon a adversary type hierarchical tree decomposition and an efficient branch-and-bound search to solve Bayesian generalsum TSGs. With this we provide four contributions: (1) GATE, the first algorithm for solving Bayesian general-sum TSGs, which uses hierarchical type trees and a novel branch-and-bound search, (2) the Branch-and-Guide approach which combines branch-and-bound search with the MGA algorithm for the first time, (3) heuristics based on properties of TSGs for accelerated computation of GATE, and (4) experimental results showing the scalability of GATE needed for real-world domains.

IJCAI Conference 2016 Conference Paper

To Give or Not to Give: Fair Division for Single Minded Valuations

• Simina Br
• acirc; nzei
• Yuezhou Lv
• Ruta Mehta

Single minded agents have strict preferences, in which a bundle is acceptable only if it meets a certain demand. Such preferences arise naturally in scenarios such as allocating computational resources among users, where the goal is to fairly serve as many requests as possible. In this paper we study the fair division problem for such agents, which is complex due to discontinuity and complementarities of preferences. Our solution concept - the competitive allocation from equal incomes (CAEI) - is inspired from market equilibria and implements fair outcomes through a pricing mechanism. We study existence and computation of CAEI for multiple divisible goods, discrete goods, and cake cutting. Our solution is useful more generally, when the players have a target set of goods, and very small positive values for any bundle other than their target set.

STOC Conference 2014 Conference Paper

Constant rank bimatrix games are PPAD-hard

• Ruta Mehta

The rank of a bimatrix game ( A, B ) is defined as rank ( A + B ). Computing a Nash equilibrium (NE) of a rank-0, i.e., zero-sum game is equivalent to linear programming (von Neumann'28, Dantzig'51). In 2005, Kannan and Theobald gave an FPTAS for constant rank games, and asked if there exists a polynomial time algorithm to compute an exact NE. Adsul et. al. (2011) answered this question affirmatively for rank-1 games, leaving rank-2 and beyond unresolved.

STOC Conference 2014 Conference Paper

Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions

• Jugal Garg
• Ruta Mehta
• Vijay V. Vazirani

SODA Conference 2013 Conference Paper

Towards Polynomial Simplex-Like Algorithms for Market Equlibria

• Jugal Garg
• Ruta Mehta
• Milind A. Sohoni
• Nisheeth K. Vishnoi

STOC Conference 2012 Conference Paper

A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities

• Jugal Garg
• Ruta Mehta
• Milind A. Sohoni
• Vijay V. Vazirani

STOC Conference 2011 Conference Paper

Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm

• Bharat Adsul
• Jugal Garg
• Ruta Mehta
• Milind A. Sohoni

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 by Kannan and Theobald (SODA'07). 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. Our approach also provides new proofs of important classical results such as the existence and oddness of Nash equilibria, and the index theorem for bimatrix games. 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.