Research

I am interested in problems at the intersection of economics and algorithms.

Papers in Preparation

- N. Immorlica, J. Leshno, I. Lo, and B. Lucier. Information Acquisition Costs in Matching Markets, in preparation.
- N. Immorlica, J. Mao, A. Slivkins, and S. Wu. Incentivizing Exploration with Unbiased Histories, in preparation.
- N. Immorlica, M. Jackson, and E.G. Weyl. Verifying Identity as a Social Intersection, in preparation.
- J. Eguia, N. Immorlica, K. Ligett, E.G. Weyl, and D. Xefteris. A New Consensus Protocol: Quadratic Voting with Multiple Alternatives, in preparation.
- N. Immorlica, S. Singla, and B. Waggoner. Prophet Inequalities with Linear Correlations, in preparation.
- N. Immorlica, K.A. Sankararaman, R. Schapire, and A. Slivkins. Adversarial Bandits with Knapsacks, in preparation.
- M. Bahrani, N. Immorlica, D. Mohan, and M. Weinberg. Asynchronous Majority Dynamics in Preferential Attachment Trees, in preparation.

Selected Publications

- N. Immorlica and R.D. Kleinberg. Recharging Bandits, FOCS 2018.
- Y. Chen, N. Immorlica, B. Lucier, V. Syrgkanis, and J. Ziani. Optimal Data Acquisition for Statistical Estimation, EC 2018.
- N. Immorlica, R. Kranton, M. Manea, and G. Stoddard. Social Status in Networks, AEJ Micro 2017, lead article. Conference version: N. Immorlica, R. Kranton, and G. Stoddard, Striving for Social Status, EC 2012.
- M. Feldman, N. Immorlica, B. Lucier, T. Roughgarden, and V. Syrgkanis. The Price of Anarchy in Large Games, STOC 2016.
- N. Immorlica, G. Stoddard, and V. Syrgkanis. Social Status and Badge Design, WWW 2015.
- M. Babaioff, N. Immorlica, B. Lucier, and M. Weinberg. A Simple and Approximately Optimal Mechanism for an Additive Buyer, FOCS 2014.
- M. Feldman, N. Immorlica, B. Lucier, and M. Weinberg. Reaching Consensus via non-Bayesian Asynchronous Learning in Social Networks, APPROX 2014.
- N. Immorlica, B. Lucier, and B. Rogers. Emergence of Cooperation in Anonymous Social Networks through Social Capital, EC 2010.
- M. Babaioff, N. Immorlica, and R. Kleinberg. Matroids, Secretary Problems, and Online Mechanisms, SODA 2007.
- N. Immorlica and M. Mahdian. Incentives in Large Random Two-Sided Markets, Transactions on Economics and Computation, 2015. Conference version entitled "Marriage, Honesty, and Stability" appeared in SODA 2005.

Online Talks

- International Joint Conferences on Artificial Intelligence (IJCAI) 2018, Keynote Talk: Maximizing the Social Good: Markets without Money, Simons Institute for the Theory of Computing, Berkeley, October 2015.
- Economics and Computation Semester, Complexity and Simplicity in Economics Workshop: The Emergent Structure of Simple Behaviors in Complex Networks, Simons Institute for the Theory of Computing, Berkeley, October 2015.
- Innovations in Algorithmic Game Theory: Dueling Algorithms, Hebrew University, May 2011.

Full Publication List

