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 in Matching Markets: The Role of Price Discovery, in preparation. [talk]
- L. Bolte, N. Immorlica, and M. Jackson. The Role of Referrals in Inequality, Immobility and Inefficiency in Labor Markets, in preparation. [talk]
- J. Eguia, N. Immorlica, K. Ligett, E.G. Weyl, and D. Xefteris. A New Consensus Protocol: Quadratic Voting with Multiple Alternatives, in preparation.
Selected Publications
- M. Babaioff, R. Cole, J. Hartline, N. Immorlica, and B. Lucier. Non-Quasi-Linear Agents in Quasi-Linear Mechanisms, ITCS 2021.
- N. Immorlica, J. Mao, A. Slivkins, and S. Wu. Incentivizing Exploration with Selective Data Disclosure, EC 2020.
- 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. Journal of the ACM 2020.
- 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, D. Kempe and R. Kleinberg.
Matroid Secretary Problems, Journal of the ACM 2018.
- 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
- Virtual Seminars in Economic Theory (VSET): Communicating with Anecdotes, virtual, December 2021.
- International Joint Conferences on Artificial Intelligence (IJCAI) 2018, Keynote Talk: Maximizing the Social Good: Markets without Money, Stockholm, Sweden, July 2018.
- 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
- M. Babaioff, R. Cole, J. Hartline, N. Immorlica, and B. Lucier. Non-Quasi-Linear Agents in Quasi-Linear Mechanisms, ITCS 2021.
- G. Allon, G. Askaladis, R. Berry, N. Immorlica, K. Moon and A. Singh. When to Be Agile: Ratings and Version Updates in Mobile Apps, Management Science 2021.
- N. Immorlica, J. Mao, A. Slivkins, and S. Wu. Incentivizing Exploration with Selective Data Disclosure, EC 2020.
- N. Immorlica, S. Singla, and B. Waggoner. Prophet Inequalities with Linear Correlations, EC 2020.
- N. Haghtalab, N. Immorlica, B. Lucier, and J. Wang. Maximizing Welfare with Incentive-Aware Evaluation Mechanisms, IJCAI 2020.
- M. Bahrani, N. Immorlica, D. Mohan, and M. Weinberg. Asynchronous Majority Dynamics in Preferential Attachment Trees, ICALP 2020.
- K. Goldner, N. Immorlica, and B. Lucier. Reducing Inefficiency in Carbon Auctions with Imperfect Competition, ITCS 2020.
- N. Immorlica, B. Plaut, and G. Weyl. Equality of Power and Fair Public Decision-Making, WINE 2019.
- N. Immorlica, K.A. Sankararaman, R. Schapire, and A. Slivkins. Adversarial Bandits with Knapsacks, FOCS 2019.
- 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, M.R. Khani, B. Lucier, and R. Niazadeh. Fast Core Pricing for Rich Advertising Auctions, 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. Forthcoming in Journal of the ACM.
- 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.
- M. Babaioff, N. Immorlica, D. Kempe and R. Kleinberg.
Matroid Secretary Problems, Journal of the ACM 2018. Conference version: 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
- N. Immorlica The Design of Everyday Markets, The Future of Economic Design, In: Laslier JF., Moulin H., Sanver M., Zwicker W. (eds) , Springer 2019, pp 517-522.
- 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