About

Ruta Mehta is an Associate Professor of Computer Science at the University of Illinois at Urbana-Champaign, affiliated with the Siebel School of Computing and Data Science and the Coordinated Science Laboratory. She is a founding member of the AImpact Center at UIUC. Her academic background includes a Ph.D. in Computer Science and Engineering from the Indian Institute of Technology Bombay, where her thesis received the ACM India Doctoral Dissertation Award and the IIT-Bombay Excellence in Ph.D. Thesis Award. She also holds a Masters of Technology from IIT Bombay and a Bachelor of Engineering from Maharaja Saiyajirao University, Baroda. Her research focuses on theoretical computer science, particularly at the intersection of economics, game theory, and machine learning. She explores fundamental solution concepts from these fields through a computational lens, with interests in algorithmic game theory, mathematical economics, and the design of efficient and trustworthy systems. Recently, her work includes trustworthy machine learning systems, data-driven economies based on AI agents, and online and stochastic fair division. She has served on editorial boards, organized conferences, and received notable awards such as the NSF CAREER Award, the Simons-Berkeley Research Fellowship, and the Best Postdoctoral Award from the College of Computing at Georgia Tech. Her academic positions include roles as an assistant professor, postdoctoral fellow at UC Berkeley and Georgia Tech, and associate professor at UIUC, where she continues her research and teaching.

Research topics

• Mathematical economics
• Combinatorics
• Mathematics

Selected publications

• Tit-for-tat strategies drive growth and inequality in production economies

  Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · 2025-01-01

  articleOpen access

  We consider production economies where multiple agents make goods according to their inherent production recipe. Daily agents bring goods to the market along with a monetary budget that they allocate across these goods in competitive bids. Goods are distributed in proportion to the bids they attract, with sellers collecting the corresponding revenues. Agents then use their acquired bundles as raw ingredients for the next day’s production. We analyse a dynamic known as proportional response, where agents adjust their bids on goods proportionally to returns on past investments: a tit-for-tat like market behaviour. We show these dynamics lead to growth of the economy, whenever growth is feasible within the parameters of the model. The dynamics implicitly learn a key global feature of the network—the most efficient production cycles—through local interactions among the agents who communicate only with their immediate neighbours, with information flowing across the network edges. However, the dynamics also lead to unbounded inequality, i.e. very rich and very poor agents emerge and the gaps between their fortunes expand over time. We analyse several other phenomena, such as the existence of free-riding in star networks, where an agent may have growing fortune without participating in any efficient production cycle if they have strong enough connections with the centre.

  PublisherDOI

• Minimization I.I.D. Prophet Inequality via Extreme Value Theory: A Unified Approach

  arXiv (Cornell University) · 2024-11-29

  preprintOpen accessSenior author

  The I.I.D. Prophet Inequality is a fundamental problem where, given $n$ independent random variables $X_1,\dots,X_n$ drawn from a known distribution $\mathcal{D}$, one has to decide at every step $i$ whether to stop and accept $X_i$ or discard it forever and continue. The goal is to maximize or minimize the selected value and compete against the all-knowing prophet. For maximization, a tight constant-competitive guarantee of $\approx 0.745$ is well-known (Correa et al, 2019), whereas minimization is qualitatively different: the optimal constant is distribution-dependent and can be arbitrarily large (Livanos and Mehta, 2024). In this paper, we provide a novel framework via the lens of Extreme Value Theory to analyze optimal threshold algorithms. We show that the competitive ratio for the minimization setting has a closed form described by a function $Λ$, which depends only on the extreme value index $γ$; in particular, it corresponds to $Λ(γ)$ for $γ\leq 0$. Despite the contrast of maximization and minimization, our framework turns out to be universal and we recover the results of (Kennedy and Kertz, 1991) for maximization as well. Surprisingly, the optimal competitive ratio for maximization is given by the same function $Λ(γ)$, but for $γ\geq 0$. Along the way, we obtain several results on the algorithm and the prophet's objectives from the perspective of extreme value theory, which might be of independent interest. We next study single-threshold algorithms for minimization. Using extreme value theory, we generalize the results of (Livanos and Mehta, 2024) which hold only for special classes of distributions, and obtain poly-logarithmic in $n$ guarantees. Finally, we consider the $k$-multi-unit prophet inequality for minimization and show that there exist constant-competitive single-threshold algorithms when $k \geq \log{n}$.

  PublisherOA PDFDOI

• Monotone Contractions

  arXiv (Cornell University) · 2024-11-15

  preprintOpen access

  We study functions $f : [0, 1]^d \rightarrow [0, 1]^d$ that are both monotone and contracting, and we consider the problem of finding an $\varepsilon$-approximate fixed point of $f$. We show that the problem lies in the complexity class UEOPL. We give an algorithm that finds an $\varepsilon$-approximate fixed point of a three-dimensional monotone contraction using $O(\log (1/\varepsilon))$ queries to $f$. We also give a decomposition theorem that allows us to use this result to obtain an algorithm that finds an $\varepsilon$-approximate fixed point of a $d$-dimensional monotone contraction using $O((c \cdot \log (1/\varepsilon))^{\lceil d / 3 \rceil})$ queries to $f$ for some constant $c$. Moreover, each step of both of our algorithms takes time that is polynomial in the representation of $f$. These results are strictly better than the best-known results for functions that are only monotone, or only contracting. All of our results also apply to Shapley stochastic games, which are known to be reducible to the monotone contraction problem. Thus we put Shapley games in UEOPL, and we give a faster algorithm for approximating the value of a Shapley game.

  PublisherOA PDFDOI

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

  Proceedings of the AAAI Conference on Artificial Intelligence · 2024-03-24 · 1 citations

  articleOpen accessSenior author

  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.

  PublisherOA PDFDOI

