Showing 1–50 of 66 results for author: Immorlica, N

The Evolution of Digital Search: From Blue Links to Delegated Decision-Making

Authors: David M. Rothschild, Nicole Immorlica, Brendan Lucier, Markus Mobius, Aleksandrs Slivkins

Abstract: Digital search is undergoing a fundamental transformation from a human-driven process of discovery to an agent-mediated system of delegated decision-making. In the traditional model of digital search, users translate intent into keyword-based queries, evaluate ranked lists of links, and execute decisions outside the search interface. In an AI-native world, users express goals in natural language,… ▽ More Digital search is undergoing a fundamental transformation from a human-driven process of discovery to an agent-mediated system of delegated decision-making. In the traditional model of digital search, users translate intent into keyword-based queries, evaluate ranked lists of links, and execute decisions outside the search interface. In an AI-native world, users express goals in natural language, agents interpret these intentions, and outcomes are returned as recommendations or executed decisions. This shift moves search from a link-based user interface to an embedded system component, with implications for transparency, competition, and monetization. The resulting system design problem raises key questions about information quality and access, trust, incentive alignment, and market structure. Early evidence from experimental agent-mediated marketplaces and economic theory suggests that small design choices, such as how stakeholders access information, how options are surfaced, and how actions are executed, have first-order effects on efficiency, competition, and the welfare of consumers and firms. We propose that the future of search will be determined not by incremental improvements in ranking algorithms and natural-language interfaces, but by the design of open, transparent, and competitive agentic systems that govern how decisions are made and how markets operate, highlighting a set of grand challenges at the intersection of AI, economics, and system design. △ Less

Submitted 23 July, 2026; originally announced July 2026.

Comments: 4 pages, 0 figures

Teaming Up with AI: Coordination and Cooperation

Authors: Nicole Immorlica, Inbal Talgam-Cohen

Abstract: Successful diffusion of AI in the workforce hinges on the economic value that AI brings to human endeavors. Bringing AI into the workforce is more than deploying a powerful new technology -- it is launching a new form of collaboration. Each human worker is now endowed with a team of AI agents; work can be delegated to these agents, and the role of the human shifts towards managing and monitoring.… ▽ More Successful diffusion of AI in the workforce hinges on the economic value that AI brings to human endeavors. Bringing AI into the workforce is more than deploying a powerful new technology -- it is launching a new form of collaboration. Each human worker is now endowed with a team of AI agents; work can be delegated to these agents, and the role of the human shifts towards managing and monitoring. How can we maximize the economic value from collaboration with AI in the workforce? How can we make it a "true" collaboration that empowers human workers rather than replacing them? We take an approach that combines the fields of theoretical computer science and economics, highlighting the potential of algorithmic tools grounded in economic principles to improve the effectiveness of human-AI collective work. We consider two tiers of tools: (1) tools for better coordination, via algorithmic management of interdependencies; (2) tools for better cooperation, via contractual incentive alignment. We show how a principled approach based on algorithmic and economic research enhances both coordination and cooperation, charting a pathway for future research to inform AI markets. △ Less

Submitted 3 July, 2026; originally announced July 2026.

Chaining Tasks, Redefining Work: A Theory of AI Automation

Authors: Mert Demirer, John J. Horton, Nicole Immorlica, Brendan Lucier, Peyman Shahidi

Abstract: Production is a sequence of steps that can be executed (1) manually, (2) augmented with AI, or (3) fully automated within contiguous AI-executed steps called ''chains.'' Firms optimally bundle steps into tasks and then jobs, trading off specialization gains against coordination costs. We characterize the optimal assignment of humans and AI to steps and the firm's resulting job structure, showing t… ▽ More Production is a sequence of steps that can be executed (1) manually, (2) augmented with AI, or (3) fully automated within contiguous AI-executed steps called ''chains.'' Firms optimally bundle steps into tasks and then jobs, trading off specialization gains against coordination costs. We characterize the optimal assignment of humans and AI to steps and the firm's resulting job structure, showing that comparative advantage logic can fail with AI chaining. The model implies non-linear productivity gains from AI quality improvements and admits a CES representation at the macro level. Empirical evidence supports the model's key predictions that (1) AI-executed steps co-occur in chains, (2) dispersion of AI-exposed steps lowers AI execution at the job level, and (3) adjacency to AI-executed steps increases the likelihood that a step is AI-executed. △ Less

Submitted 14 June, 2026; originally announced June 2026.

