About

Jugal Garg is an Associate Professor in the Department of Industrial and Enterprise Systems Engineering and an Affiliate in the Department of Computer Science at the University of Illinois at Urbana-Champaign. His research focuses on algorithms and complexity for fundamental problems in economics and computation, with a particular emphasis on allocation problems arising in fair division and general equilibrium theory. Jugal received his BTech and PhD in Computer Science from IIT-Bombay. He subsequently held postdoctoral positions at the Algorithms and Randomness Center at Georgia Tech and the Algorithms and Complexity group at the Max-Planck-Institut für Informatik in Saarbrücken. Throughout his career, Jugal Garg has been recognized with several prestigious awards, including the NSF CRII Award, the NSF CAREER Award, the Exemplary Theory Paper Award at ACM EC 2020, the INFORMS Koopman Prize in 2021, and the Dean's Award for Excellence in Research in 2022. He has also been honored for his teaching with the James Franklin Sharp Outstanding Teaching Award in 2019 and the ISE Department Head Teaching Award in 2023, and has been featured multiple times in the List of Teachers Ranked as Excellent. Jugal Garg's work contributes significantly to the understanding and development of algorithms that address complex economic models and fair division challenges. His research integrates theoretical computer science with economic theory, advancing knowledge in market equilibrium computation, Nash social welfare approximation, and fair allocation of indivisible goods and chores. His academic journey and achievements reflect a strong commitment to both research excellence and quality education.

Research topics

• Computer Science
• Mathematics
• Mathematical economics
• Combinatorics
• Epistemology
• Mathematical optimization
• Philosophy
• Data Mining
• Algorithm
• Economics
• Applied mathematics

Selected publications

• Data Pricing via Competitive Equilibrium

  2026-04-09

  articleOpen access

  Data powers almost everything we experience on the web today---from the recommendations and ads we see to the AI systems and online marketplaces that shape our digital interactions. The increasing demand for high-quality data has given rise to platforms that facilitate the buying and selling of data. A key practical challenge in such markets is determining how to price data. Competitive equilibrium (CE), a foundational concept in classical market economics, determines prices for rivalrous goods by matching their supply and demand. In this work, we initiate the study of CE in data markets, explicitly incorporating the role of data in improving predictive performance in buyers' utility functions, and the non-rival nature of data by adapting the standard market-clearing condition to allow the simultaneous allocation of data records to multiple buyers. We analyze the existence, structure, and computation of CE in such data markets. We establish that CE always exists, and almost all instances admit a unique and rational equilibrium price vector. In general, however, there could be a non-convex set of prices, which rules out convex-programming approaches for finding a CE. Despite these challenges, we design an FPTAS for computing approximate equilibria using a Walrasian-style price adjustment algorithm. Our framework opens avenues for studying richer buyer utilities under correlated data sellers, and deeper structural and algorithmic aspects of data markets.

  PublisherDOI

• Approximating Nash Social Welfare by Matching and Local Search

  Journal of the ACM · 2026-04-07 · 4 citations

  preprintOpen access1st authorCorresponding

  For any ε > 0, we give a simple, deterministic (4 + ε)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents’ valuations, and give an e( ω + 2 + ε)-approximation if the ratio between the largest weight and the average weight is at most ω . We also show that the 1/2-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time that is both 1/2-EFX and an (8 + ε)-approximation to the symmetric NSW problem under submodular valuations.

  PublisherDOI

