4 citations · 10 across the 11 of their papers we have counts for
7 papers · 1 filter
Beyond Worst-Case Budget-Feasible Mechanism Design
Aviad Rubinstein, Junyao Zhao
Motivated by large-market applications such as crowdsourcing, we revisit the problem of budget-feasible mechanism design under a "small-bidder assumption". Anari, Goel, and Nikzad…
The Randomized Communication Complexity of Randomized Auctions
Aviad Rubinstein, Junyao Zhao
We study the communication complexity of incentive compatible auction-protocols between a monopolist seller and a single buyer with a combinatorial valuation function over item…
Exponential Communication Separations between Notions of Selfishness
Aviad Rubinstein, Raghuvansh R. Saxena, Clayton Thomas +2
We consider the problem of implementing a fixed social choice function between multiple players (which takes as input a type from each player and outputs an outcome $f(t_…
Communication complexity of Nash equilibrium in potential games
Yakov Babichenko, Aviad Rubinstein
We prove communication complexity lower bounds for (possibly mixed) Nash equilibrium in potential games. In particular, we show that finding a Nash equilibrium requires c…
Smoothed Complexity of 2-player Nash Equilibria
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins +1
We prove that computing a Nash equilibrium of a two-player () game with payoffs in is PPAD-hard (under randomized reductions) even in the smoothed analysis set…
Optimal Deterministic Mechanisms for an Additive Buyer
Moshe Babaioff, Noam Nisan, Aviad Rubinstein
We study revenue maximization by deterministic mechanisms for the simplest case for which Myerson's characterization does not hold: a single seller selling two items, with independ…