Nick Gravin

Publication Activity (10 Years)

Years Active: 2009-2023
Publications (10 Years): 47

Top Topics

Combinatorial Auctions

Pure Nash Equilibria

Mechanism Design

Top Venues

Math. Oper. Res.

Publications

Nick Gravin, Hongao Wang
Prophet Inequality for Bipartite Matching: Merits of Being Simple and Nonadaptive. Math. Oper. Res. 48 (1) (2023)
Tomer Ezra, Michal Feldman, Nick Gravin, Zhihao Gavin Tang
"Who is Next in Line?" On the Significance of Knowing the Arrival Order in Bayesian Online Settings. SODA (2023)
Xiaohui Bei, Nick Gravin, Pinyan Lu, Zhihao Gavin Tang
Bidder Subset Selection Problem in Auction Design. SODA (2023)
Nick Gravin, Enze Sun, Zhihao Gavin Tang
Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity. FOCS (2023)
Nick Gravin, Yixuan Even Xu, Renfei Zhou
Bidder Selection Problem in Position Auctions via Poisson Approximation. CoRR (2023)
Michal Feldman, Vasilis Gkatzelis, Nick Gravin, Daniel Schoepflin
Bayesian and Randomized Clock Auctions. CoRR (2022)
Michal Feldman, Vasilis Gkatzelis, Nick Gravin, Daniel Schoepflin
Bayesian and Randomized Clock Auctions. EC (2022)
Xiaohui Bei, Nick Gravin, Pinyan Lu, Zhihao Gavin Tang
Bidder Subset Selection Problem in Auction Design. CoRR (2022)
Tomer Ezra, Michal Feldman, Nick Gravin, Zhihao Gavin Tang
General Graphs are Easier than Bipartite Graphs: Tight Bounds for Secretary Matching. EC (2022)
Tomer Ezra, Michal Feldman, Nick Gravin, Zhihao Gavin Tang
On the Significance of Knowing the Arrival Order in Prophet Inequality. CoRR (2022)
Nick Gravin, Enze Sun, Zhihao Gavin Tang
The Cardinal Complexity of Comparison-based Online Algorithms. CoRR (2022)
Michal Feldman, Nick Gravin, Zhihao Gavin Tang, Almog Wald
Lookahead Auctions with Pooling. SAGT (2022)
Nick Gravin, Hao Li, Zhihao Gavin Tang
Optimal Prophet Inequality with Less than One Sample. WINE (2022)
Tomer Ezra, Michal Feldman, Nick Gravin, Zhihao Gavin Tang
Prophet Matching with General Arrivals. Math. Oper. Res. 47 (2) (2022)
Almog Wald, Michal Feldman, Nick Gravin, Zhihao Gavin Tang
Lookahead Auctions with Pooling. CoRR (2022)
Ioannis Caragiannis, Nick Gravin, Pinyan Lu, Zihe Wang
Relaxing the Independence Assumption in Sequential Posted Pricing, Prophet Inequality, and Random Bipartite Matching. WINE (2021)
Yu Cheng, Nick Gravin, Kamesh Munagala, Kangning Wang
A Simple Mechanism for a Budget-Constrained Buyer. ACM Trans. Economics and Comput. 9 (2) (2021)
Nick Gravin, Siyao Guo, Tsz Chiu Kwok, Pinyan Lu
-wise independence with applications to non-uniform security. SODA (2021)
Nick Gravin, Zhihao Gavin Tang, Kangning Wang
Online Stochastic Matching with Edge Arrivals. ICALP (2021)
Tomer Ezra, Michal Feldman, Nick Gravin, Zhihao Gavin Tang
Secretary Matching with General Arrivals. CoRR (2020)
Tomer Ezra, Michal Feldman, Nick Gravin, Zhihao Gavin Tang
Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models. EC (2020)
Nick Gravin, Yaonan Jin, Pinyan Lu, Chenhao Zhang
Optimal Budget-Feasible Mechanisms for Additive Valuations. ACM Trans. Economics and Comput. 8 (4) (2020)
Michal Feldman, Hu Fu, Nick Gravin, Brendan Lucier
Simultaneous auctions without complements are (almost) efficient. Games Econ. Behav. 123 (2020)
Tomer Ezra, Michal Feldman, Nick Gravin, Zhihao Gavin Tang
Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models. CoRR (2020)
Nick Gravin, Hongao Wang
Prophet inequality for bipartite matching: merits of being simple and non adaptive. CoRR (2019)
Xiaohui Bei, Nick Gravin, Pinyan Lu, Zhihao Gavin Tang
Correlation-Robust Analysis of Single Item Auction. SODA (2019)
Nick Gravin, Yaonan Jin, Pinyan Lu, Chenhao Zhang
Optimal Budget-Feasible Mechanisms for Additive Valuations. EC (2019)
Ioannis Caragiannis, Nick Gravin, Xin Huang
Envy-freeness up to any item with high Nash welfare: The virtue of donating items. CoRR (2019)
Ioannis Caragiannis, Nick Gravin, Xin Huang
Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items. EC (2019)
Nick Gravin, Zhihao Gavin Tang, Kangning Wang
Online Stochastic Matching with Edge Arrivals. CoRR (2019)
Nick Gravin, Yaonan Jin, Pinyan Lu, Chenhao Zhang
Optimal Budget-Feasible Mechanisms for Additive Valuations. CoRR (2019)
Nick Gravin, Pinian Lu
Correlation-robust mechanism design. SIGecom Exch. 16 (2) (2018)
Yu Cheng, Nick Gravin, Kamesh Munagala, Kangning Wang
A Simple Mechanism for a Budget-Constrained Buyer. CoRR (2018)
Yu Cheng, Nick Gravin, Kamesh Munagala, Kangning Wang
A Simple Mechanism for a Budget-Constrained Buyer. WINE (2018)
Nick Gravin, Pinyan Lu
Separation in Correlation-Robust Monopolist Problem with Budget. SODA (2018)
Nick Gravin, Zhihao Gavin Tang
Monopoly pricing with buyer search. CoRR (2018)
Constantinos Daskalakis, Nishanth Dikkala, Nick Gravin
Testing Symmetric Markov Chains From a Single Trajectory. COLT (2018)
Nick Gravin, Yuval Peres, Balasubramanian Sivan
Tight Lower Bounds for Multiplicative Weights Algorithmic Families. ICALP (2017)
Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu
Worst-Case Mechanism Design via Bayesian Analysis. SIAM J. Comput. 46 (4) (2017)
Yossi Azar, Michal Feldman, Nick Gravin, Alan Roytman
Liquid Price of Anarchy. SAGT (2017)
Constantinos Daskalakis, Nishanth Dikkala, Nick Gravin
Testing from One Sample: Is the casino really using a riffle shuffle? CoRR (2017)
Ioannis Caragiannis, Angelo Fanelli, Nick Gravin
Short Sequences of Improvement Moves Lead to Approximate Equilibria in Constraint Satisfaction Games. Algorithmica 77 (4) (2017)
Nick Gravin, Yuval Peres, Balasubramanian Sivan
Towards Optimal Algorithms for Prediction with Expert Advice. SODA (2016)
Michal Feldman, Nick Gravin, Brendan Lucier
Combinatorial Walrasian Equilibrium. SIAM J. Comput. 45 (1) (2016)
Nick Gravin, Yuval Peres, Balasubramanian Sivan
Tight Lower Bounds for Multiplicative Weights Algorithmic Families. CoRR (2016)
Nick Gravin, Nicole Immorlica, Brendan Lucier, Emmanouil Pountourakis
Procrastination with variable present bias. CoRR (2016)
Nick Gravin, Nicole Immorlica, Brendan Lucier, Emmanouil Pountourakis
Procrastination with Variable Present Bias. EC (2016)
John Augustine, Ning Chen, Edith Elkind, Angelo Fanelli, Nick Gravin, Dmitry Shiryaev
Dynamics of Profit-Sharing Games. Internet Math. 11 (1) (2015)
Michal Feldman, Nick Gravin, Brendan Lucier
On Welfare Approximation and Stable Pricing. CoRR (2015)
Yossi Azar, Michal Feldman, Nick Gravin, Alan Roytman
Liquid Price of Anarchy. CoRR (2015)
Michal Feldman, Nick Gravin, Brendan Lucier
Combinatorial Auctions via Posted Prices. SODA (2015)
Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik
Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure. ACM Trans. Economics and Comput. 3 (1) (2015)
Ioannis Caragiannis, Angelo Fanelli, Nick Gravin
Short sequences of improvement moves lead to approximate equilibria in constraint satisfaction games. CoRR (2014)
Ning Chen, Nick Gravin, Pinyan Lu
Competitive analysis via benchmark decomposition. CoRR (2014)
Michal Feldman, Nick Gravin, Brendan Lucier
Combinatorial Auctions via Posted Prices. CoRR (2014)
Nick Gravin, Yuval Peres, Balasubramanian Sivan
Towards Optimal Algorithms for Prediction with Expert Advice. CoRR (2014)
Ning Chen, Nick Gravin, Pinyan Lu
Optimal competitive auctions. STOC (2014)
Ning Chen, Nick Gravin, Pinyan Lu
Optimal Competitive Auctions. CoRR (2014)
Ioannis Caragiannis, Angelo Fanelli, Nick Gravin
Short Sequences of Improvement Moves Lead to Approximate Equilibria in Constraint Satisfaction Games. SAGT (2014)
Ning Chen, Nick Gravin, Pinyan Lu
Truthful Generalized Assignments via Stable Matching. Math. Oper. Res. 39 (3) (2014)
Michal Feldman, Hu Fu, Nick Gravin, Brendan Lucier
Simultaneous auctions are (almost) efficient. STOC (2013)
Nick Gravin, Pinyan Lu
Competitive Auctions for Markets with Positive Externalities. ICALP (2) (2013)
Michal Feldman, Nick Gravin, Brendan Lucier
Combinatorial Walrasian Equilibrium CoRR (2013)
Michal Feldman, Nick Gravin, Brendan Lucier
Combinatorial walrasian equilibrium. STOC (2013)
Nick Gravin, Mihail N. Kolountzakis, Sinai Robins, Dmitry Shiryaev
Structure Results for Multiple Tilings in 3D. Discret. Comput. Geom. 50 (4) (2013)
Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik
Computing approximate pure Nash equilibria in congestion games. SIGecom Exch. 11 (1) (2012)
Nick Gravin, Sinai Robins, Dmitry Shiryaev
Translational tilings by a polytope, with multiplicity. Comb. 32 (6) (2012)
Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu
Budget feasible mechanism design: from prior-free to bayesian. STOC (2012)
Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik
Approximate pure nash equilibria in weighted congestion games: existence, efficient computation, and structure. EC (2012)
Michal Feldman, Hu Fu, Nick Gravin, Brendan Lucier
Simultaneous Auctions are (almost) Efficient CoRR (2012)
Nick Gravin, Jean B. Lasserre, Dmitrii V. Pasechnik, Sinai Robins
The Inverse Moment Problem for Convex Polytopes. Discret. Comput. Geom. 48 (3) (2012)
Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu
Budget Feasible Mechanism Design: From Prior-Free to Bayesian CoRR (2012)
Nick Gravin, Ning Chen
-shortest paths problem. J. Graph Theory 67 (1) (2011)
Xiaohui Bei, Ning Chen, Nick Gravin, Pinyan Lu
Budget Feasible Mechanism Design via Random Sampling CoRR (2011)
Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik
Computing approximate pure Nash equilibria in weighted congestion games with polynomial latency functions CoRR (2011)
Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik
Efficient computation of approximate pure Nash equilibria CoRR (2011)
Nick Gravin, Jean B. Lasserre, Dmitrii V. Pasechnik, Sinai Robins
The inverse moment problem for convex polytopes CoRR (2011)
John Augustine, Ning Chen, Edith Elkind, Angelo Fanelli, Nick Gravin, Dmitry Shiryaev
Dynamics of Profit-Sharing Games. IJCAI (2011)
Nick Gravin, Pinyan Lu
Competitive Auctions for Markets with Positive Externalities CoRR (2011)
Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik
Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games. FOCS (2011)
Ning Chen, Nick Gravin, Pinyan Lu
On the Approximability of Budget Feasible Mechanisms. SODA (2011)
Ning Chen, Nick Gravin, Pinyan Lu
Mechanism Design without Money via Stable Matching CoRR (2011)
Ning Chen, Edith Elkind, Nick Gravin, Fedor Petrov
Frugal Mechanism Design via Spectral Techniques. FOCS (2010)
Ning Chen, Nick Gravin, Pinyan Lu
On the Approximability of Budget Feasible Mechanisms CoRR (2010)
Nick Gravin
-List Colouring of a Graph. CSR (2010)
John Augustine, Ning Chen, Edith Elkind, Angelo Fanelli, Nick Gravin, Dmitry Shiryaev
Dynamics of Profit-Sharing Games CoRR (2010)
John Augustine, Nick Gravin
On the Continuous CNN Problem. ISAAC (2) (2010)
John Augustine, Nick Gravin
On the Continuous CNN Problem CoRR (2010)
Ning Chen, Edith Elkind, Nick Gravin
Refining the Cost of Cheap Labor in Set System Auctions. WINE (2009)
Ning Chen, Edith Elkind, Nick Gravin, Fedor Petrov
Frugal Mechanism Design via Spectral Techniques CoRR (2009)