Eshwar Ram Arunachaleswaran
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Eshwar Ram Arunachaleswaran has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Jon Schneider
Google Research, New York City, USA
3 shared publications - Natalie Collina
University of Pennsylvania, Philadelphia, USA
3 shared publications - Aaron Roth
University of Pennsylvania
1 shared publication - Balasubramanian Sivan
Google Research, New York City, USA
1 shared publication - Juba Ziani
Industrial & Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia, USA
1 shared publication - Mehryar Mohri
Google Research, New Brunswick, USA
1 shared publication
Latest Publications
- Open Access
- 17 June 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Economics and Computation
- Vol. 14 (2) , 1-14
College Applications with Non-Homogeneous Application Costs
A college applicant submits costly applications to a set of colleges while uncertain which colleges will admit her. If she knows the application costs, her utility of attending each college, and her probability of being admitted to each college, which subset of colleges should she apply to maximize her expected net payoff? The problem is an instance of non-monotone submodular maximization. There are two principal variants in the literature, one where the events of getting into different colleges are independent, and the other where they are correlated. The main results in the literature handle cases where all application costs are the same. We provide exact and approximate algorithms for the problem when college application costs vary.
- 17 June 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Economics and Computation
- Vol. 14 (2) , 1-14
Open AccessCollege Applications with Non-Homogeneous Application Costs
A college applicant submits costly applications to a set of colleges while uncertain which colleges will admit her. If she knows the application costs, her utility of attending each college, and her probability of being admitted to each college, which subset of colleges should she apply to maximize her expected net payoff? The problem is an instance of non-monotone submodular maximization. There are two principal variants in the literature, one where the events of getting into different colleges are independent, and the other where they are correlated. The main results in the literature handle cases where all application costs are the same. We provide exact and approximate algorithms for the problem when college application costs vary.
- Open Access
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 130-157
Swap Regret and Correlated Equilibria Beyond Normal-Form Games
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 130-157
Open AccessSwap Regret and Correlated Equilibria Beyond Normal-Form Games
- Open Access
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 478-504
Learning to Play Against Unknown Opponents
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 478-504
Open AccessLearning to Play Against Unknown Opponents
- Open Access
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 490-510
Pareto-Optimal Algorithms for Learning in Games
We study the problem of characterizing optimal learning algorithms for playing repeated games against an adversary with unknown payoffs. In this problem, the first player (called the learner) commits to a learning algorithm against a second player (called the optimizer), and the optimizer best-responds by choosing the optimal dynamic strategy for their (unknown but well-defined) payoff. Classic learning algorithms (such as no-regret algorithms) provide some counterfactual guarantees for the learner, but might perform much more poorly than other learning algorithms against particular optimizer payoffs. In this paper, we introduce the notion of asymptotically Pareto-optimal learning algorithms. Intuitively, if a learning algorithm is Pareto-optimal, then there is no other algorithm which performs asymptotically at least as well against all optimizers and performs strictly better (by at least Ω(T)) against some optimizer. We show that well-known no-regret algorithms such as Multiplicative Weights and Follow The Regularized Leader are Pareto-dominated. However, while no-regret is not enough to ensure Pareto-optimality, we show that a strictly stronger property, no-swap-regret, is a sufficient condition for Pareto-optimality. Proving these results requires us to address various technical challenges specific to repeated play, including the fact that there is no simple characterization of how optimizers who are rational in the long-term best-respond against a learning algorithm over multiple rounds of play. To address this, we introduce the idea of the asymptotic menu of a learning algorithm: the convex closure of all correlated distributions over strategy profiles that are asymptotically implementable by an adversary. Interestingly, we show that all no-swap-regret algorithms share the same asymptotic menu, implying that all no-swap-regret algorithms are "strategically equivalent".
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 490-510
Open AccessPareto-Optimal Algorithms for Learning in Games
We study the problem of characterizing optimal learning algorithms for playing repeated games against an adversary with unknown payoffs. In this problem, the first player (called the learner) commits to a learning algorithm against a second player (called the optimizer), and the optimizer best-responds by choosing the optimal dynamic strategy for their (unknown but well-defined) payoff. Classic learning algorithms (such as no-regret algorithms) provide some counterfactual guarantees for the learner, but might perform much more poorly than other learning algorithms against particular optimizer payoffs. In this paper, we introduce the notion of asymptotically Pareto-optimal learning algorithms. Intuitively, if a learning algorithm is Pareto-optimal, then there is no other algorithm which performs asymptotically at least as well against all optimizers and performs strictly better (by at least Ω(T)) against some optimizer. We show that well-known no-regret algorithms such as Multiplicative Weights and Follow The Regularized Leader are Pareto-dominated. However, while no-regret is not enough to ensure Pareto-optimality, we show that a strictly stronger property, no-swap-regret, is a sufficient condition for Pareto-optimality. Proving these results requires us to address various technical challenges specific to repeated play, including the fact that there is no simple characterization of how optimizers who are rational in the long-term best-respond against a learning algorithm over multiple rounds of play. To address this, we introduce the idea of the asymptotic menu of a learning algorithm: the convex closure of all correlated distributions over strategy profiles that are asymptotically implementable by an adversary. Interestingly, we show that all no-swap-regret algorithms share the same asymptotic menu, implying that all no-swap-regret algorithms are "strategically equivalent".
- Open Access
Pipeline Interventions
We introduce the \emph{pipeline intervention} problem, defined by a layered directed acyclic graph and a set of stochastic matrices governing transitions between successive layers. The graph is a stylized model for how people from different populations are presented opportunities, eventually leading to some reward. In our model, individuals are born into an initial position (i.e. some node in the first layer of the graph) according to a fixed probability distribution, and then stochastically progress through the graph according to the transition matrices, until they reach a node in the final layer of the graph; each node in the final layer has a \emph{reward} associated with it. The pipeline intervention problem asks how to best make costly changes to the transition matrices governing people's stochastic transitions through the graph, subject to a budget constraint. We consider two objectives: social welfare maximization, and a fairness-motivated maximin objective that seeks to maximize the value to the population (starting node) with the \emph{least} expected value. We consider two variants of the maximin objective that turn out to be distinct, depending on whether we demand a deterministic solution or allow randomization. For each objective, we give an efficient approximation algorithm (an additive FPTAS) for constant width networks. We also tightly characterize the "price of fairness" in our setting: the ratio between the highest achievable social welfare and the highest social welfare consistent with a maximin optimal solution. Finally we show that for polynomial width networks, even approximating the maximin objective to any constant factor is NP hard, even for networks with constant depth. This shows that the restriction on the width in our positive results is essential.
Open AccessPipeline Interventions
We introduce the \emph{pipeline intervention} problem, defined by a layered directed acyclic graph and a set of stochastic matrices governing transitions between successive layers. The graph is a stylized model for how people from different populations are presented opportunities, eventually leading to some reward. In our model, individuals are born into an initial position (i.e. some node in the first layer of the graph) according to a fixed probability distribution, and then stochastically progress through the graph according to the transition matrices, until they reach a node in the final layer of the graph; each node in the final layer has a \emph{reward} associated with it. The pipeline intervention problem asks how to best make costly changes to the transition matrices governing people's stochastic transitions through the graph, subject to a budget constraint. We consider two objectives: social welfare maximization, and a fairness-motivated maximin objective that seeks to maximize the value to the population (starting node) with the \emph{least} expected value. We consider two variants of the maximin objective that turn out to be distinct, depending on whether we demand a deterministic solution or allow randomization. For each objective, we give an efficient approximation algorithm (an additive FPTAS) for constant width networks. We also tightly characterize the "price of fairness" in our setting: the ratio between the highest achievable social welfare and the highest social welfare consistent with a maximin optimal solution. Finally we show that for polynomial width networks, even approximating the maximin objective to any constant factor is NP hard, even for networks with constant depth. This shows that the restriction on the width in our positive results is essential.