Jon Schneider
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Jon Schneider has a total of 29 co-authors. Here are the top co-authors by number of shared publications:
- Renato Paes Leme
Google Research, New York, NY, USA
4 shared publications - Eshwar Ram Arunachaleswaran
University of Pennsylvania, Philadelphia, USA
3 shared publications - Guru Guruganesh
Google Research, Mountain View, USA
3 shared publications - Natalie Collina
University of Pennsylvania, Philadelphia, USA
3 shared publications - Balasubramanian Sivan
Google Research, New York City, USA
2 shared publications - Joshua Wang
Google Research, USA
2 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1995-2006
Combinatorial Optimization using Comparison Oracles
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1995-2006
Open AccessCombinatorial Optimization using Comparison Oracles
- 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
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 542-553
Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 542-553
Open AccessEfficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games
- 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
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 893
Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions
Learning to bid in repeated first-price auctions is a fundamental problem at the interface of game theory and machine learning, which has seen a recent surge in interest due to the transition of display advertising to first-price auctions. In this work, we propose a novel concave formulation for pure-strategy bidding in first-price auctions, and use it to analyze natural Gradient-Ascent-based algorithms for this problem. Importantly, our analysis goes beyond regret, which was the typical focus of past work, and also accounts for the strategic backdrop of online-advertising markets where bidding algorithms are deployed---we provide the first guarantees of strategic-robustness and incentive-compatibility for Gradient Ascent. Concretely, we show that our algorithms achieve [EQUATION] regret when the highest competing bids are generated adversarially, and show that no online algorithm can do better. We further prove that the regret reduces to O(log T) when the competition is stationary and stochastic, which drastically improves upon the previous best of [EQUATION]. Moving beyond regret, we show that a strategic seller cannot exploit our algorithms to extract more revenue on average than is possible under the optimal mechanism. Finally, we prove that our algorithm is also incentive compatible---it is a (nearly) dominant strategy for the buyer to report her values truthfully to the algorithm as a whole. Altogether, these guarantees make our algorithms the first to simultaneously achieve both optimal regret and strategic-robustness. The full paper can be found at https://arxiv.org/abs/2402.07363.
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 893
Open AccessStrategically-Robust Learning Algorithms for Bidding in First-Price Auctions
Learning to bid in repeated first-price auctions is a fundamental problem at the interface of game theory and machine learning, which has seen a recent surge in interest due to the transition of display advertising to first-price auctions. In this work, we propose a novel concave formulation for pure-strategy bidding in first-price auctions, and use it to analyze natural Gradient-Ascent-based algorithms for this problem. Importantly, our analysis goes beyond regret, which was the typical focus of past work, and also accounts for the strategic backdrop of online-advertising markets where bidding algorithms are deployed---we provide the first guarantees of strategic-robustness and incentive-compatibility for Gradient Ascent. Concretely, we show that our algorithms achieve [EQUATION] regret when the highest competing bids are generated adversarially, and show that no online algorithm can do better. We further prove that the regret reduces to O(log T) when the competition is stationary and stochastic, which drastically improves upon the previous best of [EQUATION]. Moving beyond regret, we show that a strategic seller cannot exploit our algorithms to extract more revenue on average than is possible under the optimal mechanism. Finally, we prove that our algorithm is also incentive compatible---it is a (nearly) dominant strategy for the buyer to report her values truthfully to the algorithm as a whole. Altogether, these guarantees make our algorithms the first to simultaneously achieve both optimal regret and strategic-robustness. The full paper can be found at https://arxiv.org/abs/2402.07363.
- Open Access
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 75-100
Complex Dynamics in Autobidding Systems
It has become the default in markets such as ad auctions for participants to bid in an auction through automated bidding agents (autobidders) which adjust bids over time to satisfy return-over-spend constraints. Despite the prominence of such systems for the internet economy, their resulting dynamical behavior is still not well understood. Although one might hope that such relatively simple systems would typically converge to the equilibria of their underlying auctions, we provide a plethora of results that show the emergence of complex behavior, such as bi-stability, periodic orbits and quasi periodicity. We empirically observe how the market structure (expressed as motifs) qualitatively affects the behavior of the dynamics. We complement it with theoretical results showing that autobidding systems can simulate both linear dynamical systems as well logical boolean gates.
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 75-100
Open AccessComplex Dynamics in Autobidding Systems
It has become the default in markets such as ad auctions for participants to bid in an auction through automated bidding agents (autobidders) which adjust bids over time to satisfy return-over-spend constraints. Despite the prominence of such systems for the internet economy, their resulting dynamical behavior is still not well understood. Although one might hope that such relatively simple systems would typically converge to the equilibria of their underlying auctions, we provide a plethora of results that show the emergence of complex behavior, such as bi-stability, periodic orbits and quasi periodicity. We empirically observe how the market structure (expressed as motifs) qualitatively affects the behavior of the dynamics. We complement it with theoretical results showing that autobidding systems can simulate both linear dynamical systems as well logical boolean gates.
- Open Access
- 13 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 135-143
Prior-Free Mechanism with Welfare Guarantees
We consider the problem of designing prior-free revenue-maximizing mechanisms for allocating items to n buyers when the mechanism is additionally provided with an estimate for the optimal welfare (which is guaranteed to be correct to within a multiplicative factor of 1/α). In the digital goods setting (where we can allocate items to an arbitrary subset of the buyers), we demonstrate a mechanism that achieves revenue that is O(log n/α)-competitive with the optimal welfare. In the public goods setting (where we either must allocate the item to all buyers or to no buyers), we demonstrate a mechanism which is O(n log 1/α) competitive. In both settings, we show the dependence on α and n is tight. Finally, we discuss generalizations to broader classes of allocation constraints.
- 13 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 135-143
Open AccessPrior-Free Mechanism with Welfare Guarantees
We consider the problem of designing prior-free revenue-maximizing mechanisms for allocating items to n buyers when the mechanism is additionally provided with an estimate for the optimal welfare (which is guaranteed to be correct to within a multiplicative factor of 1/α). In the digital goods setting (where we can allocate items to an arbitrary subset of the buyers), we demonstrate a mechanism that achieves revenue that is O(log n/α)-competitive with the optimal welfare. In the public goods setting (where we either must allocate the item to all buyers or to no buyers), we demonstrate a mechanism which is O(n log 1/α) competitive. In both settings, we show the dependence on α and n is tight. Finally, we discuss generalizations to broader classes of allocation constraints.
- Open Access
- 7 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 818-848
The Power of Menus in Contract Design
We study the power of menus of contracts in principal-agent problems with adverse selection (agents can be one of several types) and moral hazard (we cannot observe agent actions directly). For principal-agent problems with T types and n actions, we show that the best menu of contracts can obtain a factor Ω (max(n, log T)) more utility for the principal than the best individual contract, partially resolving an open question of Guruganesh et al. [2021]. We then turn our attention to randomized menus of linear contracts, where we likewise show that randomized linear menus can be Ω(T) better than the best single linear contract. As a corollary, we show this implies an analogous gap between deterministic menus of (general) contracts and randomized menus of contracts (as introduced by Castiglioni et al. [2022]).
- 7 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 818-848
Open AccessThe Power of Menus in Contract Design
We study the power of menus of contracts in principal-agent problems with adverse selection (agents can be one of several types) and moral hazard (we cannot observe agent actions directly). For principal-agent problems with T types and n actions, we show that the best menu of contracts can obtain a factor Ω (max(n, log T)) more utility for the principal than the best individual contract, partially resolving an open question of Guruganesh et al. [2021]. We then turn our attention to randomized menus of linear contracts, where we likewise show that randomized linear menus can be Ω(T) better than the best single linear contract. As a corollary, we show this implies an analogous gap between deterministic menus of (general) contracts and randomized menus of contracts (as introduced by Castiglioni et al. [2022]).
- Open Access
- 30 April 2023
- Published by Association for Computing Machinery (ACM)
- p. 3541-3549
Eligibility Mechanisms: Auctions Meet Information Retrieval
The design of internet advertisement systems is both an auction design problem and an information retrieval (IR) problem. As an auction, the designer needs to take the participants incentives into account. As an information retrieval problem, it needs to identify the ad that it is the most relevant to a user out of an enormous set of ad candidates. Those aspects are combined by first having an IR system narrow down the initial set of ad candidates to a manageable size followed by an auction that ranks and prices those candidates. If the IR system uses information about bids, agents could in principle manipulate the system by manipulating the IR stage even when the subsequent auction is truthful. In this paper we investigate the design of truthful IR mechanisms, which we term eligibility mechanisms. We model it as a truthful version of the stochastic probing problem. We show that there is a constant gap between the truthful and non-truthful versions of the stochastic probing problem and exhibit a constant approximation algorithm. En route, we also characterize the set of eligibility mechanisms, which provides necessary and sufficient conditions for an IR system to be truthful.
- 30 April 2023
- Published by Association for Computing Machinery (ACM)
- p. 3541-3549
Open AccessEligibility Mechanisms: Auctions Meet Information Retrieval
The design of internet advertisement systems is both an auction design problem and an information retrieval (IR) problem. As an auction, the designer needs to take the participants incentives into account. As an information retrieval problem, it needs to identify the ad that it is the most relevant to a user out of an enormous set of ad candidates. Those aspects are combined by first having an IR system narrow down the initial set of ad candidates to a manageable size followed by an auction that ranks and prices those candidates. If the IR system uses information about bids, agents could in principle manipulate the system by manipulating the IR stage even when the subsequent auction is truthful. In this paper we investigate the design of truthful IR mechanisms, which we term eligibility mechanisms. We model it as a truthful version of the stochastic probing problem. We show that there is a constant gap between the truthful and non-truthful versions of the stochastic probing problem and exhibit a constant approximation algorithm. En route, we also characterize the set of eligibility mechanisms, which provides necessary and sufficient conditions for an IR system to be truthful.