3 citations · 4 across the 8 of their papers we have counts for
11 papers
Parity Tests under Ties: A One-Test Lifting Theorem
Ron Kupfer
In the unrestricted polynomial decision-tree model, only the number of polynomial sign tests is charged. A parity test asks for the sign of a product of pairwise differences. Such…
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…
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…
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…
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…