Ning Chen Associate Professor

Division of Mathematical Sciences
School of Physical and Mathematical Sciences
Nanyang Technological University
Singapore, 637371

Office: SPMS-05-46
Phone: (65) 6513 2029
Email: ningc [at] ntu.edu.sg


I got my Ph.D. from Computer Science & Engineering of the University of Washington at Seattle in 2008. My advisor was Professor Anna Karlin.

My research interests include:
  • Algorithmic Game Theory and Computational Economics
  • Algorithmic and Economic aspects of the Internet
  • Algorithms and Combinatorial Optimization
  • My photo portfolio.


    Publications

    • Optimal Competitive Auctions.
      Ning Chen, Nick Gravin, and Pinyan Lu.
      • ACM Symposium on Theory of Computing (STOC), 2014.
    • Truthful Generalized Assignments via Stable Matching.
      Ning Chen, Nick Gravin, and Pinyan Lu.
      • To appear in Mathematics of Operations Research.
    • Trial and Error in Influential Social Networks.
      Xiaohui Bei, Ning Chen, Liyu Dou, Xiangru Huang, and Ruixin Qiang.
      • ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2013.
    • On the Complexity of Trial and Error.
      Xiaohui Bei, Ning Chen, and Shengyu Zhang.
      • ACM Symposium on Theory of Computing (STOC), 2013.
    • Auctions for Social Lending: A Theoretical Analysis.
      Ning Chen, Arpita Ghosh, and Nicolas Lambert.
      • To appear in Games and Economic Behavior.
      • Subsumes earlier paper, titled "Social Lending", in ACM Conference on Electronic Commerce (EC), 2009.
    • Envy-Free Pricing in Multi-Item Markets.
      Ning Chen, and Xiaotie Deng.
      • To appear in ACM Transactions on Algorithms.
      • Subsumes earlier paper in International Colloquium on Automata, Languages and Programming (ICALP), 2010.
    • Improved Approximation Algorithms for the Spanning Star Forest Problem.
      Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, and Gyanit Singh.
      • Algorithmica, V.65(3), 498-516, 2013.
      • Subsumes earlier paper in International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2007.
    • Incentive Ratios of Fisher Markets.
      Ning Chen, Xiaotie Deng, Hongyang Zhang, and Jie Zhang.
      • International Colloquium on Automata, Languages and Programming (ICALP), 2012.
    • Computing the Nucleolus of Matching, Cover and Clique Games.
      Ning Chen, Pinyan Lu, and Hongyang Zhang
      • AAAI Conference on Artificial Intelligence (AAAI), 2012.
    • Optimal Proportional Cake Cutting with Connected Pieces.
      Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, and Endong yang.
      • AAAI Conference on Artificial Intelligence (AAAI), 2012.
    • Budget Feasible Mechanism Design: From Prior-Free to Bayesian.
      Xiaohui Bei, Ning Chen, Nick Gravin, and Pinyan Lu.
      • ACM Symposium on Theory of Computing (STOC), 2012.
    • On Computing Pareto Stable Assignments.
      Ning Chen.
      • Symposium on Theoretical Aspects of Computer Science (STACS), 2012.
    • How Profitable are Strategic Behaviors in a Market?.
      Ning Chen, Xiaotie Deng, and Jie Zhang.
      • European Symposium on Algorithms (ESA), 2011.
    • A Market Clearing Solution for Social Lending.
      Ning Chen, and Arpita Ghosh.
      • International Joint Conference on Artificial Intelligence (IJCAI), 2011.
    • Dynamics of Profit-Sharing Games.
      John Augustine, Ning Chen, Edith Elkind, Angelo Fanelli, Nick Gravin, and Dmitry Shiryaev.
      • International Joint Conference on Artificial Intelligence (IJCAI), 2011.
    • On the Approximability of Budget Feasible Mechanisms.
      Ning Chen, Nick Gravin, and Pinyan Lu.
      • ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
    • A Note on k-Shortest Paths Problem.
      Nick Gravin, and Ning Chen.
      • Journal of Graph Theory, V.67(1), 34-37, 2011.
    • Optimal Envy-free Pricing with Metric Substitutability.
      Ning Chen, Arpita Ghosh, and Sergei Vassilvitskii.
      • SIAM Journal on Computing, V.40(3), 623-645, 2011.
      • Subsumes earlier paper in ACM Conference on Electronic Commerce (EC), 2008.
    • Competitive Equilibria in Matching Markets with Budgets.
      Ning Chen, Xiaotie Deng, and Arpita Ghosh.
      • ACM SIGecom Exchanges, V.9.1, 2010.
    • Frugal Mechanism Design via Spectral Techniques.
      Ning Chen, Edith Elkind, Nick Gravin, and Fedor Petrov.
      • IEEE Symposium on Foundations of Computer Science (FOCS), 2010.
    • Strongly Stable Assignment.
      Ning Chen, and Arpita Ghosh.
      • European Symposium on Algorithms (ESA), 2010.
    • Dynamic Pricing for Impatient Bidders.
      Nikhil Bansal, Ning Chen, Neva Cherniavsky, Atri Rudra, Baruch Schieber, and Maxim Sviridenko.
      • ACM Transactions on Algorithms, V.6(2), 35, 2010.
      • Subsumes earlier paper in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007.
    • Deterministic Decentralized Search in Random Graphs.
      Esteban Arcaute, Ning Chen, Ravi Kumar, David Liben-Nowell, Mohammad Mahdian, Hamid Nazerzadeh, and Ying Xu.
      • Internet Mathematics, V.5(1), 141-154, 2010.
      • Subsumes earlier paper in Workshop on Algorithms and Models for the Web-Graph (WAW), 2007.
    • Refining the Cost of Cheap Labor in Set System Auctions.
      Ning Chen, Edith Elkind, and Nick Gravin.
      • International Workshop on Internet and Network Economics (WINE), 2009.
    • Approximating Matches Made in Heaven.
      Ning Chen, Nicole Immorlica, Anna Karlin, Mohammad Mahdian and Atri Rudra.
      • International Colloquium on Automata, Languages and Programming (ICALP), 2009.
    • On the Approximability of Influence in Social Networks.
      Ning Chen.
      • SIAM Journal on Discrete Mathematics. V.23(3), 1400-1415, 2009.
      • Subsumes earlier paper in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.
    • Walrasian Equilibrium: Hardness, Approximations and Tractable Instances.
      Ning Chen, and Atri Rudra.
      • Algorithmica, V.52(1), 44-64, 2008.
      • Subsumes earlier paper in International Workshop on Internet and Network Economics (WINE), 2005. (Best Student Paper Award.)
    • Cheap Labor Can Be Expensive. (with a correction of a bug in the SODA version)
      Ning Chen, and Anna Karlin.
      • ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007.
    • Assignment Problems in Rental Market.
      David Abraham, Ning Chen, Vijay Kumar, and Vahab Mirrokni.
      • International Workshop on Internet and Network Economics (WINE), 2006.
    • Fisher Equilibrium Price with Concave Utility Functions.
      Ning Chen, Xiaotie Deng, Xiaoming Sun, and Andrew Chi-Chih Yao.
      • European Symposium on Algorithms (ESA), 2004.
    • Dynamic Price Sequence and Incentive Compatibility.
      Ning Chen, Xiaotie Deng, Xiaoming Sun, and Andrew Chi-Chih Yao.
      • International Colloquium on Automata, Languages and Programming (ICALP), 2004.
    • On Complexity of Single-Minded Auction.
      Ning Chen, Xiaotie Deng, and Xiaoming Sun.
      • Journal of Computer and System Sciences, V.69(4), 675-687, 2004.
    • Fully Truthful Mechanisms.
      Ning Chen, and Hong Zhu.
      • International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2004. (Best Student Paper Award.)
    • Combinatorial Auction across Independent Markets.
      Ning Chen, Xiaotie Deng, and Hong Zhu.
      • ACM Conference on E-Commerce (EC),2003.
    • Approximation for Dominating Set Problem with Measure Functions.
      Ning Chen, Jie Meng, Jiawei Rong, and Hong Zhu.
      • Computing and Informatics, V.23, 1001-1013, 2004.

    My new adventure: Nestia - a portal for Singapore property rental.

    Last Update: May 23, 2013