20 papers
Graphic Matroid Secretary without the Graph
Paul Dütting, Renato Paes Leme, Martin Pál +1
The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists a consta…
Resource Allocation and Conversion along the Org Chart
Yuan Deng, Giannis Fikioris, Chido Onyeze +3
We consider the allocation of multiple heterogeneous resources to agents who are organized according to an organizational hierarchy. In a company those correspond to business units…
Compensation Design
Ioannis Anagnostides, Kshipra Bhawalkar, Christopher Liaw +5
The paper defines the problem of compensation design, proposing simple cost‑oblivious payment rules that guarantee the existence of pure Nash equilibria with a price of anarchy clo…
Quota Marketplace: Dynamic Pricing for Efficient Allocation of ML Training Resources
Balasubramanian Sivan, Renato Paes Leme, Mihai Tiuca +6
The escalating demand for Machine Learning (ML) training resources in recent years has resulted in a substantial gap between the high demand and the available supply. Efficient all…
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…