Comments: Accepted to the 27th ACM Conference on Economics and Computation (EC '26)

From Augmentation to Reconstruction: Guiding the AI Disruption to the Good Place

Authors: David M. Rothschild, Jake M. Hofman, Markus Mobius, Brendan Lucier, Eleanor Dillon, Daniel G. Goldstein, Nicole Immorlica, Aleksandrs Slivkins

Abstract: Artificial intelligence feels omnipresent, yet the disruption many expect has not fully arrived. The main reason is not model capability, nor even the tools built to harness those models. Rather, most organizations are still using AI to accelerate workflows designed for a pre-AI world. We offer a three-stage lens: Augmentation, Automation, and Reconstruction, and argue that the most consequential… ▽ More Artificial intelligence feels omnipresent, yet the disruption many expect has not fully arrived. The main reason is not model capability, nor even the tools built to harness those models. Rather, most organizations are still using AI to accelerate workflows designed for a pre-AI world. We offer a three-stage lens: Augmentation, Automation, and Reconstruction, and argue that the most consequential disruption resides in the third stage where workflows and markets are rebuilt around delegation, machine-to-machine interaction, continuous monitoring, and auditable constraints. Achieving this system-level transformation takes time: it requires trust and accountability infrastructure, machine-legible and interoperable data and interfaces, the design and adoption of these new workflows, and economic incentives that favor reconstruction rather than local optimization: the complementary investments that produce the familiar "productivity J-curve" of general-purpose technologies. We illustrate this transition through examples in consumer markets, education, news, and coding. Finally, we emphasize a normative point: the agentic future is not predetermined. Leaders must both skate to where the puck is going and actively steer it toward a good place, ensuring innovation delivers welfare gains felt by businesses and consumers around the world. △ Less

Submitted 27 May, 2026; originally announced May 2026.

Comments: 5 Pages, 0 Figures

Subsidizing Sequential Search

Authors: Salvador Candelas, Nicole Immorlica, Brendan Lucier

Abstract: We study markets where firms compete for consumer attention by subsidizing costly product inspection. These subsidies do not change product quality, but they alter the order in which consumers search by lowering inspection costs. We establish a subsidy-sorting principle: in any equilibrium, higher-quality firms provide weakly larger subsidies, leading consumers to search in descending subsidy orde… ▽ More We study markets where firms compete for consumer attention by subsidizing costly product inspection. These subsidies do not change product quality, but they alter the order in which consumers search by lowering inspection costs. We establish a subsidy-sorting principle: in any equilibrium, higher-quality firms provide weakly larger subsidies, leading consumers to search in descending subsidy order. A unique equilibrium survives forward-induction reasoning in the spirit of the Intuitive Criterion: low-quality firms are never inspected, intermediate-quality firms separate with strictly increasing subsidies, and high-quality firms pool at the full subsidy. This equilibrium maximizes information revelation among all possible outcomes and ensures efficient inspection. We then extend the analysis to AI-mediated platforms that can create and price inspection tokens. The platform's optimal linear pricing leads to excessive inspection relative to the social optimum. While this distortion does not reduce consumer welfare, it reallocates surplus from sellers to the platform and consumers. △ Less

Submitted 27 May, 2026; originally announced May 2026.

Agentic Markets: Equilibrium Effects of Improving Consumer Search

Authors: Brendan Lucier, Nicole Immorlica, Markus Mobius, Aleksandrs Slivkins, Daniel G. Goldstein, Jake M. Hofman, Sonia Jaffe, David M. Rothschild

Abstract: Motivated by agentic markets -- two-sided markets in which consumers and businesses are assisted by AI tools that facilitate consumers' search -- we study the impact of improved search technology on learning and welfare in markets. We put forth a model where consumers engage in costly search to acquire signals of product fit prior to purchase. The market tracks indications of fit for searched prod… ▽ More Motivated by agentic markets -- two-sided markets in which consumers and businesses are assisted by AI tools that facilitate consumers' search -- we study the impact of improved search technology on learning and welfare in markets. We put forth a model where consumers engage in costly search to acquire signals of product fit prior to purchase. The market tracks indications of fit for searched products and indications of quality for chosen products, thereby guiding searches. We characterize the long-run steady-state of the resulting dynamics as well as the impact of improving search technology. We find cheaper search improves learning and consumer surplus, whereas more informative search can degrade both unless the market learns as much as consumers about the products by, for example, ``reading the transcripts'' of agentic conversations. Finally, we consider the impact of search improvements on how businesses set prices. At equilibrium prices in symmetric markets, consumer surplus is improved by cheaper search but may be decreased by more informative search, due to weakened inter-business competition. △ Less

Submitted 26 March, 2026; originally announced March 2026.

Optimal Selection Using Algorithmic Rankings with Side Information

Authors: Kate Donahue, Nicole Immorlica, Brendan Lucier

Abstract: Motivated by online platforms such as job markets, we study an agent choosing from a list of candidates, each with a hidden quality that determines match value. The agent observes only a noisy ranking of the candidates plus a binary signal that indicates whether each candidate is "free" or "busy". Being busy is positively correlated with higher quality, but can also reduce value due to decreased a… ▽ More Motivated by online platforms such as job markets, we study an agent choosing from a list of candidates, each with a hidden quality that determines match value. The agent observes only a noisy ranking of the candidates plus a binary signal that indicates whether each candidate is "free" or "busy". Being busy is positively correlated with higher quality, but can also reduce value due to decreased availability. We study the agent's optimal selection problem in the presence of ranking noise and free-busy signals and ask how the accuracy of the ranking tool impacts outcomes. In a setting with one high-valued candidate and an arbitrary number of low-valued candidates, we show that increased accuracy of the ranking tool can result in suboptimal social outcomes. For example, increased accuracy may mean that agents may be more likely to make offers to busy candidates, and (counter-intuitively) may be more likely to select lower-ranked candidates. We further discuss conditions under which these results extend to more general settings. △ Less

Submitted 24 February, 2026; v1 submitted 6 November, 2025; originally announced November 2025.

Magentic Marketplace: An Open-Source Environment for Studying Agentic Markets

Authors: Gagan Bansal, Wenyue Hua, Zezhou Huang, Adam Fourney, Amanda Swearngin, Will Epperson, Tyler Payne, Jake M. Hofman, Brendan Lucier, Chinmay Singh, Markus Mobius, Akshay Nambi, Archana Yadav, Kevin Gao, David M. Rothschild, Aleksandrs Slivkins, Daniel G. Goldstein, Hussein Mozannar, Nicole Immorlica, Maya Murad, Matthew Vogel, Subbarao Kambhampati, Eric Horvitz, Saleema Amershi

Abstract: As LLM agents advance, they are increasingly mediating economic decisions, ranging from product discovery to transactions, on behalf of users. Such applications promise benefits but also raise many questions about agent accountability and value for users. Addressing these questions requires understanding how agents behave in realistic market conditions. However, previous research has largely evalu… ▽ More As LLM agents advance, they are increasingly mediating economic decisions, ranging from product discovery to transactions, on behalf of users. Such applications promise benefits but also raise many questions about agent accountability and value for users. Addressing these questions requires understanding how agents behave in realistic market conditions. However, previous research has largely evaluated agents in constrained settings, such as single-task marketplaces (e.g., negotiation) or structured two-agent interactions. Real-world markets are fundamentally different: they require agents to handle diverse economic activities and coordinate within large, dynamic ecosystems where multiple agents with opaque behaviors may engage in open-ended dialogues. To bridge this gap, we investigate two-sided agentic marketplaces where Assistant agents represent consumers and Service agents represent competing businesses. To study these interactions safely, we develop Magentic-Marketplace -- a simulated environment where Assistants and Services can operate. This environment enables us to study key market dynamics: the utility agents achieve, behavioral biases, vulnerability to manipulation, and how search mechanisms shape market outcomes. Our experiments show that frontier models can approach optimal welfare -- but only under ideal search conditions. Performance degrades sharply with scale, and all models exhibit severe first-proposal bias, creating 10-30x advantages for response speed over quality. These findings reveal how behaviors emerge across market conditions, informing the design of fair and efficient agentic marketplaces. △ Less

Submitted 27 October, 2025; originally announced October 2025.

Interactions across multiple games: cooperation, corruption, and organizational design

Authors: Jonathan Bendor, Lukas Bolte, Nicole Immorlica, Matthew O. Jackson

Abstract: Teamwork is vital in many settings, and it is socially beneficial for teams to cooperate in some situations (``good games'') and not in others (``bad games;'' e.g., those that allow for corruption). A team's cooperation in any given game depends on expectations of cooperation in future iterations of both good and bad games. We identify when sustaining cooperation on good games necessitates coopera… ▽ More Teamwork is vital in many settings, and it is socially beneficial for teams to cooperate in some situations (``good games'') and not in others (``bad games;'' e.g., those that allow for corruption). A team's cooperation in any given game depends on expectations of cooperation in future iterations of both good and bad games. We identify when sustaining cooperation on good games necessitates cooperation on bad games. We then characterize how a designer should optimally assign workers to teams and teams to tasks that involve varying arrival rates of good and bad games. Our results show how organizational design can be used to promote cooperation while minimizing corruption. △ Less

Submitted 15 February, 2026; v1 submitted 2 July, 2025; originally announced July 2025.

Eliciting Informed Preferences

Authors: Modibo K. Camara, Nicole Immorlica, Brendan Lucier

Abstract: In many settings -- like market research and social choice -- people may be presented with unfamiliar options. Classical mechanisms may perform poorly because they fail to incentivize people to learn about these options, or worse, encourage counterproductive information acquisition. We formalize this problem in a model of robust mechanism design where agents find it costly to learn about their val… ▽ More In many settings -- like market research and social choice -- people may be presented with unfamiliar options. Classical mechanisms may perform poorly because they fail to incentivize people to learn about these options, or worse, encourage counterproductive information acquisition. We formalize this problem in a model of robust mechanism design where agents find it costly to learn about their values for a product or policy. We identify sharp limits on the designer's ability to elicit, or learn about, these values. Where these limits do not bind, we propose two-stage mechanisms that are detail-free and robust: the second stage is a classical mechanism and the first stage asks participants to predict the results of the second stage. △ Less

Submitted 19 July, 2025; v1 submitted 26 May, 2025; originally announced May 2025.

Comments: Appeared at EC 2025

The Agentic Economy

Authors: David M. Rothschild, Markus Mobius, Jake M. Hofman, Eleanor W. Dillon, Daniel G. Goldstein, Nicole Immorlica, Sonia Jaffe, Brendan Lucier, Aleksandrs Slivkins, Matthew Vogel

Abstract: Generative AI has transformed human-computer interaction by enabling natural language interfaces and the emergence of autonomous agents capable of acting on users' behalf. While early applications have improved individual productivity, these gains have largely been confined to predefined tasks within existing workflows. We argue that the more profound economic impact lies in reducing communication… ▽ More Generative AI has transformed human-computer interaction by enabling natural language interfaces and the emergence of autonomous agents capable of acting on users' behalf. While early applications have improved individual productivity, these gains have largely been confined to predefined tasks within existing workflows. We argue that the more profound economic impact lies in reducing communication frictions between consumers and businesses. This shift could reorganize markets, redistribute power, and catalyze the creation of new products and services. We explore the implications of an agentic economy, where assistant agents act on behalf of consumers and service agents represent businesses, interacting programmatically to facilitate transactions. A key distinction we draw is between unscripted interactions -- enabled by technical advances in natural language and protocol design -- and unrestricted interactions, which depend on market structures and governance. We examine the current limitations of siloed and end-to-end agents, and explore future scenarios shaped by technical standards and market dynamics. These include the potential tension between agentic walled gardens and an open web of agents, implications for advertising and discovery, the evolution of micro-transactions, and the unbundling and rebundling of digital goods. Ultimately, we argue that the architecture of agentic communication will determine the extent to which generative AI democratizes access to economic opportunity. △ Less

Submitted 29 May, 2025; v1 submitted 21 May, 2025; originally announced May 2025.

Shifting Work Patterns with Generative AI

Authors: Eleanor Wiske Dillon, Sonia Jaffe, Nicole Immorlica, Christopher T. Stanton

Abstract: We present evidence from a field experiment across 66 firms and 7,137 knowledge workers. Workers were randomly selected to access a generative AI tool integrated into applications they already used at work for email, meetings, and writing. In the second half of the 6-month experiment, the 80% of treated workers who used this tool spent two fewer hours on email each week and reduced their time work… ▽ More We present evidence from a field experiment across 66 firms and 7,137 knowledge workers. Workers were randomly selected to access a generative AI tool integrated into applications they already used at work for email, meetings, and writing. In the second half of the 6-month experiment, the 80% of treated workers who used this tool spent two fewer hours on email each week and reduced their time working outside of regular hours. Apart from these individual time savings, we do not detect shifts in the quantity or composition of workers' tasks resulting from individual-level AI provision. △ Less

Submitted 13 November, 2025; v1 submitted 15 April, 2025; originally announced April 2025.

Inducing Efficient and Equitable Professional Networks through Link Recommendations

Authors: Cynthia Dwork, Chris Hays, Lunjia Hu, Nicole Immorlica, Juan Perdomo

Abstract: Professional networks are a key determinant of individuals' labor market outcomes. They may also play a role in either exacerbating or ameliorating inequality of opportunity across demographic groups. In a theoretical model of professional network formation, we show that inequality can increase even without exogenous in-group preferences, confirming and complementing existing theoretical literatur… ▽ More Professional networks are a key determinant of individuals' labor market outcomes. They may also play a role in either exacerbating or ameliorating inequality of opportunity across demographic groups. In a theoretical model of professional network formation, we show that inequality can increase even without exogenous in-group preferences, confirming and complementing existing theoretical literature. Increased inequality emerges from the differential leverage privileged and unprivileged individuals have in forming connections due to their asymmetric ex ante prospects. This is a formalization of a source of inequality in the labor market which has not been previously explored. We next show how inequality-aware platforms may reduce inequality by subsidizing connections, through link recommendations that reduce costs, between privileged and unprivileged individuals. Indeed, mixed-privilege connections turn out to be welfare improving, over all possible equilibria, compared to not recommending links or recommending some smaller fraction of cross-group links. Taken together, these two findings reveal a stark reality: professional networking platforms that fail to foster integration in the link formation process risk reducing the platform's utility to its users and exacerbating existing labor market inequality. △ Less

Submitted 6 March, 2025; originally announced March 2025.

Comments: 34 pages, 4 figures

Flattening Supply Chains: When do Technology Improvements lead to Disintermediation?

Authors: S. Nageeb Ali, Nicole Immorlica, Meena Jagadeesan, Brendan Lucier

Abstract: In the digital economy, technological innovations make it cheaper to produce high-quality content. For example, generative AI tools reduce costs for creators who develop content to be distributed online, but can also reduce production costs for the users who consume that content. These innovations can thus lead to disintermediation, since consumers may choose to use these technologies directly, by… ▽ More In the digital economy, technological innovations make it cheaper to produce high-quality content. For example, generative AI tools reduce costs for creators who develop content to be distributed online, but can also reduce production costs for the users who consume that content. These innovations can thus lead to disintermediation, since consumers may choose to use these technologies directly, bypassing intermediaries. To investigate when technological improvements lead to disintermediation, we study a game with an intermediary, suppliers of a production technology, and consumers. First, we show disintermediation occurs whenever production costs are too high or too low. We then investigate the consequences of disintermediation for welfare and content quality at equilibrium. While the intermediary is welfare-improving, the intermediary extracts all gains to social welfare and its presence can raise or lower content quality. We further analyze how disintermediation is affected by the level of competition between suppliers and the intermediary's fee structure. More broadly, our results take a step towards assessing how production technology innovations affect the survival of intermediaries and impact the digital economy. △ Less

Submitted 28 February, 2025; originally announced February 2025.

From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs

Authors: Cynthia Dwork, Chris Hays, Nicole Immorlica, Juan C. Perdomo, Pranay Tankala

Abstract: Professional networks provide invaluable entree to opportunity through referrals and introductions. A rich literature shows they also serve to entrench and even exacerbate a status quo of privilege and disadvantage. Hiring platforms, equipped with the ability to nudge link formation, provide a tantalizing opening for beneficial structural change. We anticipate that key to this prospect will be the… ▽ More Professional networks provide invaluable entree to opportunity through referrals and introductions. A rich literature shows they also serve to entrench and even exacerbate a status quo of privilege and disadvantage. Hiring platforms, equipped with the ability to nudge link formation, provide a tantalizing opening for beneficial structural change. We anticipate that key to this prospect will be the ability to estimate the likelihood of edge formation in an evolving graph. Outcome-indistinguishable prediction algorithms ensure that the modeled world is indistinguishable from the real world by a family of statistical tests. Omnipredictors ensure that predictions can be post-processed to yield loss minimization competitive with respect to a benchmark class of predictors for many losses simultaneously, with appropriate post-processing. We begin by observing that, by combining a slightly modified form of the online K29 star algorithm of Vovk (2007) with basic facts from the theory of reproducing kernel Hilbert spaces, one can derive simple and efficient online algorithms satisfying outcome indistinguishability and omniprediction, with guarantees that improve upon, or are complementary to, those currently known. This is of independent interest. We apply these techniques to evolving graphs, obtaining online outcome-indistinguishable omnipredictors for rich -- possibly infinite -- sets of distinguishers that capture properties of pairs of nodes, and their neighborhoods. This yields, inter alia, multicalibrated predictions of edge formation with respect to pairs of demographic groups, and the ability to simultaneously optimize loss as measured by a variety of social welfare functions. △ Less

Submitted 26 November, 2024; originally announced November 2024.

Generative AI as Economic Agents

Authors: Nicole Immorlica, Brendan Lucier, Aleksandrs Slivkins

Abstract: Traditionally, AI has been modeled within economics as a technology that impacts payoffs by reducing costs or refining information for human agents. Our position is that, in light of recent advances in generative AI, it is increasingly useful to model AI itself as an economic agent. In our framework, each user is augmented with an AI agent and can consult the AI prior to taking actions in a game.… ▽ More Traditionally, AI has been modeled within economics as a technology that impacts payoffs by reducing costs or refining information for human agents. Our position is that, in light of recent advances in generative AI, it is increasingly useful to model AI itself as an economic agent. In our framework, each user is augmented with an AI agent and can consult the AI prior to taking actions in a game. The AI agent and the user have potentially different information and preferences over the communication, which can result in equilibria that are qualitatively different than in settings without AI. △ Less

Submitted 1 June, 2024; originally announced June 2024.

Comments: To appear in SIGEcom Exchanges

Maximal Procurement under a Budget

Authors: Nicole Immorlica, Nicholas Wu, Brendan Lucier

Abstract: We study the problem of a principal who wants to influence an agent's observable action, subject to an ex-post budget. The agent has a private type determining their cost function. This paper endogenizes the value of the resource driving incentives, which holds no inherent value but is restricted by finite availability. We characterize the optimal mechanism, showing the emergence of a pooling regi… ▽ More We study the problem of a principal who wants to influence an agent's observable action, subject to an ex-post budget. The agent has a private type determining their cost function. This paper endogenizes the value of the resource driving incentives, which holds no inherent value but is restricted by finite availability. We characterize the optimal mechanism, showing the emergence of a pooling region where the budget constraint binds for low-cost types. We then introduce a linear value for the transferable resource; as the principal's value increases, the mechanism demands more from agents with binding budget constraint but less from others. △ Less

Submitted 23 April, 2024; originally announced April 2024.

Online Algorithms with Limited Data Retention

Authors: Nicole Immorlica, Brendan Lucier, Markus Mobius, James Siderius

Abstract: We introduce a model of online algorithms subject to strict constraints on data retention. An online learning algorithm encounters a stream of data points, one per round, generated by some stationary process. Crucially, each data point can request that it be removed from memory $m$ rounds after it arrives. To model the impact of removal, we do not allow the algorithm to store any information or ca… ▽ More We introduce a model of online algorithms subject to strict constraints on data retention. An online learning algorithm encounters a stream of data points, one per round, generated by some stationary process. Crucially, each data point can request that it be removed from memory $m$ rounds after it arrives. To model the impact of removal, we do not allow the algorithm to store any information or calculations between rounds other than a subset of the data points (subject to the retention constraints). At the conclusion of the stream, the algorithm answers a statistical query about the full dataset. We ask: what level of performance can be guaranteed as a function of $m$? We illustrate this framework for multidimensional mean estimation and linear regression problems. We show it is possible to obtain an exponential improvement over a baseline algorithm that retains all data as long as possible. Specifically, we show that $m = \textsc{Poly}(d, \log(1/ε))$ retention suffices to achieve mean squared error $ε$ after observing $O(1/ε)$ $d$-dimensional data points. This matches the error bound of the optimal, yet infeasible, algorithm that retains all data forever. We also show a nearly matching lower bound on the retention required to guarantee error $ε$. One implication of our results is that data retention laws are insufficient to guarantee the right to be forgotten even in a non-adversarial world in which firms merely strive to (approximately) optimize the performance of their algorithms. Our approach makes use of recent developments in the multidimensional random subset sum problem to simulate the progression of stochastic gradient descent under a model of adversarial noise, which may be of independent interest. △ Less

Submitted 16 April, 2024; originally announced April 2024.

Impact of Decentralized Learning on Player Utilities in Stackelberg Games

Authors: Kate Donahue, Nicole Immorlica, Meena Jagadeesan, Brendan Lucier, Aleksandrs Slivkins

Abstract: When deployed in the world, a learning agent such as a recommender system or a chatbot often repeatedly interacts with another learning agent (such as a user) over time. In many such two-agent systems, each agent learns separately and the rewards of the two agents are not perfectly aligned. To better understand such cases, we examine the learning dynamics of the two-agent system and the implicatio… ▽ More When deployed in the world, a learning agent such as a recommender system or a chatbot often repeatedly interacts with another learning agent (such as a user) over time. In many such two-agent systems, each agent learns separately and the rewards of the two agents are not perfectly aligned. To better understand such cases, we examine the learning dynamics of the two-agent system and the implications for each agent's objective. We model these systems as Stackelberg games with decentralized learning and show that standard regret benchmarks (such as Stackelberg equilibrium payoffs) result in worst-case linear regret for at least one player. To better capture these systems, we construct a relaxed regret benchmark that is tolerant to small learning errors by agents. We show that standard learning algorithms fail to provide sublinear regret, and we develop algorithms to achieve near-optimal $O(T^{2/3})$ regret for both players with respect to these benchmarks. We further design relaxed environments under which faster learning ($O(\sqrt{T})$) is possible. Altogether, our results take a step towards assessing how two-agent interactions in sequential and decentralized learning environments affect the utility of both agents. △ Less

Submitted 21 June, 2024; v1 submitted 29 February, 2024; originally announced March 2024.

Comments: To appear at ICML 2024; this is the full version

Clickbait vs. Quality: How Engagement-Based Optimization Shapes the Content Landscape in Online Platforms

Authors: Nicole Immorlica, Meena Jagadeesan, Brendan Lucier

Abstract: Online content platforms commonly use engagement-based optimization when making recommendations. This encourages content creators to invest in quality, but also rewards gaming tricks such as clickbait. To understand the total impact on the content landscape, we study a game between content creators competing on the basis of engagement metrics and analyze the equilibrium decisions about investment… ▽ More Online content platforms commonly use engagement-based optimization when making recommendations. This encourages content creators to invest in quality, but also rewards gaming tricks such as clickbait. To understand the total impact on the content landscape, we study a game between content creators competing on the basis of engagement metrics and analyze the equilibrium decisions about investment in quality and gaming. First, we show the content created at equilibrium exhibits a positive correlation between quality and gaming, and we empirically validate this finding on a Twitter dataset. Using the equilibrium structure of the content landscape, we then examine the downstream performance of engagement-based optimization along several axes. Perhaps counterintuitively, the average quality of content consumed by users can decrease at equilibrium as gaming tricks become more costly for content creators to employ. Moreover, engagement-based optimization can perform worse in terms of user utility than a baseline with random recommendations, and engagement-based optimization is also suboptimal in terms of realized engagement relative to quality-based optimization. Altogether, our results highlight the need to consider content creator incentives when evaluating a platform's choice of optimization metric. △ Less

Submitted 18 January, 2024; originally announced January 2024.

Algorithmic Persuasion Through Simulation

Authors: Keegan Harris, Nicole Immorlica, Brendan Lucier, Aleksandrs Slivkins

Abstract: We study a Bayesian persuasion game where a sender wants to persuade a receiver to take a binary action, such as purchasing a product. The sender is informed about the (real-valued) state of the world, such as the quality of the product, but only has limited information about the receiver's beliefs and utilities. Motivated by customer surveys, user studies, and recent advances in AI, we allow the… ▽ More We study a Bayesian persuasion game where a sender wants to persuade a receiver to take a binary action, such as purchasing a product. The sender is informed about the (real-valued) state of the world, such as the quality of the product, but only has limited information about the receiver's beliefs and utilities. Motivated by customer surveys, user studies, and recent advances in AI, we allow the sender to learn more about the receiver by querying an oracle that simulates the receiver's behavior. After a fixed number of queries, the sender commits to a messaging policy and the receiver takes the action that maximizes her expected utility given the message she receives. We characterize the sender's optimal messaging policy given any distribution over receiver types. We then design a polynomial-time querying algorithm that optimizes the sender's expected utility in this game. We also consider approximate oracles, more general query structures, and costly queries. △ Less

Submitted 12 February, 2025; v1 submitted 29 November, 2023; originally announced November 2023.

Certification Design for a Competitive Market

Authors: Andreas A. Haupt, Nicole Immorlica, Brendan Lucier

Abstract: Motivated by applications such as voluntary carbon markets and educational testing, we consider a market for goods with varying but hidden levels of quality in the presence of a third-party certifier. The certifier can provide informative signals about the quality of products, and can charge for this service. Sellers choose both the quality of the product they produce and a certification. Prices a… ▽ More Motivated by applications such as voluntary carbon markets and educational testing, we consider a market for goods with varying but hidden levels of quality in the presence of a third-party certifier. The certifier can provide informative signals about the quality of products, and can charge for this service. Sellers choose both the quality of the product they produce and a certification. Prices are then determined in a competitive market. Under a single-crossing condition, we show that the levels of certification chosen by producers are uniquely determined at equilibrium. We then show how to reduce a revenue-maximizing certifier's problem to a monopolistic pricing problem with non-linear valuations, and design an FPTAS for computing the optimal slate of certificates and their prices. In general, both the welfare-optimal and revenue-optimal slate of certificates can be arbitrarily large. △ Less

Submitted 31 January, 2023; originally announced January 2023.

Comments: 22 pages, 1 figure

Efficiency in Collective Decision-Making via Quadratic Transfers

Authors: Jon X. Eguia, Nicole Immorlica, Steven P. Lalley, Katrina Ligett, Glen Weyl, Dimitrios Xefteris

Abstract: Consider the following collective choice problem: a group of budget constrained agents must choose one of several alternatives. Is there a budget balanced mechanism that: i) does not depend on the specific characteristics of the group, ii) does not require unaffordable transfers, and iii) implements utilitarianism if the agents' preferences are quasilinear and their private information? We study t… ▽ More Consider the following collective choice problem: a group of budget constrained agents must choose one of several alternatives. Is there a budget balanced mechanism that: i) does not depend on the specific characteristics of the group, ii) does not require unaffordable transfers, and iii) implements utilitarianism if the agents' preferences are quasilinear and their private information? We study the following procedure: every agent can express any intensity of support or opposition to each alternative, by transferring to the rest of the agents wealth equal to the square of the intensity expressed; and the outcome is determined by the sums of the expressed intensities. We prove that as the group grows large, in every equilibrium of this quadratic-transfers mechanism, each agent's transfer converges to zero, and the probability that the efficient outcome is chosen converges to one. △ Less

