5 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…
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 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…
Bayesian Conversations
Renato Paes Leme, Jon Schneider, Heyang Shang +1
We initiate the study of Bayesian conversations, which model interactive communication between two strategic agents without a mediator. We compare this to communication through a m…