5 papers
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…
Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond -Approximation
Aviad Rubinstein, Junyao Zhao
In this work we give two new algorithms that use similar techniques for (non-monotone) submodular function maximization subject to a cardinality constraint. The first is an offline…
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_…
Robust Maximization of Non-Submodular Objectives
Ilija Bogunovic, Junyao Zhao, Volkan Cevher
We study the problem of maximizing a monotone set function subject to a cardinality constraint in the setting where some number of elements is deleted from the returned set…