Submitted 15 January, 2023; originally announced January 2023.

Content Filtering with Inattentive Information Consumers

Authors: Ian Ball, James Bono, Justin Grana, Nicole Immorlica, Brendan Lucier, Aleksandrs Slivkins

Abstract: We develop a model of content filtering as a game between the filter and the content consumer, where the latter incurs information costs for examining the content. Motivating examples include censoring misinformation, spam/phish filtering, and recommender systems. When the attacker is exogenous, we show that improving the filter's quality is weakly Pareto improving, but has no impact on equilibriu… ▽ More We develop a model of content filtering as a game between the filter and the content consumer, where the latter incurs information costs for examining the content. Motivating examples include censoring misinformation, spam/phish filtering, and recommender systems. When the attacker is exogenous, we show that improving the filter's quality is weakly Pareto improving, but has no impact on equilibrium payoffs until the filter becomes sufficiently accurate. Further, if the filter does not internalize the information costs, its lack of commitment power may render it useless and lead to inefficient outcomes. When the attacker is also strategic, improvements to filter quality may sometimes decrease equilibrium payoffs. △ Less

Submitted 20 December, 2023; v1 submitted 27 May, 2022; originally announced May 2022.

On the Effect of Triadic Closure on Network Segregation

Authors: Rediet Abebe, Nicole Immorlica, Jon Kleinberg, Brendan Lucier, Ali Shirali

