EAEshwar Ram Arunachaleswaran

Eshwar Ram Arunachaleswaran

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Eshwar Ram Arunachaleswaran has a total of 10 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    College Applications with Non-Homogeneous Application Costs

    by Eshwar Arunachaleswaran, Sampath Kannan, Rakesh Vohra

    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

    Swap Regret and Correlated Equilibria Beyond Normal-Form Games

    by Eshwar Ram Arunachaleswaran, Natalie Collina, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan


  • Open Access

    Learning to Play Against Unknown Opponents

    by Eshwar Ram Arunachaleswaran, Natalie Collina, Jon Schneider


  • Open Access

    Pareto-Optimal Algorithms for Learning in Games

    by Eshwar Ram Arunachaleswaran, Natalie Collina, Jon Schneider

    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

    by Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, Juba Ziani

    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.