• Designing Truthful Mechanisms for Asymptotic Fair Division

  ArXiv.org · 2025-12-11

  preprintOpen access1st authorCorresponding

  We study the problem of fairly allocating a set of $m$ goods among $n$ agents in the asymptotic setting, where each item's value for each agent is drawn from an underlying joint distribution. Prior works have shown that if this distribution is well-behaved, then an envy-free allocation exists with high probability when $m=Ω(n\log{n})$ [Dickerson et al., 2014]. Under the stronger assumption that item values are independently and identically distributed (i.i.d.) across agents, this requirement improves to $m=Ω(n\log{n}/\log{\log{n}})$, which is tight [Manurangsi and Suksompong, 2021]. However, these results rely on non-strategyproof mechanisms, such as maximum-welfare allocation or the round-robin algorithm, limiting their applicability in settings with strategic agents. In this work, we extend the theory to a broader, more realistic class of joint value distributions, allowing for correlations among agents, atomicity, and unequal probabilities of having the highest value for an item. We show that envy-free allocations continue to exist with a high probability when $m=Ω(n\log{n})$. More importantly, we give a new randomized mechanism that is truthful in expectation, efficiently implementable in polynomial time, and outputs envy-free allocations with high probability, answering an open question posed by [Manurangsi and Suksompong, 2017]. We further extend our mechanism to settings with asymptotic weighted fair division and multiple agent types and good types, proving new results in each case.

  PublisherOA PDFDOI

• Proportional and Pareto-Optimal Allocation of Chores with Subsidy

  2025-10-11

  preprintOpen access1st authorCorresponding

  We consider the problem of allocating m indivisible chores among n agents with possibly different weights, aiming for a solution that is both fair and efficient. Specifically, we focus on the classic fairness notion of proportionality and efficiency notion of Pareto-optimality. Since proportional allocations may not always exist in this setting, we allow the use of subsidies (monetary compensation to agents) to ensure agents are proportionally-satisfied, and aim to minimize the total subsidy required. Wu and Zhou (WINE 2024) showed that when each chore has disutility at most 1, a total subsidy of at most n/3 - 1/6 is sufficient to guarantee proportionality. However, their approach is based on a complex technique, which does not guarantee economic efficiency -- a key desideratum in fair division.

  PublisherOA PDFDOI

• Constant-Factor EFX Exists for Chores

  2025-06-15 · 2 citations

  article1st authorCorresponding
  PublisherDOI

• Existence of 2-EFX Allocations of Chores

  ArXiv.org · 2025-07-25

  preprintOpen access1st authorCorresponding

  We study the fair division of indivisible chores among agents with additive disutility functions. We investigate the existence of allocations satisfying the popular fairness notion of envy-freeness up to any chore (EFX), and its multiplicative approximations. The existence of $4$-EFX allocations was recently established by Garg, Murhekar, and Qin (2025). We improve this guarantee by proving the existence of $2$-EFX allocations for all instances with additive disutilities. This approximation was previously known only for restricted instances such as bivalued disutilities (Lin, Wu, and Zhou (2025)) or three agents (Afshinmehr, Ansaripour, Danaei, and Mehlhorn (2024)). We obtain our result by providing a general framework for achieving approximate-EFX allocations. The approach begins with a suitable initial allocation and performs a sequence of local swaps between the bundles of envious and envied agents. For our main result, we begin with an initial allocation that satisfies envy-freeness up to one chore (EF1) and Pareto-optimality (PO); the existence of such an allocation was recently established in a major breakthrough by Mahara (2025). We further demonstrate the strength and generality of our framework by giving simple and unified proofs of existing results, namely (i) $2$-EFX for bivalued instances, (ii) 2-EFX for three agents, (iii) EFX when the number of chores is at most twice the number of agents, and (iv) $4$-EFX for all instances. We expect this framework to have broader applications in approximate-EFX due to its simplicity and generality.

  PublisherOA PDFDOI