Abstract: The tendency for individuals to form social ties with others who are similar to themselves, known as homophily, is one of the most robust sociological principles. Since this phenomenon can lead to patterns of interactions that segregate people along different demographic dimensions, it can also lead to inequalities in access to information, resources, and opportunities. As we consider potential in… ▽ More The tendency for individuals to form social ties with others who are similar to themselves, known as homophily, is one of the most robust sociological principles. Since this phenomenon can lead to patterns of interactions that segregate people along different demographic dimensions, it can also lead to inequalities in access to information, resources, and opportunities. As we consider potential interventions that might alleviate the effects of segregation, we face the challenge that homophily constitutes a pervasive and organic force that is difficult to push back against. Designing effective interventions can therefore benefit from identifying counterbalancing social processes that might be harnessed to work in opposition to segregation. In this work, we show that triadic closure -- another common phenomenon that posits that individuals with a mutual connection are more likely to be connected to one another -- can be one such process. In doing so, we challenge a long-held belief that triadic closure and homophily work in tandem. By analyzing several fundamental network models using popular integration measures, we demonstrate the desegregating potential of triadic closure. We further empirically investigate this effect on real-world dynamic networks, surfacing observations that mirror our theoretical findings. We leverage these insights to discuss simple interventions that can help reduce segregation in settings that exhibit an interplay between triadic closure and homophily. We conclude with a discussion on qualitative implications for the design of interventions in settings where individuals arrive in an online fashion, and the designer can influence the initial set of connections. △ Less

Submitted 26 May, 2022; originally announced May 2022.

