I am an Associate Professor at

School of Information Management and Engineering

Shanghai University of Finance and Economics

EMAIL: nikolai (*) mail (dot) shufe (dot) edu (dot) cn

I used to work at MIT CSAIL and at Microsoft Research New England

Received PhD in mathematics from St.Petersburg department of Steklov Institute of Mathematics

and a PhD in theoretical computer science from Nanyang Technological University 

My supervisors were Dmitrii Karpov</A> (Steklov Institute) and Dmitrii Pasechnik</A> (NTU).

I've received a Microsoft Research fellowship in 2011. 

Research interests

1·Algorithmic Game Theory

• Auctions and Mechanism design

• Online algorithms

• Behavioral Economics

  

2·Computational learning

• Online learning

• Property testing

  

  

3.Combinatorics and Geometry

Program Committee

I am a PC chair of WINE 2020 (Conference on Web and Internet Economics) at Peking University

Cirriculum Vitae

Resume

Research papers

Works under submission/preparation

1. C. Daskalakis, N. Dikkala, N. Gravin.

Testing from One Sample: Is the casino really using a riffle shuffle?

(arxiv)

2.Y. Azar, M. Feldman, N. Gravin, A. Roytman.

Liquid Price of Anarchy

(arxiv)

3.N. Gravin, D. Pasechnik, B. Shapiro, M. Shapiro

On moments of a polytope.

(arxiv)

Publications

Computer Science

1. N. Gravin, Y. Peres, B. Sivan. (arxiv)
   Tight Lower Bounds for Multiplicative Weights Algorithmic Families
   Forthcoming, ICALP 2017.

2. N. Gravin, N. Immorlica, B. Lucier, E. Pountourakis. (arxiv)
   Procrastination with Variable Present Bias
   p.361, ACM EC 2016.

3. N. Gravin, Y. Peres, B. Sivan. (arxiv)
   Towards Optimal Algorithms for Prediction with Expert Advice.
   p. 528-547, SODA 2016.

4. N. Chen, N. Gravin, P. Lu. (arxiv)
   Competitive analysis via benchmark decomposition.
   p. 363-376, EC 2015.

5. M. Feldman, N Gravin, B. Lucier. (arxiv)
   Combinatorial Auctions via Posted Prices.
   p. 123--135, SODA 2015.

6. I. Caragiannis, A. Fanelli, N. Gravin. (arxiv)
   Short Sequences of Improvement Moves Lead to
   Approximate Equilibria in Constraint Satisfaction Games
   p. 49--60, SAGT 2014.
   Journal version accepted to Algorithmica

7. N. Chen, N. Gravin, P. Lu (arxiv)
   Optimal Competitive Auctions.
   p. 253--262, STOC 2014.

8. N. Chen, N. Gravin, P. Lu. (arxiv)
   Truthful Generalized Assignments via Stable Matching.
   Mathematics of Operations Research p. 722-736, v. 39, n. 3, 2014

9. N. Gravin, P. Lu. (arxiv)
   Competitive Auctions for Markets with Positive Externalities.
   p. 569-580, ICALP 2013.

10. M. Feldman, N Gravin, B. Lucier. (arxiv)
    Combinatorial Walrasian Equilibrium
    p. 61-70, STOC 2013.
    Journal version to appear in SIAM Journal of Computing

11. M. Feldman, Hu Fu, N Gravin, B. Lucier. (arxiv)
    Simultaneous Auctions are (almost) Efficient
    p. 201-210, STOC 2013.
    (Invited to the special issue of Games and Economic Behavior)

12. I. Caragiannis, A. Fanelli, N. Gravin, A. Skopalik.
    Computing approximate pure Nash equilibria in congestion games.
    p. 26-29, SIGecom Exchanges 2012.

13. I. Caragiannis, A. Fanelli, N. Gravin, A. Skopalik. (arxiv)
    Approximate Pure Nash Equilibria in Weighted Congestion Games:
    Existence, Efficient Computation, and Structure.
    p.284-301, EC 2012.
    (Invited to the special issue of ACM Transactions on Economics and Computation)

14. X. Bei, N. Chen, N. Gravin, P. Lu (arxiv)
    Budget Feasible Mechanism Design: From Prior-Free to Bayesian
    p. 449-458, STOC 2012.

15. I. Caragiannis, A. Fanelli, N. Gravin, A. Skopalik. (arxiv)
    Efficient computation of approximate pure Nash equilibria in congestion games.
    p. 532-541, FOCS 2011.

16. J. Augustine, N. Chen, E. Elkind, A. Fanelli, N. Gravin, D. Shiryaev. (arxiv)
    Dynamics of Profit-Sharing Games.
    p. 37-42, IJCAI 2011.

