4 citations · 14 across the 27 of their papers we have counts for
34 papers
Note on Finite-Automata Bernoulli Factories for Rational Functions
Renato Paes Leme, Jon Schneider
Mossel and Peres (2005) established a comprehensive framework for designing Bernoulli factories. Notably, they demonstrated that a single-variable function admits a finite-automata…
Nonbossy Mechanisms: Mechanism Design Robust to Secondary Goals
Renato Paes Leme, Jon Schneider, Hanrui Zhang
We study mechanism design when agents may have hidden secondary goals which will play a role when the primary utility of the outcomes is the same. We show that in such cases, a mec…
Bayesian Conversations
Renato Paes Leme, Jon Schneider, Heyang Shang +1
We study Bayesian conversations, a model of interactive information disclosure between two privately informed agents. Unlike Bayesian persuasion, information flows in both directio…
U-Calibration: Forecasting for an Unknown Agent
Robert Kleinberg, Renato Paes Leme, Jon Schneider +1
We consider the problem of evaluating forecasts of binary events whose predictions are consumed by rational agents who take an action in response to a prediction, but whose utility…
The Power of Menus in Contract Design
Guru Guruganesh, Jon Schneider, Joshua Wang +1
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 d…
Is Learning in Games Good for the Learners?
William Brown, Jon Schneider, Kiran Vodrahalli
We consider a number of questions related to tradeoffs between reward and regret in repeated gameplay between two agents. To facilitate this, we introduce a notion of $\textit{gene…
Pseudonorm Approachability and Applications to Regret Minimization
Christoph Dann, Yishay Mansour, Mehryar Mohri +2
Blackwell's celebrated approachability theory provides a general framework for a variety of learning problems, including regret minimization. However, Blackwell's proof and implici…
Anonymous Bandits for Multi-User Systems
Hossein Esfandiari, Vahab Mirrokni, Jon Schneider
In this work, we present and study a new framework for online learning in systems with multiple users that provide user anonymity. Specifically, we extend the notion of bandits to…
Bernoulli Factories for Flow-Based Polytopes
Rad Niazadeh, Renato Paes Leme, Jon Schneider
We construct explicit combinatorial Bernoulli factories for the class of \emph{flow-based polytopes}; integral 0/1-polytopes defined by a set of network flow constraints. This gene…
Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization
Renato Paes Leme, Chara Podimata, Jon Schneider
We study the problem of contextual search, a generalization of binary search in higher dimensions, in the adversarial noise model. Let be the dimension of the problem, be t…
Strategizing against Learners in Bayesian Games
Yishay Mansour, Mehryar Mohri, Jon Schneider +1
We study repeated two-player games where one of the players, the learner, employs a no-regret learning strategy, while the other, the optimizer, is a rational utility maximizer. We…
Online Learning with Bounded Recall
Jon Schneider, Kiran Vodrahalli
We study the problem of full-information online learning in the "bounded recall" setting popular in the study of repeated games. An online learning algorithm is -$…
Multiparameter Bernoulli Factories
Renato Paes Leme, Jon Schneider
We consider the problem of computing with many coins of unknown bias. We are given samples access to coins with \emph{unknown} biases and are asked to sample f…
Margin-Independent Online Multiclass Learning via Convex Geometry
Guru Guruganesh, Allen Liu, Jon Schneider +1
We consider the problem of multi-class classification, where a stream of adversarially chosen queries arrive and must be assigned a label online. Unlike traditional bounds which se…
Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
Sreenivas Gollapudi, Guru Guruganesh, Kostas Kollias +3
We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden -d…
Prior-free Dynamic Mechanism Design With Limited Liability
Mark Braverman, Jon Schneider, S. Matthew Weinberg
We study the problem of repeatedly auctioning off an item to one of bidders where: a) bidders have a per-round individual rationality constraint, b) bidders may leave the mecha…
Combinatorial Bernoulli Factories
Rad Niazadeh, Renato Paes Leme, Jon Schneider
A Bernoulli factory is an algorithmic procedure for exact sampling of certain random variables having only Bernoulli access to their parameters. Bernoulli access to a parameter $p…
Contracts under Moral Hazard and Adverse Selection
Guru Guruganesh, Jon Schneider, Joshua Wang
In the classical principal-agent problem, a principal must design a contract to incentivize an agent to perform an action on behalf of the principal. We study the classical princip…
Learning Product Rankings Robust to Fake Users
Negin Golrezaei, Vahideh Manshadi, Jon Schneider +1
In many online platforms, customers' decisions are substantially influenced by product rankings as most customers only examine a few top-ranked products. Concurrently, such platfor…
Reserve Price Optimization for First Price Auctions
Zhe Feng, Sébastien Lahaie, Jon Schneider +1
The display advertising industry has recently transitioned from second- to first-price auctions as its primary mechanism for ad allocation and pricing. In light of this, publishers…
Variable Decomposition for Prophet Inequalities and Optimal Ordering
Allen Liu, Renato Paes Leme, Martin Pal +2
We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number o…
Optimal Contextual Pricing and Extensions
Allen Liu, Renato Paes Leme, Jon Schneider
In the contextual pricing problem a seller repeatedly obtains products described by an adversarially chosen feature vector in and only observes the purchasing decisi…
Strategizing against No-regret Learners
Yuan Deng, Jon Schneider, Balusubramanian Sivan
How should a player who repeatedly plays a game against a no-regret learner strategize to maximize his utility? We study this question and show that under some mild assumptions, th…
Contextual Bandits with Cross-learning
Santiago Balseiro, Negin Golrezaei, Mohammad Mahdian +2
In the classical contextual bandits problem, in each round , a learner observes some context , chooses some action to perform, and receives some reward . We c…