60 citations · 237 across the 39 of their papers we have counts for
43 papers
On the satisfiability of random -SAT formulas with -wise independent clauses
Ioannis Caragiannis, Nick Gravin, Zhile Jiang
The problem of identifying the satisfiability threshold of random -SAT formulas has received a lot of attention during the last decades and has inspired the study of other thres…
On Robustness to -wise Independence of Optimal Bayesian Mechanisms
Nick Gravin, Zhiqi Wang
This paper reexamines the classic problem of revenue maximization in single-item auctions with buyers under the lens of the robust optimization framework. The celebrated Myerso…
Bidder Subset Selection Problem in Auction Design
Xiaohui Bei, Nick Gravin, Pinyan Lu +1
Motivated by practical concerns in the online advertising industry, we study a bidder subset selection problem in single-item auctions. In this problem, a large pool of candidate b…
Lookahead Auctions with Pooling
Almog Wald, Michal Feldman, Nick Gravin +1
A Lookahead Auction (LA), introduced by Ronen, is an auction format for the sale of a single item among multiple buyers, which is considered simpler and more fair than the optimal…
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity
Nick Gravin, Enze Sun, Zhihao Gavin Tang
We consider ordinal online problems, i.e., tasks that only require pairwise comparisons between elements of the input. A classic example is the secretary problem and the game of go…
Bayesian and Randomized Clock Auctions
Michal Feldman, Vasilis Gkatzelis, Nick Gravin +1
In a single-parameter mechanism design problem, a provider is looking to sell a service to a group of potential buyers. Each buyer has a private value for receiving the s…