Publications (10)
A Note on the Gains from Trade of the Random-Offerer Mechanism
Moshe Babaioff, Shahar Dobzinski, Ron Kupfer
We study the classic bilateral trade setting. Myerson and Satterthwaite show that there is no Bayesian incentive compatible and budget-balanced mechanism that obtains the gains fro…
Prophet Inequality with Competing Agents
Tomer Ezra, Michal Feldman, Ron Kupfer
We introduce a model of competing agents in a prophet setting, where rewards arrive online, and decisions are made immediately and irrevocably. The rewards are unknown from the out…
An Optimal Elimination Algorithm for Learning a Best Arm
Avinatan Hassidim, Ron Kupfer, Yaron Singer
We consider the classic problem of -PAC learning a best arm where the goal is to identify with confidence an arm whose mean is an -approximation to that of the…
The Influence of One Strategic Agent on the Core of Stable Matchings
Ron Kupfer
In this work, we analyze the influence of a single strategic agent on the quality of the other agents' matchings in a matching market. We consider a stable matching problem with $n…
A Note on Approximate Revenue Maximization with Two Items
Ron Kupfer
We consider the problem of maximizing revenue when selling 2 items to a single buyer with known valuation distributions. Hart and Nisan showed that selling each item separately usi…
Simplicity in Auctions Revisited: The Primitive Complexity
Moshe Babaioff, Shahar Dobzinski, Ron Kupfer
In this paper we revisit the notion of simplicity in mechanisms. We consider a seller of items, facing a single buyer with valuation . We observe that previous attempts to d…
Parity Tests with Ties
Ron Kupfer
We extend the Ting--Yao randomized maximum-finding algorithm [TY94] to inputs that need not be pairwise distinct: each parity test on $B\subseteq…
Finding a Hidden Edge
Ron Kupfer, Noam Nisan
We consider the problem of finding an edge in a hidden undirected graph with vertices, in a model where we only allowed queries that ask whether or not a subset of…
On a Competitive Secretary Problem with Deferred Selections
Tomer Ezra, Michal Feldman, Ron Kupfer
We study secretary problems in settings with multiple agents. In the standard secretary problem, a sequence of arbitrary awards arrive online, in a random order, and a single decis…
A Note on the Ratio of Revenues Between Selling in a Bundle and Separately
Ron Kupfer
We consider the problem of maximizing revenue when selling k items to a single buyer with known valuation distributions. We show that for a single, additive buyer whose valuations…