Comments: To Appear in Proceedings of the 23rd ACM Conference on Economics and Computation (EC'22)

Communicating with Anecdotes

Authors: Nika Haghtalab, Nicole Immorlica, Brendan Lucier, Markus Mobius, Divyarthi Mohan

Abstract: We study a communication game between a sender and a receiver. The sender chooses one of her signals about the state of the world (i.e., anecdotes) and communicates to the receiver who takes an action affecting both players. The sender and the receiver both care about the state of the world but are also influenced by personal preferences, so their ideal actions can differ. We characterize perfect… ▽ More We study a communication game between a sender and a receiver. The sender chooses one of her signals about the state of the world (i.e., anecdotes) and communicates to the receiver who takes an action affecting both players. The sender and the receiver both care about the state of the world but are also influenced by personal preferences, so their ideal actions can differ. We characterize perfect Bayesian equilibria. The sender faces a temptation to persuade: she wants to select a biased anecdote to influence the receiver's action. Anecdotes are still informative to the receiver (who will debias at equilibrium) but the attempt to persuade comes at a cost to precision. This gives rise to informational homophily where the receiver prefers to listen to like-minded senders because they provide higher-precision signals. Communication becomes polarized when the sender is an expert with access to many signals, with the sender choosing extreme outlier anecdotes at equilibrium (unless preferences are perfectly aligned). This polarization dissipates all gains from communication with an increasingly well-informed sender when the anecdote distribution is heavy-tailed. Experts can therefore face a curse of informedness: receivers will prefer to listen to less-informed senders who cannot pick biased signals as easily. △ Less

Submitted 17 July, 2024; v1 submitted 26 May, 2022; originally announced May 2022.

Comments: Extended Abstract appeared at ITCS 2024. A preliminary version of this paper appeared under the title "Persuading with Anecdotes" as an NBER working paper

Social Learning under Platform Influence: Consensus and Persistent Disagreement

Authors: Ozan Candogan, Nicole Immorlica, Bar Light, Jerry Anunrojwong

Abstract: Individuals increasingly rely on social networking platforms to form opinions. However, these platforms typically aim to maximize engagement, which may not align with social good. In this paper, we introduce an opinion dynamics model where agents are connected in a social network, and update their opinions based on their neighbors' opinions and on the content shown to them by the platform. We focu… ▽ More Individuals increasingly rely on social networking platforms to form opinions. However, these platforms typically aim to maximize engagement, which may not align with social good. In this paper, we introduce an opinion dynamics model where agents are connected in a social network, and update their opinions based on their neighbors' opinions and on the content shown to them by the platform. We focus on a stochastic block model with two blocks, where the initial opinions of the individuals in different blocks are different. We prove that for large and dense enough networks the trajectory of opinion dynamics in such networks can be approximated well by a simple two-agent system. The latter admits tractable analytical analysis, which we leverage to provide interesting insights into the platform's impact on the social learning outcome in our original two-block model. Specifically, by using our approximation result, we show that agents' opinions approximately converge to some limiting opinion, which is either: consensus, where all agents agree, or persistent disagreement, where agents' opinions differ. We find that when the platform is weak and there is a high number of connections between agents with different initial opinions, a consensus equilibrium is likely. In this case, even if a persistent disagreement equilibrium arises, the polarization in this equilibrium, i.e., the degree of disagreement, is low. When the platform is strong, a persistent disagreement equilibrium is likely and the equilibrium polarization is high. A moderate platform typically leads to a persistent disagreement equilibrium with moderate polarization. We analyze the effect of initial polarization on consensus and explore various extensions including a three block stochastic model and a correlation between initial opinions and agents' connection probabilities. △ Less

Submitted 5 June, 2025; v1 submitted 24 February, 2022; originally announced February 2022.

Making Auctions Robust to Aftermarkets

Authors: Moshe Babaioff, Nicole Immorlica, Yingkai Li, Brendan Lucier

Abstract: A prevalent assumption in auction theory is that the auctioneer has full control over the market and that the allocation she dictates is final. In practice, however, agents might be able to resell acquired items in an aftermarket. A prominent example is the market for carbon emission allowances. These allowances are commonly allocated by the government using uniform-price auctions, and firms can t… ▽ More A prevalent assumption in auction theory is that the auctioneer has full control over the market and that the allocation she dictates is final. In practice, however, agents might be able to resell acquired items in an aftermarket. A prominent example is the market for carbon emission allowances. These allowances are commonly allocated by the government using uniform-price auctions, and firms can typically trade these allowances among themselves in an aftermarket that may not be fully under the auctioneer's control. While the uniform-price auction is approximately efficient in isolation, we show that speculation and resale in aftermarkets might result in a significant welfare loss. Motivated by this issue, we consider three approaches, each ensuring high equilibrium welfare in the combined market. The first approach is to adopt smooth auctions such as discriminatory auctions. This approach is robust to correlated valuations and to participants acquiring information about others' types. However, discriminatory auctions have several downsides, notably that of charging bidders different prices for identical items, resulting in fairness concerns that make the format unpopular. Two other approaches we suggest are either using posted-pricing mechanisms, or using uniform-price auctions with anonymous reserves. We show that when using balanced prices, both these approaches ensure high equilibrium welfare in the combined market. The latter also inherits many of the benefits from uniform-price auctions such as price discovery, and can be introduced with a minor modification to auctions currently in use to sell carbon emission allowances. △ Less

Submitted 15 November, 2022; v1 submitted 13 July, 2021; originally announced July 2021.

Revenue Maximization for Buyers with Costly Participation

Authors: Yannai A. Gonczarowski, Nicole Immorlica, Yingkai Li, Brendan Lucier

Abstract: We study mechanisms for selling a single item when buyers have private costs for participating in the mechanism. An agent's participation cost can also be interpreted as an outside option value that she must forego to participate. This substantially changes the revenue maximization problem, which becomes non-convex in the presence of participation costs. For multiple buyers, we show how to constru… ▽ More We study mechanisms for selling a single item when buyers have private costs for participating in the mechanism. An agent's participation cost can also be interpreted as an outside option value that she must forego to participate. This substantially changes the revenue maximization problem, which becomes non-convex in the presence of participation costs. For multiple buyers, we show how to construct a $(2+ε)$-approximately revenue-optimal mechanism in polynomial time. Our approach makes use of a many-buyers-to-single-buyer reduction, and in the single-buyer case our mechanism improves to an FPTAS. We also bound the menu size and the sample complexity for the optimal single-buyer mechanism. Moreover, we show that posting a single price in the single-buyer case is in fact optimal under the assumption that either (1) the participation cost is independent of the value, and the value distribution has decreasing marginal revenue or monotone hazard rate; or (2) the participation cost is a concave function of the value. When there are multiple buyers, we show that sequential posted pricing guarantees a large fraction of the optimal revenue under similar conditions. △ Less

Submitted 5 November, 2023; v1 submitted 5 March, 2021; originally announced March 2021.

Comments: accepted at SODA 2024

Designing Approximately Optimal Search on Matching Platforms

Authors: Nicole Immorlica, Brendan Lucier, Vahideh Manshadi, Alexander Wei

Abstract: We study the design of a decentralized two-sided matching market in which agents' search is guided by the platform. There are finitely many agent types, each with (potentially random) preferences drawn from known type-specific distributions. Equipped with knowledge of these distributions, the platform guides the search process by determining the meeting rate between each pair of types from the two… ▽ More We study the design of a decentralized two-sided matching market in which agents' search is guided by the platform. There are finitely many agent types, each with (potentially random) preferences drawn from known type-specific distributions. Equipped with knowledge of these distributions, the platform guides the search process by determining the meeting rate between each pair of types from the two sides. Focusing on symmetric pairwise preferences in a continuum model, we first characterize the unique stationary equilibrium that arises given a feasible set of meeting rates. We then introduce the platform's optimal directed search problem, which involves optimizing meeting rates to maximize equilibrium social welfare. We first show that incentive issues arising from congestion and cannibalization make the design problem fairly intricate. Nonetheless, we develop an efficiently computable search design whose corresponding equilibrium achieves at least 1/4 the social welfare of the optimal design. In fact, our construction always recovers at least 1/4 the first-best social welfare, where agents' incentives are disregarded. Our directed search design is simple and easy-to-implement, as its corresponding bipartite graph consists of disjoint stars. Furthermore, our design implies the platform can substantially limit choice and yet induce an equilibrium with an approximately optimal welfare. Finally, we show that approximation is likely the best we can hope for by establishing that the problem of designing optimal directed search is NP-hard to even approximate beyond a certain constant factor. △ Less

Submitted 18 August, 2021; v1 submitted 17 February, 2021; originally announced February 2021.

Buying Data Over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions

Authors: Nicole Immorlica, Ian Kash, Brendan Lucier

Abstract: We consider a model where an agent has a repeated decision to make and wishes to maximize their total payoff. Payoffs are influenced by an action taken by the agent, but also an unknown state of the world that evolves over time. Before choosing an action each round, the agent can purchase noisy samples about the state of the world. The agent has a budget to spend on these samples, and has flexibil… ▽ More We consider a model where an agent has a repeated decision to make and wishes to maximize their total payoff. Payoffs are influenced by an action taken by the agent, but also an unknown state of the world that evolves over time. Before choosing an action each round, the agent can purchase noisy samples about the state of the world. The agent has a budget to spend on these samples, and has flexibility in deciding how to spread that budget across rounds. We investigate the problem of choosing a sampling algorithm that optimizes total expected payoff. For example: is it better to buy samples steadily over time, or to buy samples in batches? We solve for the optimal policy, and show that it is a natural instantiation of the latter. Under a more general model that includes per-round fixed costs, we prove that a variation on this batching policy is a 2-approximation. △ Less

Submitted 18 January, 2021; originally announced January 2021.

The Role of Referrals in Immobility, Inequality, and Inefficiency in Labor Markets

Authors: Lukas Bolte, Nicole Immorlica, Matthew O. Jackson

Abstract: We study the consequences of job markets' heavy reliance on referrals. Referrals lead to more opportunities for workers to be hired, which lead to better matches and increased productivity, but also disadvantage job-seekers with few or no connections to employed workers, increasing inequality. Coupled with homophily, referrals also lead to immobility. We identify conditions under which distributin… ▽ More We study the consequences of job markets' heavy reliance on referrals. Referrals lead to more opportunities for workers to be hired, which lead to better matches and increased productivity, but also disadvantage job-seekers with few or no connections to employed workers, increasing inequality. Coupled with homophily, referrals also lead to immobility. We identify conditions under which distributing referrals more evenly reduces inequality and improves future productivity and mobility. We use the model to examine the short and long-run welfare impacts of policies such as affirmative action and algorithmic fairness. △ Less

Submitted 9 April, 2026; v1 submitted 22 December, 2020; originally announced December 2020.

Non-quasi-linear Agents in Quasi-linear Mechanisms

Authors: Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, Brendan Lucier

Abstract: Mechanisms with money are commonly designed under the assumption that agents are quasi-linear, meaning they have linear disutility for spending money. We study the implications when agents with non-linear (specifically, convex) disutility for payments participate in mechanisms designed for quasi-linear agents. We first show that any mechanism that is truthful for quasi-linear buyers has a simple b… ▽ More Mechanisms with money are commonly designed under the assumption that agents are quasi-linear, meaning they have linear disutility for spending money. We study the implications when agents with non-linear (specifically, convex) disutility for payments participate in mechanisms designed for quasi-linear agents. We first show that any mechanism that is truthful for quasi-linear buyers has a simple best response function for buyers with non-linear disutility from payments, in which each bidder simply scales down her value for each potential outcome by a fixed factor, equal to her target return on investment (ROI). We call such a strategy ROI-optimal. We prove the existence of a Nash equilibrium in which agents use ROI-optimal strategies for a general class of allocation problems. Motivated by online marketplaces, we then focus on simultaneous second-price auctions for additive bidders and show that all ROI-optimal equilibria in this setting achieve constant-factor approximations to suitable welfare and revenue benchmarks. △ Less

Submitted 4 December, 2020; originally announced December 2020.

Dynamic Weighted Matching with Heterogeneous Arrival and Departure Rates

Authors: Natalie Collina, Nicole Immorlica, Kevin Leyton-Brown, Brendan Lucier, Neil Newman

Abstract: We study a dynamic non-bipartite matching problem. There is a fixed set of agent types, and agents of a given type arrive and depart according to type-specific Poisson processes. Agent departures are not announced in advance. The value of a match is determined by the types of the matched agents. We present an online algorithm that is (1/8)-competitive with respect to the value of the optimal-in-hi… ▽ More We study a dynamic non-bipartite matching problem. There is a fixed set of agent types, and agents of a given type arrive and depart according to type-specific Poisson processes. Agent departures are not announced in advance. The value of a match is determined by the types of the matched agents. We present an online algorithm that is (1/8)-competitive with respect to the value of the optimal-in-hindsight policy, for arbitrary weighted graphs. Our algorithm treats agents heterogeneously, interpolating between immediate and delayed matching in order to thicken the market while still matching valuable agents opportunistically. △ Less

Submitted 10 January, 2021; v1 submitted 1 December, 2020; originally announced December 2020.

Maximizing Welfare with Incentive-Aware Evaluation Mechanisms

Authors: Nika Haghtalab, Nicole Immorlica, Brendan Lucier, Jack Z. Wang

Abstract: Motivated by applications such as college admission and insurance rate determination, we propose an evaluation problem where the inputs are controlled by strategic individuals who can modify their features at a cost. A learner can only partially observe the features, and aims to classify individuals with respect to a quality score. The goal is to design an evaluation mechanism that maximizes the o… ▽ More Motivated by applications such as college admission and insurance rate determination, we propose an evaluation problem where the inputs are controlled by strategic individuals who can modify their features at a cost. A learner can only partially observe the features, and aims to classify individuals with respect to a quality score. The goal is to design an evaluation mechanism that maximizes the overall quality score, i.e., welfare, in the population, taking any strategic updating into account. We further study the algorithmic aspect of finding the welfare maximizing evaluation mechanism under two specific settings in our model. When scores are linear and mechanisms use linear scoring rules on the observable features, we show that the optimal evaluation mechanism is an appropriate projection of the quality score. When mechanisms must use linear thresholds, we design a polynomial time algorithm with a (1/4)-approximation guarantee when the underlying feature distribution is sufficiently smooth and admits an oracle for finding dense regions. We extend our results to settings where the prior distribution is unknown and must be learned from samples. △ Less

Submitted 3 November, 2020; originally announced November 2020.

Comments: Published in IJCAI 2020

Prophet Inequalities with Linear Correlations and Augmentations

Authors: Nicole Immorlica, Sahil Singla, Bo Waggoner

Abstract: In a classical online decision problem, a decision-maker who is trying to maximize her value inspects a sequence of arriving items to learn their values (drawn from known distributions), and decides when to stop the process by taking the current item. The goal is to prove a "prophet inequality": that she can do approximately as well as a prophet with foreknowledge of all the values. In this work,… ▽ More In a classical online decision problem, a decision-maker who is trying to maximize her value inspects a sequence of arriving items to learn their values (drawn from known distributions), and decides when to stop the process by taking the current item. The goal is to prove a "prophet inequality": that she can do approximately as well as a prophet with foreknowledge of all the values. In this work, we investigate this problem when the values are allowed to be correlated. Since non-trivial guarantees are impossible for arbitrary correlations, we consider a natural "linear" correlation structure introduced by Bateni et al. [ESA 2015] as a generalization of the common-base value model of Chawla et al. [GEB 2015]. A key challenge is that threshold-based algorithms, which are commonly used for prophet inequalities, no longer guarantee good performance for linear correlations. We relate this roadblock to another "augmentations" challenge that might be of independent interest: many existing prophet inequality algorithms are not robust to slight increase in the values of the arriving items. We leverage this intuition to prove bounds (matching up to constant factors) that decay gracefully with the amount of correlation of the arriving items. We extend these results to the case of selecting multiple items by designing a new $(1+o(1))$ approximation ratio algorithm that is robust to augmentations. △ Less

Submitted 23 May, 2020; v1 submitted 28 January, 2020; originally announced January 2020.

Comments: 31 pages. Appears in EC 2020

Reducing Inefficiency in Carbon Auctions with Imperfect Competition

Authors: Kira Goldner, Nicole Immorlica, Brendan Lucier

Abstract: We study auctions for carbon licenses, a policy tool used to control the social cost of pollution. Each identical license grants the right to produce a unit of pollution. Each buyer (i.e., firm that pollutes during the manufacturing process) enjoys a decreasing marginal value for licenses, but society suffers an increasing marginal cost for each license distributed. The seller (i.e., the governmen… ▽ More We study auctions for carbon licenses, a policy tool used to control the social cost of pollution. Each identical license grants the right to produce a unit of pollution. Each buyer (i.e., firm that pollutes during the manufacturing process) enjoys a decreasing marginal value for licenses, but society suffers an increasing marginal cost for each license distributed. The seller (i.e., the government) can choose a number of licenses to put up for auction, and wishes to maximize the societal welfare: the total economic value of the buyers minus the social cost. Motivated by emission license markets deployed in practice, we focus on uniform price auctions with a price floor and/or price ceiling. The seller has distributional information about the market, and their goal is to tune the auction parameters to maximize expected welfare. The target benchmark is the maximum expected welfare achievable by any such auction under truth-telling behavior. Unfortunately, the uniform price auction is not truthful, and strategic behavior can significantly reduce (even below zero) the welfare of a given auction configuration. We describe a subclass of "safe-price'" auctions for which the welfare at any Bayes-Nash equilibrium will approximate the welfare under truth-telling behavior. We then show that the better of a safe-price auction, or a truthful auction that allocates licenses to only a single buyer, will approximate the target benchmark. In particular, we show how to choose a number of licenses and a price floor so that the worst-case welfare, at any equilibrium, is a constant approximation to the best achievable welfare under truth-telling after excluding the welfare contribution of a single buyer. △ Less

Submitted 13 December, 2019; originally announced December 2019.

Comments: To appear in the 11th Innovations in Theoretical Computer Science (ITCS 2020)

Asynchronous Majority Dynamics in Preferential Attachment Trees

Authors: Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan, S. Matthew Weinberg

Abstract: We study information aggregation in networks where agents make binary decisions (labeled incorrect or correct). Agents initially form independent private beliefs about the better decision, which is correct with probability $1/2+δ$. The dynamics we consider are asynchronous (each round, a single agent updates their announced decision) and non-Bayesian (agents simply copy the majority announcements… ▽ More We study information aggregation in networks where agents make binary decisions (labeled incorrect or correct). Agents initially form independent private beliefs about the better decision, which is correct with probability $1/2+δ$. The dynamics we consider are asynchronous (each round, a single agent updates their announced decision) and non-Bayesian (agents simply copy the majority announcements among their neighbors, tie-breaking in favor of their private signal). Our main result proves that when the network is a tree formed according to the preferential attachment model \cite{BarabasiA99}, with high probability, the process stabilizes in a correct majority within $O(n \log n/ \log\log n)$ rounds. We extend our results to other tree structures, including balanced $M$-ary trees for any $M$. △ Less

Submitted 7 July, 2020; v1 submitted 12 July, 2019; originally announced July 2019.

Comments: ICALP 2020

Diversity and Exploration in Social Learning

Authors: Nicole Immorlica, Jieming Mao, Christos Tzamos

Abstract: In consumer search, there is a set of items. An agent has a prior over her value for each item and can pay a cost to learn the instantiation of her value. After exploring a subset of items, the agent chooses one and obtains a payoff equal to its value minus the search cost. We consider a sequential model of consumer search in which agents' values are correlated and each agent updates her priors ba… ▽ More In consumer search, there is a set of items. An agent has a prior over her value for each item and can pay a cost to learn the instantiation of her value. After exploring a subset of items, the agent chooses one and obtains a payoff equal to its value minus the search cost. We consider a sequential model of consumer search in which agents' values are correlated and each agent updates her priors based on the exploration of past agents before performing her search. Specifically, we assume the value is the sum of a common-value component, called the quality, and a subjective score. Fixing the variance of the total value, we say a population is more diverse if the subjective score has a larger variance. We ask how diversity impacts average utility. We show that intermediate diversity levels yield significantly higher social utility than the extreme cases of no diversity (when agents under-explore) or full diversity (when agents are unable to learn from each other) and quantify how the impact of the diversity level changes depending on the time spent searching. △ Less

Submitted 13 May, 2019; originally announced May 2019.

Bayesian Exploration with Heterogeneous Agents

Authors: Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, Zhiwei Steven Wu

Abstract: It is common in recommendation systems that users both consume and produce information as they make strategic choices under uncertainty. While a social planner would balance "exploration" and "exploitation" using a multi-armed bandit algorithm, users' incentives may tilt this balance in favor of exploitation. We consider Bayesian Exploration: a simple model in which the recommendation system (the… ▽ More It is common in recommendation systems that users both consume and produce information as they make strategic choices under uncertainty. While a social planner would balance "exploration" and "exploitation" using a multi-armed bandit algorithm, users' incentives may tilt this balance in favor of exploitation. We consider Bayesian Exploration: a simple model in which the recommendation system (the "principal") controls the information flow to the users (the "agents") and strives to incentivize exploration via information asymmetry. A single round of this model is a version of a well-known "Bayesian Persuasion game" from [Kamenica and Gentzkow]. We allow heterogeneous users, relaxing a major assumption from prior work that users have the same preferences from one time step to another. The goal is now to learn the best personalized recommendations. One particular challenge is that it may be impossible to incentivize some of the user types to take some of the actions, no matter what the principal does or how much time she has. We consider several versions of the model, depending on whether and when the user types are reported to the principal, and design a near-optimal "recommendation policy" for each version. We also investigate how the model choice and the diversity of user types impact the set of actions that can possibly be "explored" by each type. △ Less

Submitted 19 February, 2019; originally announced February 2019.

Adversarial Bandits with Knapsacks

Authors: Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, Aleksandrs Slivkins

Abstract: We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions… ▽ More We consider Bandits with Knapsacks (henceforth, BwK), a general model for multi-armed bandits under supply/budget constraints. In particular, a bandit algorithm needs to solve a well-known knapsack problem: find an optimal packing of items into a limited-size knapsack. The BwK problem is a common generalization of numerous motivating examples, which range from dynamic pricing to repeated auctions to dynamic ad allocation to network routing and scheduling. While the prior work on BwK focused on the stochastic version, we pioneer the other extreme in which the outcomes can be chosen adversarially. This is a considerably harder problem, compared to both the stochastic version and the "classic" adversarial bandits, in that regret minimization is no longer feasible. Instead, the objective is to minimize the competitive ratio: the ratio of the benchmark reward to the algorithm's reward. We design an algorithm with competitive ratio O(log T) relative to the best fixed distribution over actions, where T is the time horizon; we also prove a matching lower bound. The key conceptual contribution is a new perspective on the stochastic version of the problem. We suggest a new algorithm for the stochastic version, which builds on the framework of regret minimization in repeated games and admits a substantially simpler analysis compared to prior work. We then analyze this algorithm for the adversarial version and use it as a subroutine to solve the latter. △ Less

Submitted 6 March, 2023; v1 submitted 28 November, 2018; originally announced November 2018.

Comments: The extended abstract appeared in FOCS 2019. The definitive version was published in JACM '22. V8 is the latest version with all technical changes. Subsequent versions fixes minor LATEX presentation issues

Incentivizing Exploration with Selective Data Disclosure

Authors: Nicole Immorlica, Jieming Mao, Aleksandrs Slivkins, Zhiwei Steven Wu

Abstract: We propose and design recommendation systems that incentivize efficient exploration. Agents arrive sequentially, choose actions and receive rewards, drawn from fixed but unknown action-specific distributions. The recommendation system presents each agent with actions and rewards from a subsequence of past agents, chosen ex ante. Thus, the agents engage in sequential social learning, moderated by t… ▽ More We propose and design recommendation systems that incentivize efficient exploration. Agents arrive sequentially, choose actions and receive rewards, drawn from fixed but unknown action-specific distributions. The recommendation system presents each agent with actions and rewards from a subsequence of past agents, chosen ex ante. Thus, the agents engage in sequential social learning, moderated by these subsequences. We asymptotically attain optimal regret rate for exploration, using a flexible frequentist behavioral model and mitigating rationality and commitment assumptions inherent in prior work. We suggest three components of effective recommendation systems: independent focus groups, group aggregators, and interlaced information structures. △ Less

Submitted 31 March, 2026; v1 submitted 14 November, 2018; originally announced November 2018.

Comments: The ACM-EC 2020 conference publication corresponds to the Feb'20 version. Section 7 ("robustness") and Section 8 (the numerical study) were added in, resp., Dec'20 and Nov'24. New discussions (Section 3.2.1 and Appendix B) were added in April'26, as well as a partial reframing of the motivating story to emphasize transparency and deemphasize commitment

Access to Population-Level Signaling as a Source of Inequality

Authors: Nicole Immorlica, Katrina Ligett, Juba Ziani

Abstract: We identify and explore differential access to population-level signaling (also known as information design) as a source of unequal access to opportunity. A population-level signaler has potentially noisy observations of a binary type for each member of a population and, based on this, produces a signal about each member. A decision-maker infers types from signals and accepts those individuals who… ▽ More We identify and explore differential access to population-level signaling (also known as information design) as a source of unequal access to opportunity. A population-level signaler has potentially noisy observations of a binary type for each member of a population and, based on this, produces a signal about each member. A decision-maker infers types from signals and accepts those individuals whose type is high in expectation. We assume the signaler of the disadvantaged population reveals her observations to the decision-maker, whereas the signaler of the advantaged population forms signals strategically. We study the expected utility of the populations as measured by the fraction of accepted members, as well as the false positive rates (FPR) and false negative rates (FNR). We first show the intuitive results that for a fixed environment, the advantaged population has higher expected utility, higher FPR, and lower FNR, than the disadvantaged one (despite having identical population quality), and that more accurate observations improve the expected utility of the advantaged population while harming that of the disadvantaged one. We next explore the introduction of a publicly-observable signal, such as a test score, as a potential intervention. Our main finding is that this natural intervention, intended to reduce the inequality between the populations' utilities, may actually exacerbate it in settings where observations and test scores are noisy. △ Less

Submitted 11 September, 2018; originally announced September 2018.

The Disparate Effects of Strategic Manipulation

Authors: Lily Hu, Nicole Immorlica, Jennifer Wortman Vaughan

Abstract: When consequential decisions are informed by algorithmic input, individuals may feel compelled to alter their behavior in order to gain a system's approval. Models of agent responsiveness, termed "strategic manipulation," analyze the interaction between a learner and agents in a world where all agents are equally able to manipulate their features in an attempt to "trick" a published classifier. In… ▽ More When consequential decisions are informed by algorithmic input, individuals may feel compelled to alter their behavior in order to gain a system's approval. Models of agent responsiveness, termed "strategic manipulation," analyze the interaction between a learner and agents in a world where all agents are equally able to manipulate their features in an attempt to "trick" a published classifier. In cases of real world classification, however, an agent's ability to adapt to an algorithm is not simply a function of her personal interest in receiving a positive classification, but is bound up in a complex web of social factors that affect her ability to pursue certain action responses. In this paper, we adapt models of strategic manipulation to capture dynamics that may arise in a setting of social inequality wherein candidate groups face different costs to manipulation. We find that whenever one group's costs are higher than the other's, the learner's equilibrium strategy exhibits an inequality-reinforcing phenomenon wherein the learner erroneously admits some members of the advantaged group, while erroneously excluding some members of the disadvantaged group. We also consider the effects of interventions in which a learner subsidizes members of the disadvantaged group, lowering their costs in order to improve her own classification performance. Here we encounter a paradoxical result: there exist cases in which providing a subsidy improves only the learner's utility while actually making both candidate groups worse-off--even the group receiving the subsidy. Our results reveal the potentially adverse social ramifications of deploying tools that attempt to evaluate an individual's "quality" when agents' capacities to adaptively respond differ. △ Less

Submitted 10 May, 2019; v1 submitted 26 August, 2018; originally announced August 2018.

Comments: 29 pages, 4 figures

Unleashing Linear Optimizers for Group-Fair Learning and Optimization

Authors: Daniel Alabi, Nicole Immorlica, Adam Tauman Kalai

Abstract: Most systems and learning algorithms optimize average performance or average loss -- one reason being computational complexity. However, many objectives of practical interest are more complex than simply average loss. This arises, for example, when balancing performance or loss with fairness across people. We prove that, from a computational perspective, optimizing arbitrary objectives that take i… ▽ More Most systems and learning algorithms optimize average performance or average loss -- one reason being computational complexity. However, many objectives of practical interest are more complex than simply average loss. This arises, for example, when balancing performance or loss with fairness across people. We prove that, from a computational perspective, optimizing arbitrary objectives that take into account performance over a small number of groups is not significantly harder to optimize than average performance. Our main result is a polynomial-time reduction that uses a linear optimizer to optimize an arbitrary (Lipschitz continuous) function of performance over a (constant) number of possibly-overlapping groups. This includes fairness objectives over small numbers of groups, and we further point out that other existing notions of fairness such as individual fairness can be cast as convex optimization and hence more standard convex techniques can be used. Beyond learning, our approach applies to multi-objective optimization, more generally. △ Less

Submitted 4 June, 2018; v1 submitted 10 April, 2018; originally announced April 2018.

Comments: Accepted for presentation at the Conference on Learning Theory (COLT) 2018

The Importance of Communities for Learning to Influence

Authors: Eric Balkanski, Nicole Immorlica, Yaron Singer

Abstract: We consider the canonical problem of influence maximization in social networks. Since the seminal work of Kempe, Kleinberg, and Tardos, there have been two largely disjoint efforts on this problem. The first studies the problem associated with learning the parameters of the generative influence model. The second focuses on the algorithmic challenge of identifying a set of influencers, assuming the… ▽ More We consider the canonical problem of influence maximization in social networks. Since the seminal work of Kempe, Kleinberg, and Tardos, there have been two largely disjoint efforts on this problem. The first studies the problem associated with learning the parameters of the generative influence model. The second focuses on the algorithmic challenge of identifying a set of influencers, assuming the parameters of the generative model are known. Recent results on learning and optimization imply that in general, if the generative model is not known but rather learned from training data, no algorithm can yield a constant factor approximation guarantee using polynomially-many samples, drawn from any distribution. In this paper, we design a simple heuristic that overcomes this negative result in practice by leveraging the strong community structure of social networks. Although in general the approximation guarantee of our algorithm is necessarily unbounded, we show that this algorithm performs well experimentally. To justify its performance, we prove our algorithm obtains a constant factor approximation guarantee on graphs generated through the stochastic block model, traditionally used to model networks with community structure. △ Less

Submitted 22 January, 2018; originally announced January 2018.

Combinatorial Assortment Optimization

Authors: Nicole Immorlica, Brendan Lucier, Jieming Mao, Vasilis Syrgkanis, Christos Tzamos

Abstract: Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product is fixed in advance, and a probabilistic choice function describes which product a customer will choose from any given subset. We introduce the combinatorial assortment problem, where each customer may select a b… ▽ More Assortment optimization refers to the problem of designing a slate of products to offer potential customers, such as stocking the shelves in a convenience store. The price of each product is fixed in advance, and a probabilistic choice function describes which product a customer will choose from any given subset. We introduce the combinatorial assortment problem, where each customer may select a bundle of products. We consider a model of consumer choice where the relative value of different bundles is described by a valuation function, while individual customers may differ in their absolute willingness to pay, and study the complexity of the resulting optimization problem. We show that any sub-polynomial approximation to the problem requires exponentially many demand queries when the valuation function is XOS, and that no FPTAS exists even for succinctly-representable submodular valuations. On the positive side, we show how to obtain constant approximations under a "well-priced" condition, where each product's price is sufficiently high. We also provide an exact algorithm for $k$-additive valuations, and show how to extend our results to a learning setting where the seller must infer the customers' preferences from their purchasing behavior. △ Less

Submitted 7 November, 2017; v1 submitted 7 November, 2017; originally announced November 2017.

Optimal Data Acquisition for Statistical Estimation

Authors: Yiling Chen, Nicole Immorlica, Brendan Lucier, Vasilis Syrgkanis, Juba Ziani

Abstract: We consider a data analyst's problem of purchasing data from strategic agents to compute an unbiased estimate of a statistic of interest. Agents incur private costs to reveal their data and the costs can be arbitrarily correlated with their data. Once revealed, data are verifiable. This paper focuses on linear unbiased estimators. We design an individually rational and incentive compatible mechani… ▽ More We consider a data analyst's problem of purchasing data from strategic agents to compute an unbiased estimate of a statistic of interest. Agents incur private costs to reveal their data and the costs can be arbitrarily correlated with their data. Once revealed, data are verifiable. This paper focuses on linear unbiased estimators. We design an individually rational and incentive compatible mechanism that optimizes the worst-case mean-squared error of the estimation, where the worst-case is over the unknown correlation between costs and data, subject to a budget constraint in expectation. We characterize the form of the optimal mechanism in closed-form. We further extend our results to acquiring data for estimating a parameter in regression analysis, where private costs can correlate with the values of the dependent variable but not with the values of the independent variables. △ Less

Submitted 5 September, 2018; v1 submitted 3 November, 2017; originally announced November 2017.

Decoupled classifiers for fair and efficient machine learning

Authors: Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, Max Leiserson

Abstract: When it is ethical and legal to use a sensitive attribute (such as gender or race) in machine learning systems, the question remains how to do so. We show that the naive application of machine learning algorithms using sensitive features leads to an inherent tradeoff in accuracy between groups. We provide a simple and efficient decoupling technique, that can be added on top of any black-box machin… ▽ More When it is ethical and legal to use a sensitive attribute (such as gender or race) in machine learning systems, the question remains how to do so. We show that the naive application of machine learning algorithms using sensitive features leads to an inherent tradeoff in accuracy between groups. We provide a simple and efficient decoupling technique, that can be added on top of any black-box machine learning algorithm, to learn different classifiers for different groups. Transfer learning is used to mitigate the problem of having too little data on any one group. The method can apply to a range of fairness criteria. In particular, we require the application designer to specify as joint loss function that makes explicit the trade-off between fairness and accuracy. Our reduction is shown to efficiently find the minimum loss as long as the objective has a certain natural monotonicity property which may be of independent interest in the study of fairness in algorithms. △ Less

Submitted 20 July, 2017; originally announced July 2017.

On-demand or Spot? Selling the cloud to risk-averse customers

Authors: Darrell Hoy, Nicole Immorlica, Brendan Lucier

Abstract: In Amazon EC2, cloud resources are sold through a combination of an on-demand market, in which customers buy resources at a fixed price, and a spot market, in which customers bid for an uncertain supply of excess resources. Standard market environments suggest that an optimal design uses just one type of market. We show the prevalence of a dual market system can be explained by heterogeneous risk… ▽ More In Amazon EC2, cloud resources are sold through a combination of an on-demand market, in which customers buy resources at a fixed price, and a spot market, in which customers bid for an uncertain supply of excess resources. Standard market environments suggest that an optimal design uses just one type of market. We show the prevalence of a dual market system can be explained by heterogeneous risk attitudes of customers. In our stylized model, we consider unit demand risk-averse bidders. We show the model admits a unique equilibrium, with higher revenue and higher welfare than using only spot markets. Furthermore, as risk aversion increases, the usage of the on-demand market increases. We conclude that risk attitudes are an important factor in cloud resource allocation and should be incorporated into models of cloud markets. △ Less

Submitted 19 December, 2016; originally announced December 2016.

Comments: Appeared at WINE 2016