Eshwar Ram Arunachaleswaran

SODA Conference 2025 Conference Paper

An Elementary Predictor Obtaining Distance to Calibration

• Eshwar Ram Arunachaleswaran
• Natalie Collina
• Aaron Roth 0001
• Mirah Shi

ICLR Conference 2024 Conference Paper

Oracle Efficient Algorithms for Groupwise Regret

• Krishna Acharya
• Eshwar Ram Arunachaleswaran
• Sampath Kannan
• Aaron Roth 0001
• Juba Ziani

We study the problem of online prediction, in which at each time step $t \in \{1,2, \cdots T\}$, an individual $x_t$ arrives, whose label we must predict. Each individual is associated with various groups, defined based on their features such as age, sex, race etc., which may intersect. Our goal is to make predictions that have regret guarantees not just overall but also simultaneously on each sub-sequence comprised of the members of any single group. Previous work such as [Blum & Lykouris][1] and [Lee et al][2] provide attractive regret guarantees for these problems; however, these are computationally intractable on large model classes (e.g., the set of all linear models, as used in linear regression). We show that a simple modification of the sleeping experts technique of [Blum & Lykouris][1] yields an efficient *reduction* to the well-understood problem of obtaining diminishing external regret *absent group considerations*. Our approach gives similar regret guarantees compared to [Blum & Lykouris][1]; however, we run in time linear in the number of groups, and are oracle-efficient in the hypothesis class. This in particular implies that our algorithm is efficient whenever the number of groups is polynomially bounded and the external-regret problem can be solved efficiently, an improvement on [Blum & Lykouris][1]'s stronger condition that the model class must be small. Our approach can handle online linear regression and online combinatorial optimization problems like online shortest paths. Beyond providing theoretical regret bounds, we evaluate this algorithm with an extensive set of experiments on synthetic data and on two real data sets --- Medical costs and the Adult income dataset, both instantiated with intersecting groups defined in terms of race, sex, and other demographic characteristics. We find that uniformly across groups, our algorithm gives substantial error improvements compared to running a standard online linear regression algorithm with no groupwise regret guarantees.

AAMAS Conference 2023 Conference Paper

Efficient Stackelberg Strategies for Finitely Repeated Games

• Natalie Collina
• Eshwar Ram Arunachaleswaran
• Michael Kearns

We study Stackelberg equilibria in finitely repeated games, where the leader commits to a strategy that picks actions in each round and can be adaptive to the history of play (i. e. they commit to an algorithm). In particular, we study static repeated games with no discounting. We give efficient algorithms for finding approximate Stackelberg equilibria in this setting, along with rates of convergence depending on the time horizonT. In many cases, these algorithms allow the leader to do much better on average than they can in the single-round Stackelberg. We give two algorithms, one computing strategies with an optimal 1 T rate at the expense of an exponential dependence on the number of actions, and another (randomized) approach computing strategies with no dependence on the number of actions but a worse dependence on T of 1 T 0. 25. Both algorithms build upon a linear program to produce simple automata leader strategies and induce corresponding automata best-responses for the follower. We complement these results by showing that approximating the Stackelberg value in three-player finite-horizon repeated games is a computationally hard problem via a reduction from balanced vertex cover.

AAAI Conference 2019 Conference Paper

Fair Division with a Secretive Agent

• Eshwar Ram Arunachaleswaran
• Siddharth Barman
• Nidhi Rathi

We study classic fair-division problems in a partial information setting. This paper respectively addresses fair division of rent, cake, and indivisible goods among agents with cardinal preferences. We will show that, for all of these settings and under appropriate valuations, a fair (or an approximately fair) division among n agents can be efficiently computed using only the valuations of n − 1 agents. The nth (secretive) agent can make an arbitrary selection after the division has been proposed and, irrespective of her choice, the computed division will admit an overall fair allocation. For the rent-division setting we prove that well-behaved utilities of n − 1 agents suffice to find a rent division among n rooms such that, for every possible room selection of the secretive agent, there exists an allocation (of the remaining n − 1 rooms among the n − 1 agents) which ensures overall envy freeness (fairness). We complement this existential result by developing a polynomial-time algorithm for the case of quasilinear utilities. In this partial information setting, we also develop efficient algorithms to compute allocations that are envy-free up to one good (EF1) and ε-approximate envy free. These two notions of fairness are applicable in the context of indivisible goods and divisible goods (cake cutting), respectively. One of the main technical contributions of this paper is the development of novel connections between different fairdivision paradigms, e. g. , we use our existential results for envy-free rent-division to develop an efficient EF1 algorithm.

SODA Conference 2019 Conference Paper

Fully Polynomial-Time Approximation Schemes for Fair Rent Division

• Eshwar Ram Arunachaleswaran
• Siddharth Barman
• Nidhi Rathi