Jugal Garg

Jugal Garg, Eklavya Sharma

We consider the problem of fairly dividing indivisible goods among agents with additive valuations. It is known that an Epistemic EFX and $2/3$-MMS allocation can be obtained using the Envy-Cycle-Elimination (ECE) algorithm. In this work, we explore whether this algorithm can be randomized to also ensure ex-ante proportionality. For two agents, we show that a randomized variant of ECE can compute an ex-post EFX and ex-ante envy-free allocation in near-linear time. However, for three agents, we show that several natural randomization methods for ECE fail to achieve ex-ante proportionality.

Jugal Garg, Edin Husić, Wenzheng Li et al.

For any $\varepsilon>0$, we give a simple, deterministic $(4+\varepsilon)$-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 + \varepsilon)$-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 a $(8+\varepsilon)$-approximation to the symmetric NSW problem under submodular valuations.

Jugal Garg, Yixin Tao, László A. Végh

We study the relationship between two central concepts in the allocation of divisible goods: competitive equilibrium (CE) and allocations that maximize Nash welfare, i.e., allocations where the weighted geometric mean of the utilities is maximal. When agents have homogeneous concave utility functions, these concepts coincide: the classical Eisenberg-Gale convex program that maximizes Nash welfare over feasible allocations yields a competitive equilibrium. However, they diverge for non-homogeneous utilities. From a computational perspective, maximizing Nash welfare amounts to solving a convex program for any concave utility functions, whereas computing CE becomes PPAD-hard already for separable piecewise linear concave (SPLC) utilities. We introduce the concept of Gale-substitute utility functions, an analogue of the weak gross substitutes (WGS) property for the so-called Gale demand system. For Gale-substitutes utilities, we show that any allocation maximizing Nash welfare provides an approximate-CE with surprisingly strong guarantees, where every agent gets at least half the maximum utility they can get at any CE, and is approximately envy-free. Gale-substitutes include utility functions where computing CE is PPAD hard, such as all separable concave utilities and the previously studied non-separable class of Leontief-free utilities. We introduce a broad new class of utility functions called generalized network utilities based on the generalized flow model. This class includes SPLC and Leontief-free utilities, and we show that all such utilities are Gale-substitutes. Conversely, although some agents may get much higher utility at a Nash welfare maximizing allocation than at a CE, we show a `price of anarchy' type result: for general concave utilities, every CE achieves at least $(1/e)^{1/e} > 0.69$ fraction of the maximum Nash welfare, and this factor is tight.

Bhaskar Ray Chaudhury, Jugal Garg, Eklavya Sharma et al.

We study revenue-optimal pricing in data markets with rational, budget-constrained buyers. Such a market offers multiple datasets for sale, and buyers aim to improve the accuracy of their prediction tasks by acquiring data bundles. The market's objective is to price datasets to maximize total revenue, considering that buyers with quasi-linear utilities choose their bundles optimally under budget constraints. We allow the buyers to purchase fractions of datasets, and the amount they pay is proportional to the fraction they receive. Although competitive equilibrium gives revenue-optimal pricing in rivalrous markets with quasi-linear buyers, we show that revenue maximization in data markets is APX-hard. Despite the hardness, we design a 2-approximation algorithm when datasets arrive online, and a $(1-1/e)^{-1}$-approximation algorithm for the offline setting.

Jugal Garg, Shayan Taherijam, Vijay V Vazirani

Our main contribution is a strongly polynomial algorithm for computing an equilibrium for the Arctic Auction, which is the quasi-linear extension of the linear Fisher market model. We build directly on Orlin's strongly polynomial algorithm for the linear Fisher market (Orlin, 2010). The first combinatorial polynomial algorithm for the linear Fisher market was based on the primal-dual paradigm (Devanur et al., 2008). This was followed by Orlin's scaling-based algorithms. The Arctic Auction (Klemperer 2018) was developed for the Government of Iceland to allow individuals to exchange blocked offshore assets. It is a variant of the product-mix auction (Klemperer 2008, 2010, 2018) that was designed for, and used by, the Bank of England, to allocate liquidity efficiently across banks pledging heterogeneous collateral of varying quality. Our work was motivated by the fact that banks often need to run Arctic Auctions under many different settings of the parameters in order to home in on the right one, making it essential to find a time-efficient algorithm for Arctic Auction.