• Competitive Equilibrium for Chores: from Dual Eisenberg-Gale to a Fast, Greedy, LP-based Algorithm

  arXiv (Cornell University) · 2024-02-16

  preprintOpen access

  We study the computation of competitive equilibrium for Fisher markets with $n$ agents and $m$ divisible chores. Competitive equilibria for chores are known to correspond to the nonzero KKT points of a program that minimizes the product of agent disutilities, which is a non-convex program whose zero points foil iterative optimization methods. We introduce a dual-like analogue of this program, and show that a simple modification to our "dual" program avoids such zero points, while retaining the correspondence between KKT points and competitive equilibria. This allows, for the first time ever, application of iterative optimization methods over a convex region for computing competitive equilibria for chores. We next introduce a greedy Frank-Wolfe algorithm for optimization over our program and show a new state-of-the-art convergence rate to competitive equilibrium. Moreover, our method is significantly simpler than prior methods: each iteration of our method only requires solving a simple linear program. We show through numerical experiments that our method is extremely practical: it easily solves every instance we tried, including instances with hundreds of agents and up to 1000 chores, usually in 10-30 iterations, is simple to implement, and has no numerical issues.

  PublisherOA PDFDOI

• On the structure of EFX orientations on graphs

  arXiv (Cornell University) · 2024-04-21

  preprintOpen accessSenior author

  Fair division is the problem of allocating a set of items among agents in a fair manner. One of the most sought-after fairness notions is envy-freeness (EF), requiring that no agent envies another's allocation. When items are indivisible, it ceases to exist, and envy-freeness up to any good (EFX) emerged as one of its strongest relaxations. The existence of EFX allocations is arguably the biggest open question within fair division. Recently, Christodoulou, Fiat, Koutsoupias, and Sgouritsa (EC 2023) showed that EFX allocations exist for the case of graphical valuations where an instance is represented by a graph: nodes are agents, edges are goods, and each agent values only her incident edges. On the other hand, they showed NP-hardness for checking the existence of EFX orientation where every edge is allocated to one of its incident vertices, and asked for a characterization of graphs that exhibit EFX orientation regardless of the assigned valuations. In this paper, we make significant progress toward answering their question. We introduce the notion of strongly EFX orientable graphs -- graphs that have EFX orientations regardless of how much agents value the edges. We show a surprising connection between this property and the chromatic number $χ(G)$ of the graph $G$. In particular, we show that graphs with $χ(G)\le 2$ are strongly EFX orientable, and those with $χ(G)>3$ are not strongly EFX orientable. We provide examples of strongly EFX orientable and non-strongly EFX orientable graphs of $χ(G)=3$ to prove tightness. Finally, we give a complete characterization of strong EFX orientability when restricted to binary valuations.

  PublisherOA PDFDOI

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

  arXiv (Cornell University) · 2023-12-13 · 1 citations

  preprintOpen accessSenior author

  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. Further, the equilibrium computation problem, which is polynomial-time for additive valuations, becomes intractable for SPLC. 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 current 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 might be of independent interest.

  PublisherOA PDFDOI

• Fair and Efficient Allocation of Indivisible Chores with Surplus

  2023-08-01 · 2 citations

  articleOpen accessSenior author

  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.

  PublisherOA PDFDOI

• Fair and Efficient Allocation of Indivisible Chores with Surplus

  arXiv (Cornell University) · 2023-05-08

  preprintOpen accessSenior author

  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 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.

  PublisherOA PDFDOI

• Approximating APS under Submodular and XOS valuations with Binary Marginals

  arXiv (Cornell University) · 2023-12-13

  preprintOpen accessSenior author

  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. Babaioff et al. studied the problem under additive valuations, and asked (i) how large can the APS value be compared to the MMS value? and (ii) 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, we get 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 show that under binary XOS valuations, $MMS \leq APS \leq 2 \cdot MMS + 1$. Further, we show that this is almost the tightest bound we can get using MMS, by giving an instance where $APS \geq 2 \cdot MMS$. The upper bound on APS, implies a ~0.1222-approximation for APS under binary XOS valuations. And the lower bound implies the non-existence 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.

  PublisherOA PDFDOI

Recent grants

• NSF Student Travel Grant for 2018 AGT Mentoring Workshop Co-Located with Economics and Computation (EC)

  NSF · $10k · 2018–2019

• CAREER: Equilibrium Computation and Other Total Search Problems

  NSF · $500k · 2018–2024

Frequent coauthors

• Jugal Garg

  University of Illinois Urbana-Champaign

  45 shared

• Vijay V. Vazirani

  University of California, Irvine

  32 shared

• Shant Boodaghians

  University of Illinois Urbana-Champaign

  23 shared

• Sadra Yazdanbod

  Google (United States)

  19 shared

• Milind Sohoni

  15 shared

• Yishay Mansour

  12 shared

• Federico Fusco

  Sapienza University of Rome

  12 shared

• Stefano Leonardi

  12 shared

Labs

• Siebel School of Computing and Data SciencePI

Awards & honors

• NSF CAREER Award
• Simons-Berkeley Research Fellowship
• Best Postdoctoral Award (given by CoC@GT)
• ACM India Doctoral Dissertation Award
• IIT-Bombay Excellence in Ph.D. Thesis Award