% csauthors.net - beta - BibTeX bibliography of Nick Gravin
@inproceedings{conf/wine/ChenEG09,
title = {Refining the Cost of Cheap Labor in Set System Auctions.},
year = {2009},
booktitle = {WINE},
author = {{Ning Chen 005} and {Edith Elkind} and {Nick Gravin}},
publisher = {Springer},
booktitle = {Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings}
}
@inproceedings{conf/csr/Gravin10,
title = {Time Optimal d-List Colouring of a Graph.},
year = {2010},
booktitle = {CSR},
author = {{Nick Gravin}},
publisher = {Springer},
booktitle = {Computer Science - Theory and Applications, 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russia, June 16-20, 2010. Proceedings}
}
@inproceedings{conf/focs/ChenEGP10,
title = {Frugal Mechanism Design via Spectral Techniques.},
year = {2010},
booktitle = {FOCS},
author = {{Ning Chen 005} and {Edith Elkind} and {Nick Gravin} and {Fedor Petrov 001}},
publisher = {IEEE Computer Society},
booktitle = {51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA}
}
@inproceedings{conf/isaac/AugustineG10,
title = {On the Continuous CNN Problem.},
year = {2010},
booktitle = {ISAAC (2)},
author = {{John Augustine} and {Nick Gravin}},
publisher = {Springer},
booktitle = {Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part II}
}
@inproceedings{conf/focs/CaragiannisFGS11,
title = {Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games.},
year = {2011},
booktitle = {FOCS},
author = {{Ioannis Caragiannis} and {Angelo Fanelli 001} and {Nick Gravin} and {Alexander Skopalik}},
publisher = {IEEE Computer Society},
booktitle = {IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011}
}
@inproceedings{conf/soda/ChenGL11,
title = {On the Approximability of Budget Feasible Mechanisms.},
year = {2011},
booktitle = {SODA},
author = {{Ning Chen 005} and {Nick Gravin} and {Pinyan Lu}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011}
}
@article{journals/corr/abs-1104-2690,
title = {Efficient computation of approximate pure Nash equilibria},
year = {2011},
journal = {CoRR},
author = {{Ioannis Caragiannis} and {Angelo Fanelli 001} and {Nick Gravin} and {Alexander Skopalik}}
}
@article{journals/corr/abs-1104-2872,
title = {Mechanism Design without Money via Stable Matching},
year = {2011},
journal = {CoRR},
author = {{Ning Chen 005} and {Nick Gravin} and {Pinyan Lu}}
}
@article{journals/corr/abs-1107-2248,
title = {Computing approximate pure Nash equilibria in weighted congestion games with polynomial latency functions},
year = {2011},
journal = {CoRR},
author = {{Ioannis Caragiannis} and {Angelo Fanelli 001} and {Nick Gravin} and {Alexander Skopalik}}
}
@article{journals/corr/abs-1107-2994,
title = {Budget Feasible Mechanism Design via Random Sampling},
year = {2011},
journal = {CoRR},
author = {{Xiaohui Bei} and {Ning Chen 005} and {Nick Gravin} and {Pinyan Lu}}
}
@article{journals/jgt/GravinC11,
title = {A note on k-shortest paths problem.},
year = {2011},
journal = {J. Graph Theory},
author = {{Nick Gravin} and {Ning Chen 005}}
}
@inproceedings{conf/stoc/BeiCGL12,
title = {Budget feasible mechanism design: from prior-free to bayesian.},
year = {2012},
booktitle = {STOC},
author = {{Xiaohui Bei} and {Ning Chen 005} and {Nick Gravin} and {Pinyan Lu}},
publisher = {ACM},
booktitle = {Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012}
}
@article{journals/combinatorica/GravinRS12,
title = {Translational tilings by a polytope, with multiplicity.},
year = {2012},
journal = {Comb.},
author = {{Nick Gravin} and {Sinai Robins} and {Dmitry Shiryaev}}
}
@article{journals/dcg/GravinLPR12,
title = {The Inverse Moment Problem for Convex Polytopes.},
year = {2012},
journal = {Discret. Comput. Geom.},
author = {{Nick Gravin} and {Jean B. Lasserre} and {Dmitrii V. Pasechnik} and {Sinai Robins}}
}
@article{journals/sigecom/CaragiannisFGS12,
title = {Computing approximate pure Nash equilibria in congestion games.},
year = {2012},
journal = {SIGecom Exch.},
author = {{Ioannis Caragiannis} and {Angelo Fanelli 001} and {Nick Gravin} and {Alexander Skopalik}}
}
@inproceedings{conf/icalp/GravinL13,
title = {Competitive Auctions for Markets with Positive Externalities.},
year = {2013},
booktitle = {ICALP (2)},
author = {{Nick Gravin} and {Pinyan Lu}},
publisher = {Springer},
booktitle = {Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II}
}
@inproceedings{conf/stoc/FeldmanFGL13,
title = {Simultaneous auctions are (almost) efficient.},
year = {2013},
booktitle = {STOC},
author = {{Michal Feldman} and {Hu Fu 001} and {Nick Gravin} and {Brendan Lucier}},
publisher = {ACM},
booktitle = {Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013}
}
@article{journals/dcg/GravinKRS13,
title = {Structure Results for Multiple Tilings in 3D.},
year = {2013},
journal = {Discret. Comput. Geom.},
author = {{Nick Gravin} and {Mihail N. Kolountzakis} and {Sinai Robins} and {Dmitry Shiryaev}}
}
@inproceedings{conf/stoc/ChenGL14,
title = {Optimal competitive auctions.},
year = {2014},
booktitle = {STOC},
author = {{Ning Chen 005} and {Nick Gravin} and {Pinyan Lu}},
publisher = {ACM},
booktitle = {Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014}
}
@article{journals/mor/ChenGL14,
title = {Truthful Generalized Assignments via Stable Matching.},
year = {2014},
journal = {Math. Oper. Res.},
author = {{Ning Chen 005} and {Nick Gravin} and {Pinyan Lu}}
}
@inproceedings{conf/sigecom/ChenGL15,
title = {Competitive Analysis via Benchmark Decomposition.},
year = {2015},
booktitle = {EC},
author = {{Ning Chen 005} and {Nikolai Gravin} and {Pinyan Lu}},
publisher = {ACM},
booktitle = {Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, Portland, OR, USA, June 15-19, 2015}
}
@inproceedings{conf/soda/FeldmanGL15,
title = {Combinatorial Auctions via Posted Prices.},
year = {2015},
booktitle = {SODA},
author = {{Michal Feldman} and {Nick Gravin} and {Brendan Lucier}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015}
}
@article{journals/corr/FeldmanGL15,
title = {On Welfare Approximation and Stable Pricing.},
year = {2015},
journal = {CoRR},
author = {{Michal Feldman} and {Nick Gravin} and {Brendan Lucier}}
}
@article{journals/im/AugustineCEFGS15,
title = {Dynamics of Profit-Sharing Games.},
year = {2015},
journal = {Internet Math.},
author = {{John Augustine} and {Ning Chen 005} and {Edith Elkind} and {Angelo Fanelli 001} and {Nick Gravin} and {Dmitry Shiryaev}}
}
@article{journals/teco/CaragiannisFGS15,
title = {Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure.},
year = {2015},
journal = {ACM Trans. Economics and Comput.},
author = {{Ioannis Caragiannis} and {Angelo Fanelli 001} and {Nick Gravin} and {Alexander Skopalik}}
}
@inproceedings{conf/sigecom/GravinILP16,
title = {Procrastination with Variable Present Bias.},
year = {2016},
booktitle = {EC},
author = {{Nick Gravin} and {Nicole Immorlica} and {Brendan Lucier} and {Emmanouil Pountourakis}},
publisher = {ACM},
booktitle = {Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16, Maastricht, The Netherlands, July 24-28, 2016}
}
@inproceedings{conf/soda/GravinPS16,
title = {Towards Optimal Algorithms for Prediction with Expert Advice.},
year = {2016},
booktitle = {SODA},
author = {{Nick Gravin} and {Yuval Peres} and {Balasubramanian Sivan}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016}
}
@article{journals/siamcomp/FeldmanGL16,
title = {Combinatorial Walrasian Equilibrium.},
year = {2016},
journal = {SIAM J. Comput.},
author = {{Michal Feldman} and {Nick Gravin} and {Brendan Lucier}}
}
@inproceedings{conf/icalp/GravinPS17,
title = {Tight Lower Bounds for Multiplicative Weights Algorithmic Families.},
year = {2017},
booktitle = {ICALP},
author = {{Nick Gravin} and {Yuval Peres} and {Balasubramanian Sivan}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland}
}
@inproceedings{conf/sagt/AzarFGR17,
title = {Liquid Price of Anarchy.},
year = {2017},
booktitle = {SAGT},
author = {{Yossi Azar} and {Michal Feldman} and {Nick Gravin} and {Alan Roytman}},
publisher = {Springer},
booktitle = {Algorithmic Game Theory - 10th International Symposium, SAGT 2017, L'Aquila, Italy, September 12-14, 2017, Proceedings}
}
@article{journals/algorithmica/Caragiannis0G17,
title = {Short Sequences of Improvement Moves Lead to Approximate Equilibria in Constraint Satisfaction Games.},
year = {2017},
journal = {Algorithmica},
author = {{Ioannis Caragiannis} and {Angelo Fanelli 001} and {Nick Gravin}}
}
@article{journals/corr/DaskalakisDG17,
title = {Testing from One Sample: Is the casino really using a riffle shuffle?},
year = {2017},
journal = {CoRR},
author = {{Constantinos Daskalakis} and {Nishanth Dikkala} and {Nick Gravin}}
}
@article{journals/siamcomp/BeiCGL17,
title = {Worst-Case Mechanism Design via Bayesian Analysis.},
year = {2017},
journal = {SIAM J. Comput.},
author = {{Xiaohui Bei} and {Ning Chen 005} and {Nick Gravin} and {Pinyan Lu}}
}
@inproceedings{conf/colt/DaskalakisDG18,
title = {Testing Symmetric Markov Chains From a Single Trajectory.},
year = {2018},
booktitle = {COLT},
author = {{Constantinos Daskalakis} and {Nishanth Dikkala} and {Nick Gravin}},
publisher = {PMLR},
booktitle = {Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018.}
}
@inproceedings{conf/soda/GravinL18,
title = {Separation in Correlation-Robust Monopolist Problem with Budget.},
year = {2018},
booktitle = {SODA},
author = {{Nick Gravin} and {Pinyan Lu}},
publisher = {SIAM},
booktitle = {Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018}
}
@article{journals/corr/abs-1802-02751,
title = {Monopoly pricing with buyer search.},
year = {2018},
journal = {CoRR},
author = {{Nick Gravin} and {Zhihao Gavin Tang}}
}
@article{journals/sigecom/GravinL18,
title = {Correlation-robust mechanism design.},
year = {2018},
journal = {SIGecom Exch.},
author = {{Nick Gravin} and {Pinian Lu}}
}
@inproceedings{conf/ec/CaragiannisGH19,
title = {Envy-Freeness Up to Any Item with High Nash Welfare: The Virtue of Donating Items.},
year = {2019},
booktitle = {EC},
author = {{Ioannis Caragiannis} and {Nick Gravin} and {Xin Huang}},
publisher = {ACM},
booktitle = {Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019.}
}
@inproceedings{conf/ec/GravinW19,
title = {Prophet Inequality for Bipartite Matching: Merits of Being Simple and Non Adaptive.},
year = {2019},
booktitle = {EC},
author = {{Nikolai Gravin} and {Hongao Wang}},
publisher = {ACM},
booktitle = {Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019.}
}
@inproceedings{conf/soda/BeiGLT19,
title = {Correlation-Robust Analysis of Single Item Auction.},
year = {2019},
booktitle = {SODA},
author = {{Xiaohui Bei} and {Nick Gravin} and {Pinyan Lu} and {Zhihao Gavin Tang}},
publisher = {SIAM},
booktitle = {Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019}
}
@inproceedings{conf/sigecom/EzraFGT20,
title = {Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models.},
year = {2020},
booktitle = {EC},
author = {{Tomer Ezra} and {Michal Feldman} and {Nick Gravin} and {Zhihao Gavin Tang}},
publisher = {ACM},
booktitle = {EC '20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020}
}
@article{journals/corr/abs-2011-01559,
title = {Secretary Matching with General Arrivals.},
year = {2020},
journal = {CoRR},
author = {{Tomer Ezra} and {Michal Feldman} and {Nick Gravin} and {Zhihao Gavin Tang}}
}
@article{journals/geb/FeldmanFGL20,
title = {Simultaneous auctions without complements are (almost) efficient.},
year = {2020},
journal = {Games Econ. Behav.},
author = {{Michal Feldman} and {Hu Fu 001} and {Nick Gravin} and {Brendan Lucier}}
}
@article{journals/teco/GravinJLZ20,
title = {Optimal Budget-Feasible Mechanisms for Additive Valuations.},
year = {2020},
journal = {ACM Trans. Economics and Comput.},
author = {{Nick Gravin} and {Yaonan Jin} and {Pinyan Lu} and {Chenhao Zhang 003}}
}
@inproceedings{conf/icalp/GravinTW21,
title = {Online Stochastic Matching with Edge Arrivals.},
year = {2021},
booktitle = {ICALP},
author = {{Nick Gravin} and {Zhihao Gavin Tang} and {Kangning Wang}},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
booktitle = {48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference).}
}
@inproceedings{conf/soda/GravinGKL21,
title = {Concentration bounds for almost k-wise independence with applications to non-uniform security.},
year = {2021},
booktitle = {SODA},
author = {{Nick Gravin} and {Siyao Guo} and {Tsz Chiu Kwok} and {Pinyan Lu}},
publisher = {SIAM},
booktitle = {Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021}
}
@inproceedings{conf/wine/CaragiannisGLW21,
title = {Relaxing the Independence Assumption in Sequential Posted Pricing, Prophet Inequality, and Random Bipartite Matching.},
year = {2021},
booktitle = {WINE},
author = {{Ioannis Caragiannis} and {Nick Gravin} and {Pinyan Lu} and {Zihe Wang 001}},
publisher = {Springer},
booktitle = {Web and Internet Economics - 17th International Conference, WINE 2021, Potsdam, Germany, December 14-17, 2021, Proceedings}
}
@article{journals/teco/ChengGMW21,
title = {A Simple Mechanism for a Budget-Constrained Buyer.},
year = {2021},
journal = {ACM Trans. Economics and Comput.},
author = {{Yu Cheng 002} and {Nick Gravin} and {Kamesh Munagala} and {Kangning Wang}}
}
@inproceedings{conf/sagt/FeldmanGTW22,
title = {Lookahead Auctions with Pooling.},
year = {2022},
booktitle = {SAGT},
author = {{Michal Feldman} and {Nick Gravin} and {Zhihao Gavin Tang} and {Almog Wald}},
publisher = {Springer},
booktitle = {Algorithmic Game Theory - 15th International Symposium, SAGT 2022, Colchester, UK, September 12-15, 2022, Proceedings}
}
@inproceedings{conf/sigecom/EzraFGT22,
title = {General Graphs are Easier than Bipartite Graphs: Tight Bounds for Secretary Matching.},
year = {2022},
booktitle = {EC},
author = {{Tomer Ezra} and {Michal Feldman} and {Nick Gravin} and {Zhihao Gavin Tang}},
publisher = {ACM},
booktitle = {EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022}
}
@inproceedings{conf/sigecom/FeldmanGG022,
title = {Bayesian and Randomized Clock Auctions.},
year = {2022},
booktitle = {EC},
author = {{Michal Feldman} and {Vasilis Gkatzelis} and {Nick Gravin} and {Daniel Schoepflin 001}},
publisher = {ACM},
booktitle = {EC '22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11 - 15, 2022}
}
@inproceedings{conf/wine/GravinLT22,
title = {Optimal Prophet Inequality with Less than One Sample.},
year = {2022},
booktitle = {WINE},
author = {{Nick Gravin} and {Hao Li} and {Zhihao Gavin Tang}},
publisher = {Springer},
booktitle = {Web and Internet Economics - 18th International Conference, WINE 2022, Troy, NY, USA, December 12-15, 2022, Proceedings}
}
@article{journals/corr/abs-2202-09215,
title = {On the Significance of Knowing the Arrival Order in Prophet Inequality.},
year = {2022},
journal = {CoRR},
author = {{Tomer Ezra} and {Michal Feldman} and {Nick Gravin} and {Zhihao Gavin Tang}}
}
@article{journals/corr/abs-2204-01418,
title = {The Cardinal Complexity of Comparison-based Online Algorithms.},
year = {2022},
journal = {CoRR},
author = {{Nick Gravin} and {Enze Sun} and {Zhihao Gavin Tang}}
}
@article{journals/mor/EzraFGT22,
title = {Prophet Matching with General Arrivals.},
year = {2022},
journal = {Math. Oper. Res.},
author = {{Tomer Ezra} and {Michal Feldman} and {Nick Gravin} and {Zhihao Gavin Tang}}
}
@article{journals/teco/HoeferCGM22,
title = {Introduction to the Special Issue on WINE'20: Part 1.},
year = {2022},
journal = {ACM Trans. Economics and Comput.},
author = {{Martin Hoefer 001} and {Xujin Chen} and {Nikolai Gravin} and {Ruta Mehta}}
}
@inproceedings{conf/focs/GravinST23,
title = {Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity.},
year = {2023},
booktitle = {FOCS},
author = {{Nick Gravin} and {Enze Sun} and {Zhihao Gavin Tang}},
publisher = {IEEE},
booktitle = {64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023}
}
@inproceedings{conf/soda/BeiGLT23,
title = {Bidder Subset Selection Problem in Auction Design.},
year = {2023},
booktitle = {SODA},
author = {{Xiaohui Bei} and {Nick Gravin} and {Pinyan Lu} and {Zhihao Gavin Tang}},
publisher = {SIAM},
booktitle = {Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023}
}
@inproceedings{conf/soda/EzraFGT23,
title = {"Who is Next in Line?" On the Significance of Knowing the Arrival Order in Bayesian Online Settings.},
year = {2023},
booktitle = {SODA},
author = {{Tomer Ezra} and {Michal Feldman} and {Nick Gravin} and {Zhihao Gavin Tang}},
publisher = {SIAM},
booktitle = {Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023}
}
@inproceedings{conf/www/JiaLLLZGT23,
title = {Online resource allocation in Markov Chains.},
year = {2023},
booktitle = {WWW},
author = {{Jianhao Jia} and {Hao Li} and {Kai Liu} and {Ziqi Liu} and {Jun Zhou 011} and {Nikolai Gravin} and {Zhihao Gavin Tang}},
publisher = {ACM},
booktitle = {Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023 - 4 May 2023}
}
@article{journals/corr/abs-2306-10648,
title = {Bidder Selection Problem in Position Auctions via Poisson Approximation.},
year = {2023},
journal = {CoRR},
author = {{Nick Gravin} and {Yixuan Even Xu} and {Renfei Zhou}}
}
@article{journals/mor/GravinW23,
title = {Prophet Inequality for Bipartite Matching: Merits of Being Simple and Nonadaptive.},
year = {2023},
month = {February},
journal = {Math. Oper. Res.},
author = {{Nick Gravin} and {Hongao Wang}}
}