- N. Immorlica, J. Mao, A. Slivkins, and S. Wu. Bayesian Exploration with Heterogeneous Agents, The Web Conference 2019, selected for oral presentation.
- N. Immorlica, J. Mao, and C. Tzamos. Diversity and Exploration in Social Learning, The Web Conference 2019.
- L. Hu, N. Immorlica, and J. Wortman Vaughan. The Disparate Effects of Strategic Manipulation, FATSTAR 2019.
- N. Immorlica, K. Ligett, and J. Ziani. Access to Population-Level Signaling as a Source of Inequality, FATSTAR 2019.
- N. Immorlica, B. Lucier, J. Mao, V. Syrgkanis, and C. Tzamos. Combinatorial Assortment Optimization, WINE 2018.
- N. Immorlica and R.D. Kleinberg. Recharging Bandits, FOCS 2018.
- Y. Chen, N. Immorlica, B. Lucier, V. Syrgkanis, and J. Ziani. Optimal Data Acquisition for Statistical Estimation, EC 2018.
- J. Hartline, N. Immorlica, B. Lucier, and R. Niazadeh. A Faster Algorithm for Bidder-Optimal Core Points, EC 2018.
- N. Newman, L. Bergquist, N. Immorlica, K. Leyton-Brown, B. Lucier, C. McIntosh, R. Ssekibuule, and J. Quinn. Designing and Evolving an Electronic Marketplace for Agricultural Trade in Uganda, COMPASS 2018.
- D. Alabi, N. Immorlica, and A. Kalai. When Optimizing nonlinear objectives is no harder than linear objectives, COLT 2018.
- C. Dwork, N. Immorlica, A. Kalai, and M. Leiserson. Decoupled classifiers for group-fair and efficient machine learning, FAT* 2018.
- B. Wilder, N. Immorlica, E. Rice, and M. Tambe. Maximizing Influence in an Unknown Social Network, AAAI 2018.
- E. Balkanski, N. Immorlica, and Y. Singer. The Importance of Communities for Learning to Influence, NIPS 2017.
- N. Immorlica, B. Lucier, E. Pountourakis, and S. Taggart. Repeated Sales with Multiple Strategic Buyers, EC 2017.
- N. Immorlica, B. Lucier, J. Mollner, and E.G. Weyl. Approximate Efficiency in Matching Markets, WINE 2017.
- N. Immorlica, R.D. Kleinberg, B. Lucier, and M. Zadomighaddam. Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals, SODA 2017.
- Bryan Wilder, Amulya Yadav, Nicole Immorlica, Eric Rice and Milind Tambe. Uncharted but not Uninfluenced: Influence Maximization with an Uncertain Network, AAMAS 2017, full paper.
- M. Feldman, N. Immorlica, B. Lucier, T. Roughgarden, and V. Syrgkanis. The Price of Anarchy in Large Games, STOC 2016.
- N. Gravin, N. Immorlica, B. Lucier, and E. Pountourakis. Procrastination with Variable Present Bias, EC 2016.
- D. Hoy, N. Immorlica, and B. Lucier. On-Demand or Spot? Selling the cloud to risk-averse customers, WINE 2016.
- N. Immorlica, G. Stoddard, and V. Syrgkanis. Social Status and Badge Design, WWW 2015.
- H. Fu, N. Immorlica, B. Lucier, and P. Strack. Randomization beats Second Price as a Prior-Independent Auction, EC 2015.
- N. Arnosti, N. Immorlica, and B. Lucier,The (Non)-Existence of Stable Mechanisms in Incomplete Information Environments, WINE 2015.
- U. Feige, M. Feldman, N. Immorlica, R. Izsak, B. Lucier, and V. Syrgkanis. A Unifying Hierarchy of Valuations with Complements and Substitutes, AAAI 2015.
- S. Dughmi, N. Immorlica, R. O'Donnell, and L. Tan, Algorithmic Signaling of Features in Auction Design, SAGT 2015.
- M. Babaioff, N. Immorlica, B. Lucier, and M. Weinberg. A Simple and Approximately Optimal Mechanism for an Additive Buyer, FOCS 2014.
- M. Feldman, N. Immorlica, B. Lucier, and M. Weinberg. Reaching Consensus via non-Bayesian Asynchronous Learning in Social Networks, APPROX 2014.
- B. Rastegari, A. Condon, N. Immorlica, R. Irving, and K. Leyton-Brown. Reasoning about optimal stable matchings under partial information, EC 2014.
- S. Dughmi, N. Immorlica, and A. Roth. Constrained Signaling in Auction Design, SODA 2014.
- B. Rastegari, A. Condon, N. Immorlica, and K. Leyton-Brown. Two-Sided Matching with Partial Information, EC 2013.
- G. Askalidis, N. Immorlica, A. Kwanashie, D. Manlove, and E. Pountourakis. Socially Stable Matchings in the Hospitals/Residents Problem, WADS 2013.
- C. Brandt, N. Immorlica, G. Kamath and R.D. Kleinberg. An Analysis of One-Dimensional Schelling Segregation, STOC 2012. Great article about this problem in the popular press.
- S. Chawla, N. Immorlica, and B. Lucier. On the Limits of Black-Box Reductions in Mechanism Design, STOC 2012.
- N. Immorlica and E. Pountourakis. On Budget-Balanced Group-Strategyproof Cost-Sharing Mechanisms, WINE 2012.
- N. Immorlica, R. Kranton, M. Manea, and G. Stoddard. Social Status in Networks, AEJ Micro 2017, lead article. Conference version: N. Immorlica, R. Kranton, and G. Stoddard, Striving for Social Status, EC 2012.
- N. Immorlica, M. Mahdian, and G. Stoddard. Optimal User Search, Ad Auction Workshop 2012.
- N. Immorlica and B. Lucier. On the Impossibility of Black-Box Truthfulness without Priors , Workshop on Bayesian Mechanism Design (WBMD), 2011.
- J. Hatfield, N. Immorlica, and S.D. Kominers. Testing Substitutability, to appear in Games and Economic Behavior, 2011.
- N. Immorlica, A. Tauman Kalai, B. Lucier, A. Moitra, A. Postlewaite, and M. Tennenholtz. Dueling Algorithms, STOC 2011.
- N. Haghpanah, N. Immorlica, V. Mirrokni, K. Munagala. Optimal Auctions with Positive Network Externalities, to appear in ACM Transactions on Economics and Computation. Conference version appeared in EC 2011.
- N. Immorlica, E. Markakis, G. Piliouras Coalition Formation and Price of Anarchy in Cournot Oligopolies, WINE 2010.
- V. Conitzer, N. Immorlica, J. Letchford, K. Munagala, and L. Wagman. False-name-proofness in Social Networks, WINE 2010.
- N. Anari, S. Ehsani, M. Ghodsi, N. Haghpanah, N. Immorlica, H. Mahini, and V. Mirrokni. Equilibrium Pricing with Positive Externalities, WINE 2010. Journal version to appear in Theoretical Computer Science.
- N. Immorlica, B. Lucier, and B. Rogers. Emergence of Cooperation in Anonymous Social Networks through Social Capital, EC 2010.
- M.H. Bateni, M.T. Hajiaghayi, N. Immorlica, and H. Mahini. The cooperative game theory foundations of network bargaining games, ICALP 2010.
- R. Gomes, N. Immorlica, and V. Markakis. Externalities in Keyword Auctions: an Empirical and Theoretical Assessment, Workshop on Internet and Network Economics (WINE), 2009.
- U. Feige, N. Immorlica, V. Mirrokni, and H. Nazerzadeh. PASS Approximation: A Framework for Analyzing and Designing Heuristics, 2009. Conference version appeared in APPROX, 2009.
- N. Chen, N. Immorlica, A. Karlin, M. Mahdian, and A. Rudra. Approximating Matches Made in Heaven, ICALP 2009.
- M. Babaioff, M. Dinitz, A. Gupta, N. Immorlica, and K. Talwar. Secretary Problems: Weights and Discounts, SODA 2009.
- C. Borgs, J. Chayes, N. Immorlica, A. Kalai, V. Mirrokni, and C. Papadimitriou. The Myth of the Folk Theorem, Games and Economic Behavior, 2009. Conference version appeared in STOC 2008.
- U. Feige, N. Immorlica, V. Mirrokni, and H. Nazerzadeh. A Combinatorial Allocation Mechanism for Banner Advertisement with Penalties, WWW 2008.
- N. Immorlica, A. Karlin, M. Mahdian, and K. Talwar. Balloon popping with applications to ascending auctions, FOCS 2007.
- M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg.A Knapsack Secretary Problem with Applications, APPROX 2007.
- N. Immorlica, J. Kleinberg, M. Mahdian, and T. Wexler. The role of compatibility in the diffusion of technologies in social networks, EC 2007.
- C. Borgs, J. Chayes, O. Etesami, N. Immorlica, K. Jain, and M. Mahdian. Dynamics of bid optimization in online advertisement auctions, WWW 2007.
- M. Babaioff, N. Immorlica, and R. Kleinberg. Matroids, Secretary Problems, and Online Mechanisms, SODA 2007.
- N. Immorlica, K. Jain, and M. Mahdian. Game-Theoretic Aspects of Designing Hyperlink Structures, Workshop on Internet and Network Economics (WINE), 2006.
- N. Immorlica, R. Kleinberg, and M. Mahdian. Secretary Problems with Competing Employers, Workshop on Internet and Network Economics (WINE), 2006.
- B. Dean, M. Goemans, and N. Immorlica. Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data, European Symposium on Algorithms (ESA), 2006.
- B. Dean, M. Goemans, and N. Immorlica. The Unsplittable Stable Marriage Problem, IFIP International Conference on Theoretical Computer Science (IFIP TCS), 2006.
- N. Immorlica, L. Li, V. Mirrokni, and A. Schulz. Coordination Mechanisms for Selfish Scheduling, Workshop on Internet and Network Economics (WINE), 2005. Full version: Theoretical Computer Science WINE 2005 special issue, volume 410, number 17, April 2009, pages 1589-1598.
- N. Immorlica, K. Jain, M. Mahdian, and K. Talwar. Click Fraud Resistant Methods for Learning Click-Through Rates, Workshop on Internet and Network Economics (WINE), 2005.
- G. Aggarwal, A. Fiat, A. Goldberg, J. Hartline, N. Immorlica, and M. Sudan. Derandomization of Auctions, Games and Economic Behavior, 2010. Conference version appeared in STOC 2005.
- N. Immorlica, D. Karger, E. Nikolova, and R. Sami. First-Price Procurement Auctions, 2010. Conference version: First-Price Path Auctions appeared in EC, 2005.
- C. Borgs, J. Chayes, N. Immorlica, M. Mahdian, and A. Saberi. Multi-Unit Auctions with Budget-Constrained Bidders, EC 2005.
- N. Immorlica and M. Mahdian. Incentives in Large Random Two-Sided Markets, Transactions on Economics and Computation, 2015. Conference version appeared in SODA 2005.
- N. Immorlica, M. Mahdian, and V. Mirrokni. Limitations of cross-monotonic cost-sharing schemes, ACM Transactions on Algorithms special issue, volume 4, number 2, April 2008. Conference version appeared in SODA 2005 and was winner of the best student paper award.
- N. Immorlica and S. Chien. Semantic Similarity between Search Engine Queries Using Temporal Correlation, WWW 2005.
- R. Bhatia, N. Immorlica, T. Kimbrel, V.S. Mirrokni, S. Naor, B. Schieber. Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees, Theory of Computing Systems, volume 41, number 1, January 2008, pages 2-26. Conference version appeared in SPAA 2005.
- N. Immorlica, M. Mahdian, and V. Mirrokni. Cycle cover with short cycles, STACS 2005.
- N. Immorlica, D. Karger, M. Minkoff, and V. Mirrokni. On the Costs and Benefits of Procrastination: Approximation Algorithms for Stochastic Combinatorial Optimization Problems, SODA 2004.
- M. Datar, N. Immorlica, P. Indyk, and V. Mirrokni. Locality-Sensitive Hashing Scheme Based on p-Stable Distributions, SoCG 2004.
- E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Correlation Clustering in General Weighted Graphs, Theoretical Computer Science special issue, volume 361, number 2-3, September 2006, pages 172-187. Conference version (E.D. Demaine and N. Immorlica, Correlation Clustering with Partial Information) appeared in APPROX 2003.
- Y. Bejarano, N. Immorlica, S. Noar, and M. Smith. Location Area Design in Cellular Networks, MOBICOM 2003. Full version: Efficient Location Area Planning for Personal Communication Systems, IEEE/ACM Transactions on Networking, volume 14, number 2, April 2006, pages 438-450.
- M. Hajiaghayi, N. Immorlica, and V. Mirrokni. Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-hop Networks, IEEE/ACM Transactions on Networking, volume 15, issue 6, December 2007, pages 1345-1358. Conference version appeared in MOBICOM 2003.

