About

Éva Tardos is the Jacob Gould Schurman Professor of Computer Science in the Department of Computer Science at Cornell University. She earned her Dipl.Math. in 1981 and Ph.D. in 1984 from Eötvös University, Budapest, Hungary. Her research interests lie in algorithms and algorithmic game theory, a subarea of theoretical computer science focused on designing systems and algorithms for selfish users. Her research focuses on algorithms and games on networks and systems involving strategic behavior of users.

Research topics

• Computer science
• Mathematics
• Mathematical optimization
• Mathematical economics
• Combinatorics

Selected publications

• Robust Equilibria in Shared Resource Allocation via Strengthening Border’s Theorem

  Society for Industrial and Applied Mathematics eBooks · 2026-01-01

  book-chapterSenior author

  We consider repeated allocation of a shared resource via a non-monetary mechanism, wherein a single item must be allocated to one of multiple agents in each round. We assume that each agent has i.i.d. values for the item across rounds, and additive utilities. Past work on this problem has proposed mechanisms where agents can get one of two kinds of guarantees: (\(i\)) (approximate) Bayes-Nash equilibria via linkage-based mechanisms which need extensive knowledge of the value distributions, and (\(ii\)) simple distribution-agnostic mechanisms with robust utility guarantees for each individual agent, which are worse than the Nash outcome, but hold irrespective of how others behave (including possibly collusive behavior). Recent work has hinted at barriers to achieving both simultaneously. Our work however establishes this is not the case, by proposing the first mechanism in which each agent has a natural strategy that is both a Bayes-Nash equilibrium and also comes with strong robust guarantees for individual agent utilities. Our mechanism comes out of a surprising connection between the online shared resource allocation problem and implementation theory, and uses a surprising strengthening of Border’s theorem. In particular, we show that establishing robust equilibria in this setting reduces to showing that a particular subset of the Border polytope is non-empty. We establish this via a novel joint Schurconvexity argument. This strengthening of Border’s criterion for obtaining a stronger conclusion is of independent technical interest, as it may prove useful in other settings.

  PublisherDOI