17. N. Chen, N. Gravin, P. Lu. (arxiv)
    On the Approximability of Budget Feasible Mechanisms.
    p. 685-699, SODA 2011.

18. J. Augustine, N. Gravin. (arxiv)
    On the Continuous CNN Problem.
    p. 254-265, ISAAC 2010.

19. N. Gravin. (pdf)
    Time optimal d-list colouring of a graph.
    p. 156-168, CSR 2010.

20. N. Chen, E. Elkind, N. Gravin, F. Petrov. (arxiv)
    Frugal Mechanism Design via Spectral Techniques.
    p. 755-764, FOCS 2010.

21. N. Chen, E. Elkind and N. Gravin. (pdf )
    Refining the Cost of Cheap Labor in Set System Auctions.
    p. 447-454, WINE 2009.

Mathematics

1. N. Gravin, F. Petrov, D. Shiryaev, S. Robins (arxiv)
   Poisson imitation of lattices and convex curves
   Mathematika, v. 60, i. 01, pp. 139- 152, 2014.

2. N. Gravin, M. Kolountzakis, S. Robins, D. Shiryaev. (arxiv)
   Structure results for multiple tilings in 3D
   Discrete and Computational Geometry. v. 50, i. 4, p. 1033-1050, 2013

3. N. Gravin, S. Robins, D. Shiryaev. (arxiv)
   Translational tilings by a polytope, with multiplicity.
   Combinatorica, v. 32, i. 6 , p. 629-649, 2012.

4. N. Gravin, J. Lasserre, D. Pasechnik, S. Robins (arxiv)
   The inverse moment problem for convex polytopes.
   Discrete and Computational Geometry, v. 48(3), p. 596-621, 2012.

5. N. Gravin, D. Karpov. (arxiv)
   On proper colorings of hypergraphs.
   (Russian) Zapiski Nauchnykh Seminarov POMI, v. 391, p. 79–89, 2011.
   English translation in Journal of Mathematical Sciences v. 184, i. 5, p. 595-600.

6. N. Chen, N. Gravin. (pdf)
   Note on Shortest k-Paths Problem.
   Journal of Graph Theory. v. 67(1), p. 34-37, 2011.

7. N. Gravin. (arxiv.org, PDMI preprints)
   Non-degenerate colorings in the Brook's theorem.
   (in Russian) Diskretnay Matematika, v. 21-4, p. 106-128, 2009.
   Discrete Mathematics and Applications.

8. N. Gravin, D. Y. Shiryaev. (.pdf in Russian, translation in English)
   Abnormal subgroups of classical groups corresponding to closed sets of roots
   (Russian) Zap. Nauchn. Sem. POMI, v. 365, p. 151-171, 2009.
   Journal of Mathematical Sciences, v. 161:4, p. 542-552, 2009.

9. N. Gravin. (pdf in Russian)
   Construction of a spanning tree with many leaves.
   (in Russian) Zap. Nauchn. Sem. POMI p. 31-46, 2010.
   (translated into English by Springer in ``Journal of Mathematical Sciences'').

Technical reports

1. N. Gravin, D. Nguyen, D. Pasechnik, S. Robins. (arxiv)
   The Inverse Moment problem for convex polytopes: implementation aspects.
   2014.

PhD  Theses

1. Thesis at PDMI (in Russian). Some aspects of proper graph colouring.

2. Thesis at NTU. Incentive Compatible Design of Reverse Auctions.

Teaching

Spring semester 2018. Discrete Mathematics(1643)

• Location: building 3, room 501.

• lecture notes: Mathematics for Computer Science by Eric Lehman, Thomson Leighton, Albert R Meyer, also avaliable here.

Problems. Discrete Mathematics

• Problem Set 1.pdf

Spring semester 2018. Incentives, Information, and Mechanism design(0188)

• Location: building 3, room 501.

• lecture notes: Mechanism Design and Approximation  by Jason Hartline, also avaliable here and here.

• Text book: Game Theory, Alive  by Anna Karlin and Yuval Peres, also avaliable here.

• Chapter 1. Slides.

• Chapter 2. Slides.

Problems. Mechanism Design

Useful books

• BondyMurty.pdf

• ConcreteMath.pdf

• GTWA.pdf

• Diestel.pdf

• Cameron.djvu

Contacts

The Fastest Way

Email:n + my last name, domain: gmail.com

Snail mail

Address:

School of Information Management & Engineering,

Shanghai University of Finance & Economics

100 Wudong Road,

Yangpu District, Shanghai 200433,China