• Tight Efficiency Bounds for the Probabilistic Serial and Related Mechanisms

  ArXiv.org · 2025-07-04

  preprintOpen access1st authorCorresponding

  The Probabilistic Serial (PS) mechanism -- also known as the simultaneous eating algorithm -- is a canonical solution for the random assignment problem under ordinal preferences. It guarantees envy-freeness and ordinal efficiency in the resulting random assignment. However, under cardinal preferences, its efficiency may degrade significantly: it is known that PS may yield allocations that are $Ω(\ln{n})$-worse than Pareto optimal, but whether this bound is tight remained an open question. Our first result resolves this question by proving that the PS mechanism guarantees $(\ln n+1)$-approximate Pareto efficiency under cardinal preferences. The key part of our analysis shows that PS achieves a logarithmic $(\ln n + 1)$-approximation to the maximum Nash welfare, in stark contrast to the $O(\sqrt{n})$ loss that can arise in utilitarian social welfare. Our results also extend to the more general submodular setting introduced by Fujishige, Sano, and Zhan (ACM TEAC 2018). In addition, we present a polynomial-time algorithm that computes an allocation which is envy-free and $e^{1/e}$-approximately Pareto-efficient, answering an open question posed by Tröbst and Vazirani (EC 2024). The PS mechanism also applies to the allocation of chores instead of goods. We prove that it guarantees an $n$-approximately Pareto-efficient allocation in this setting, and that this bound is asymptotically tight. This result provides the first known approximation guarantee for computing a fair and efficient allocation in the random assignment problem with chores under cardinal preferences.

  PublisherOA PDFDOI

• On the Theoretical Foundations of Data Exchange Economies

  2025-07-02 · 2 citations

  articleOpen access

  Organizations increasingly seek to share and access datasets to improve their ML models and derive insights. Despite the immense demand for quality data, data exchange and collaboration have not reached their full potential. One of the key reasons is the lack of reciprocity, where some participants perceive their contribution to others to be of higher value than what they receive in return.

  PublisherOA PDFDOI

• Approximating Competitive Equilibrium by Nash Welfare

  SSRN Electronic Journal · 2025-01-01

  preprintOpen access1st authorCorresponding
  PublisherDOI

• Proportionally Fair Makespan Approximation

  Proceedings of the AAAI Conference on Artificial Intelligence · 2025-04-11 · 1 citations

  articleOpen access

  We study fair mechanisms for the classic job scheduling problem on unrelated machines with the objective of minimizing the makespan. This problem is equivalent to minimizing the egalitarian social cost in the fair division of chores. The two prevalent fairness notions in the fair division literature are envy-freeness and proportionality. Prior work has established that no envy-free mechanism can provide better than an Ω(log m / log log m)-approximation to the optimal makespan, where m is the number of machines, even when payments to the machines are allowed. In strong contrast to this impossibility, our main result demonstrates that there exists a proportional mechanism (with payments) that achieves a 3/2-approximation to the optimal makespan, and this ratio is tight. To prove this result, we provide a full characterization of allocation functions that can be made proportional with payments. Furthermore, we show that for instances with normalized costs, there exists a proportional mechanism that achieves the optimal makespan. We conclude with important directions for future research concerning other fairness notions, including relaxations of envy-freeness. Notably, we show that the technique leading to the impossibility result for envy-freeness does not extend to its relaxations.

  PublisherDOI

Recent grants

• CRII: AF: Strongly Polynomial Algorithms for Market Equilibria with Applications to Network Flows and Nash Social Welfare

  NSF · $175k · 2018–2020

• CAREER: AF: New Algorithmic Foundations for Fair Division through Competitive Equilibrium

  NSF · $505k · 2020–2025

Frequent coauthors

• Ruta Mehta

  45 shared

• Kurt Mehlhorn

  Max Planck Institute for Informatics

  27 shared

• László A. Végh

  London School of Economics and Political Science

  24 shared

• Martin Hoefer

  RWTH Aachen University

  23 shared

• Vijay V. Vazirani

  University of California, Irvine

  20 shared

• Peter McGlaughlin

  Goethe University Frankfurt

  18 shared

• Hannaneh Akrami

  Max Planck Institute for Informatics

  17 shared

• Aniket Murhekar

  University of Illinois Urbana-Champaign

  15 shared