60 citations · 237 across the 39 of their papers we have counts for
4 papers · 1 filter
Online Stochastic Matching with Edge Arrivals
Nick Gravin, Zhihao Gavin Tang, Kangning Wang
Online bipartite matching with edge arrivals remained a major open question for a long time until a recent negative result by [Gamlath et al. FOCS 2019], who showed that no online…
Prophet inequality for bipartite matching: merits of being simple and non adaptive
Nick Gravin, Hongao Wang
We consider Bayesian online selection problem of a matching in bipartite graphs, i.e., online weighted matching problem with edge arrivals where online algorithm knows distribution…
Envy-freeness up to any item with high Nash welfare: The virtue of donating items
Ioannis Caragiannis, Nick Gravin, Xin Huang
Several fairness concepts have been proposed recently in attempts to approximate envy-freeness in settings with indivisible goods. Among them, the concept of envy-freeness up to an…
Optimal Budget-Feasible Mechanisms for Additive Valuations
Nick Gravin, Yaonan Jin, Pinyan Lu +1
In this paper, we show a tight approximation guarantee for budget-feasible mechanisms with an additive buyer. We propose a new simple randomized mechanism with approximation ratio…