Surveys, Book Chapters

- M. Babaioff, N. Immorlica, B. Lucier, and S.M. Weinberg A Simple and Approximately Optimal Mechanism for an Additive Buyer, SIGecom Exchanges 13(2), December 2014.
- N. Immorlica. Why I don't rob banks for a living, ACM XRDS Crossroads, March 2011.
- M. Babaioff, N. Immorlica, D. Kempe, and R.D. Kleinberg. Online Auctions and Generalized Secretary Problems, SIGecom Exchanges 7(2), June 2008.
- N. Immorlica and A. Wirth.
"Clustering with Qualitative Information", in
__Constrained Clustering: Advances in Algorithms, Theory, and Applications__, S. Basu, I. Davidson, and K. Wagstaff (eds.), Chapman & Hall/CRC Press, 2008, pages 313-328. - A. Andoni, M. Datar,
N. Immorlica, P. Indyk, and V. Mirrokni. "Locality-sensitive
hasing using stable distributions", in
__Nearest Neighbor Methods in Learning and Vision: Theory and Practice__, T. Darrell, P. Indyk, and G. Shakhnarovich (eds.), MIT Press, 2006.

Thesis

- Ph.D. Thesis, Computing With Strategic Agents
- Masters Thesis, Data Acquisition System Design for the Alpha Magnetic Spectrometer