JSJon Schneider

Jon Schneider

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

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Jon Schneider has a total of 29 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Combinatorial Optimization using Comparison Oracles

    by Vincent Cohen-Addad, Tommaso D'ORsi, Anupam Gupta, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Reddy Pittu, Jon Schneider, David P. Woodruff

  • 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

    Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games

    by Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Charilaos Pipis, 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

    Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions

    by Rachitesh Kumar, Jon Schneider, Balasubramanian Sivan

    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

    Complex Dynamics in Autobidding Systems

    by Renato Paes Leme, Georgios Piliouras, Jon Schneider, Kelly Spendlove, Song Zuo

    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

    Prior-Free Mechanism with Welfare Guarantees

    by Guru Guruganesh, Jon Schneider, Joshua Wang

    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

    The Power of Menus in Contract Design

    by Guru Guruganesh, Jon Schneider, Joshua Wang, Junyao Zhao

    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

    Eligibility Mechanisms: Auctions Meet Information Retrieval

    by Gagan Goel, Renato Paes Leme, Jon Schneider, David Thompson, Hanrui Zhang

    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.