• Approximately Stationary Bandits with Knapsacks

  Mathematics of Operations Research · 2025-12-18

  articleSenior author

  Bandits with knapsacks (BwK), the generalization of the multiarmed bandits problem under global budget constraints, has received a lot of attention in recent years. It has numerous applications, including dynamic pricing, repeated auctions, ad allocation, network scheduling, etc. Previous work focuses on one of the two extremes: stochastic BwK in which the rewards and consumptions of the resources of each round are sampled from an independent and identical distribution and adversarial BwK in which these parameters are picked by an adversary. Achievable guarantees in the two cases exhibit a massive gap: no-regret learning is achievable in the stochastic case, but in the adversarial case, only competitive ratio style guarantees are achievable, in which the competitive ratio depends on either the budget or both the time and the number of resources. What makes this gap so vast is that, in adversarial BwK, the guarantees get worse in the typical case when the budget is more binding. Whereas best of both worlds–type algorithms are known (single algorithms that provide the best achievable guarantee in each extreme case), their known theoretical bounds degrade to the adversarial case as soon as the environment is not fully stochastic. Our work aims to bridge this gap, offering guarantees for a workload that is not exactly stochastic but is also not worst case. We define a condition, approximately stationary BwK, that parameterizes how close to stochastic or adversarial an instance is. Based on these parameters, we explore what is the best competitive ratio attainable in BwK. We explore two algorithms that are oblivious to the values of the parameters but guarantee competitive ratios that smoothly transition between the best possible guarantees in the two extreme cases, depending on the values of the parameters. Our guarantees offer great improvement over the adversarial guarantee, especially when the available budget is small. We also prove bounds on the achievable guarantee, showing that our results are approximately tight when the budget is small. Funding: This work was supported by the Air Force Office of Scientific Research [Grants FA9550-19-1-0183, FA9550-23-1-0068], the U.S. Department of Defense (National Defense Science & Engineering Graduate (N), and the Alexander S. Onassis Public Benefit Foundation [Grant F ZS 068-1/2022-2023].

  PublisherDOI

• Robust Equilibria in Shared Resource Allocation via Strengthening Border's Theorem

  ArXiv.org · 2025-05-16

  preprintOpen accessSenior author

  We consider repeated allocation of a shared resource via a non-monetary mechanism, wherein a single item must be allocated to one of multiple agents in each round. We assume that each agent has i.i.d. values for the item across rounds, and additive utilities. Past work on this problem has proposed mechanisms where agents can get one of two kinds of guarantees: $(i)$ (approximate) Bayes-Nash equilibria via linkage-based mechanisms which need extensive knowledge of the value distributions, and $(ii)$ simple distribution-agnostic mechanisms with robust utility guarantees for each individual agent, which are worse than the Nash outcome, but hold irrespective of how others behave (including possibly collusive behavior). Recent work has hinted at barriers to achieving both simultaneously. Our work however establishes this is not the case, by proposing the first mechanism in which each agent has a natural strategy that is both a Bayes-Nash equilibrium and also comes with strong robust guarantees for individual agent utilities. Our mechanism comes out of a surprising connection between the online shared resource allocation problem and implementation theory, and uses a surprising strengthening of Border's theorem. In particular, we show that establishing robust equilibria in this setting reduces to showing that a particular subset of the Border polytope is non-empty. We establish this via a novel joint Schur-convexity argument. This strengthening of Border's criterion for obtaining a stronger conclusion is of independent technical interest, as it may prove useful in other settings.

  PublisherOA PDFDOI

• Stable and Fault-Tolerant Decentralized Traffic Engineering

  ArXiv.org · 2025-10-13

  preprintOpen access

  Cloud providers have recently decentralized their wide-area network traffic engineering (TE) systems to contain the impact of TE controller failures. In the decentralized design, a controller fault only impacts its slice of the network, limiting the blast radius to a fraction of the network. However, we find that autonomous slice controllers can arrive at divergent traffic allocations that overload links by 30% beyond their capacity. We present Symphony, a decentralized TE system that addresses the challenge of divergence-induced congestion while preserving the fault-isolation benefits of decentralization. By augmenting TE objectives with quadratic regularization, Symphony makes traffic allocations robust to demand perturbations, ensuring TE controllers naturally converge to compatible allocations without coordination. In parallel, Symphony's randomized slicing algorithm partitions the network to minimize blast radius by distributing critical traffic sources across slices, preventing any single failure from becoming catastrophic. These innovations work in tandem: regularization ensures algorithmic stability to traffic allocations while intelligent slicing provides architectural resilience in the network. Through extensive evaluation on cloud provider WANs, we show Symphony reduces divergence-induced congestion by 14x and blast radius by 79% compared to current practice.

  PublisherOA PDFDOI

• Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learners

  2025-07-02

  articleOpen accessSenior author

  We analyze the performance of heterogeneous learning agents in asset markets with stochastic payoffs. Agents aim to maximize the expected growth rate of their wealth but have different theories on how to learn to do this best. Our main focus is on comparing Bayesian learners and no-regret learners who compete in markets and identifying the conditions under which each approach is more effective. Bayesian learners with a finite prior that assigns positive probability to the correct model have posterior beliefs that converge exponentially fast, and such agents survive even in the presence of agents who invest according to the correct model. Bayesian learners with a continuum prior converge at a slower rate of O((logT)/T).

  PublisherOA PDFDOI

• Allocating Public Goods via Dynamic Max-Min Fairness: Long-Run Behavior and Competitive Equilibria

  Proceedings of the ACM on Measurement and Analysis of Computing Systems · 2025-03-06

  articleOpen accessSenior author

  Dynamic max-min fair allocation (DMMF) is a simple and popular mechanism for the repeated allocation of a shared resource among competing agents: in each round, each agent can choose to request or not for the resource, which is then allocated to the requesting agent with the least number of allocations received till then. Recent work has shown that under DMMF, a simple threshold-based request policy enjoys surprisingly strong robustness properties, wherein each agent can realize a significant fraction of her optimal utility irrespective of how other agents' behave. While this goes some way in mitigating the possibility of a 'tragedy of the commons' outcome, the robust policies require that an agent defend against arbitrary (possibly adversarial) behavior by other agents. This however may be far from optimal compared to real world settings, where other agents are selfish optimizers rather than adversaries. Therefore, robust guarantees give no insight on how agents behave in an equilibrium, and whether outcomes are improved under one. Our work aims to bridge this gap by studying the existence and properties of equilibria under DMMF. To this end, we first show that despite the strong robustness guarantees of the threshold based strategies, no Nash equilibrium exists when agents participate in DMMF, each using some fixed threshold-based policy. On the positive side, however, we show that for the symmetric case, a simple data-driven request policy guarantees that no agent benefits from deviating to a different fixed threshold policy. In our proposed policy agents aim to match the historical allocation rate with a vanishing drift towards the rate optimizing overall welfare for all users. Furthermore, the resulting equilibrium outcome can be significantly better compared to what follows from the robustness guarantees. Our results are built on a complete characterization of the steady-state distribution under DMMF, as well as new techniques for analyzing strategic agent outcomes under dynamic allocation mechanisms; we hope these may prove of independent interest in related problems.

  PublisherOA PDFDOI

• Beyond Worst-Case Online Allocation via Dynamic Max-min Fairness

  2025-07-02

  articleOpen accessSenior author

  We consider the classical Dynamic Max-min fair (DMMF) mechanism for allocating an indivisible resource without money over multiple agents and T rounds. We show that under mild assumption on value distributions, it guarantees every agent close to optimal utility in large markets.

  PublisherOA PDFDOI

• Allocating Public Goods via Dynamic Max-Min Fairness: Long-Run Behavior and Competitive Equilibria

  2025-06-04

  articleSenior author
  PublisherDOI

• Online Resource Sharing: Better Robust Guarantees via Randomized Strategies

  2025-09-01

  articleSenior author

  We study the problem of fair online resource allocation via non-monetary mechanisms, where multiple agents repeatedly share a resource without monetary transfers. Previous work has shown that every agent can guarantee 1/2 of their ideal utility (the highest achievable utility given their fair share of resources) robustly, i.e., under arbitrary behavior by the other agents. While this 1/2-robustness guarantee has now been established under very different mechanisms, including pseudo-markets and dynamic max-min allocation, improving on it has appeared difficult. In this work, we obtain the first significant improvement on the robustness of online resource sharing. In more detail, we consider the widely-studied repeated first-price auction with artificial currencies. Our main contribution is to show that a simple randomized bidding strategy can guarantee each agent a 2 - √2 ≈ 0.59 fraction of her ideal utility, irrespective of others' bids. Specifically, our strategy requires each agent with fair share α to use a uniformly distributed bid whenever her value is in the top α-quantile of her value distribution. Our work almost closes the gap to the known 1 - 1/e ≈ 0.63 hardness for robust resource sharing; we also show that any static (i.e., budget independent) bidding policy cannot guarantee more than a 0.6-fraction of the ideal utility, showing our technique is almost tight.

  PublisherDOI

• Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learners

  ArXiv.org · 2025-02-12

  preprintOpen accessSenior author

  We analyze the performance of heterogeneous learning agents in asset markets with stochastic payoffs. Our main focus is on comparing Bayesian learners and no-regret learners who compete in markets and identifying the conditions under which each approach is more effective. We formally relate the notions of survival and market dominance studied in economics and the framework of regret minimization, thereby bridging these theories. A central finding is that regret plays a key role in market selection, but low regret alone does not guarantee survival: surprisingly, an agent may achieve even logarithmic regret and yet be driven out of the market when competing against a Bayesian learner with a finite prior that assigns positive probability to the correct model. At the same time, we show that Bayesian learning is highly fragile, while no-regret learning requires less knowledge of the environment and is therefore more robust. Motivated by this contrast, we propose two simple hybrid strategies that incorporate Bayesian updates while improving robustness and adaptability to distribution shifts, taking a step toward a best-of-both-worlds learning approach. More broadly, our work contributes to the understanding of dynamics of heterogeneous learning agents and their impact on markets.

  PublisherOA PDFDOI

Frequent coauthors

• Serge Plotkin

  44 shared

• Vasilis Syrgkanis

  38 shared

• Jon Kleinberg

  Cornell University

  35 shared

• Clifford Stein

  Columbia University

  27 shared

• Tim Roughgarden

  Columbia University

  22 shared

• David B. Shmoys

  Cornell University

  19 shared

• Fillia Makedon

  The University of Texas at Arlington

  17 shared

• Spyros Tragoudas

  Southern Illinois University Carbondale

  17 shared

Labs

• Éva Tardos' labPI

Education

• Other

  Eötvös University

• Ph.D.

  Eötvös University

Awards & honors

• Sloan Research Fellowship (1991)
• Packard Fellowship in Science and Engineering (1995)
• National Academy of Sciences Member (2013)
• National Academy of Engineering Member (2007)
• IEEE John von Neumann Medal (2019)