Nicole Immorlica

AAAI Conference 2024 Conference Paper

Content Filtering with Inattentive Information Consumers

• Ian Ball
• James Bono
• Justin Grana
• Nicole Immorlica
• Brendan Lucier
• Aleksandrs Slivkins

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 acting on a stream of content. 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 consumer’s information costs, its lack of commitment power may render it useless and lead to inefficient outcomes. When the attacker is also strategic, improvements in filter quality may decrease equilibrium payoffs.

ICML Conference 2024 Conference Paper

Impact of Decentralized Learning on Player Utilities in Stackelberg Games

• Kate Donahue
• Nicole Immorlica
• Meena Jagadeesan
• Brendan Lucier
• Aleksandrs Slivkins

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 $\mathcal{O}(T^{2/3})$ regret for both players with respect to these benchmarks. We further design relaxed environments under which faster learning ($\mathcal{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.

SODA Conference 2024 Conference Paper

Revenue Maximization for Buyers with Costly Participation

• Yannai A. Gonczarowski
• Nicole Immorlica
• Yingkai Li
• Brendan Lucier

IJCAI Conference 2020 Conference Paper

Maximizing Welfare with Incentive-Aware Evaluation Mechanisms

• Nika Haghtalab
• Nicole Immorlica
• Brendan Lucier
• Jack Z. Wang

Motivated by applications such as college admission and insurance rate determination, we study a classification 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 a classification mechanism that maximizes the overall quality score in the population, taking any strategic updating into account. When scores are linear and mechanisms can assign their own scores to agents, we show that the optimal classifier is an appropriate projection of the quality score. For the more restrictive task of binary classification via linear thresholds, we construct a (1/4)-approximation to the optimal classifier 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.

FOCS Conference 2019 Conference Paper

Adversarial Bandits with Knapsacks

• Nicole Immorlica
• Karthik Abinav Sankararaman
• Robert E. Schapire
• Aleksandrs Slivkins

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 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. Our algorithm is the first "black-box reduction" from bandits to BwK: it takes an arbitrary bandit algorithm and uses it as a subroutine. We use this reduction to derive several extensions.

AAAI Conference 2018 Conference Paper

Maximizing Influence in an Unknown Social Network

• Bryan Wilder
• Nicole Immorlica
• Eric Rice
• Milind Tambe

In many real world applications of influence maximization, practitioners intervene in a population whose social structure is initially unknown. This poses a multiagent systems challenge to act under uncertainty about how the agents are connected. We formalize this problem by introducing exploratory influence maximization, in which an algorithm queries individual network nodes (agents) to learn their links. The goal is to locate a seed set nearly as influential as the global optimum using very few queries. We show that this problem is intractable for general graphs. However, real world networks typically have community structure, where nodes are arranged in densely connected subgroups. We present the ARISEN algorithm, which leverages community structure to find an influential seed set. Experiments on real world networks of homeless youth, village populations in India, and others demonstrate ARISEN’s strong empirical performance. To formally demonstrate how ARISEN exploits community structure, we prove an approximation guarantee for ARISEN on graphs drawn from the Stochastic Block Model.

FOCS Conference 2018 Conference Paper

Recharging Bandits

• Robert Kleinberg
• Nicole Immorlica

We introduce a general model of bandit problems in which the expected payout of an arm is an increasing concave function of the time since it was last played. We first develop a PTAS for the underlying optimization problem of determining a reward-maximizing sequence of arm pulls. We then show how to use this PTAS in a learning setting to obtain sublinear regret.

SODA Conference 2017 Conference Paper

Exponential Segregation in a Two-Dimensional Schelling Model with Tolerant Individuals

• Nicole Immorlica
• Robert Kleinberg
• Brendan Lucier
• Morteza Zadomighaddam

We prove that the two-dimensional Schelling segregation model yields monochromatic regions of size exponential in the area of individuals’ neighborhoods, provided that the tolerance parameter is a constant strictly less than 1/2 but sufficiently close to it. Our analysis makes use of a connection with the first-passage percolation model from the theory of stochastic processes.

NeurIPS Conference 2017 Conference Paper

The Importance of Communities for Learning to Influence

• Eric Balkanski
• Nicole Immorlica
• Yaron Singer

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 generative model that produces cascades, and the second focuses on the algorithmic challenge of identifying a set of influencers, assuming the generative model is 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 for influence maximization can yield a constant factor approximation guarantee using polynomially-many samples, drawn from any distribution. In this paper we describe a simple algorithm for maximizing influence from training data. The main idea behind the algorithm is to leverage the strong community structure of social networks and identify a set of individuals who are influentials but whose communities have little overlap. Although in general, the approximation guarantee of such an algorithm is unbounded, we show that this algorithm performs well experimentally. To analyze its performance, we prove this algorithm obtains a constant factor approximation guarantee on graphs generated through the stochastic block model, traditionally used to model networks with community structure.

AAMAS Conference 2017 Conference Paper

Uncharted but not Uninfluenced: Influence Maximization with an Uncertain Network

• Bryan Wilder
• Amulya Yadav
• Nicole Immorlica
• Eric Rice
• Milind Tambe

This paper focuses on new challenges in influence maximization inspired by non-profits’ use of social networks to effect behavioral change in their target populations. Influence maximization is a multiagent problem where the challenge is to select the most influential agents from a population connected by a social network. Specifically, our work is motivated by the problem of spreading messages about HIV prevention among homeless youth using their social network. We show how to compute solutions which are provably close to optimal when the parameters of the influence process are unknown. We then extend our algorithm to a dynamic setting where information about the network is revealed at each stage. Simulation experiments using real world networks collected by the homeless shelter show the advantages of our approach.

STOC Conference 2016 Conference Paper

The price of anarchy in large games

• Michal Feldman
• Nicole Immorlica
• Brendan Lucier
• Tim Roughgarden
• Vasilis Syrgkanis

We present an analysis framework for bounding the price of anarchy (POA) in games that have many players, as in many of the games most pertinent to computer science applications. We use this framework to demonstrate that, in many of the models in which the POA has been studied, the POA in large games is much smaller than the worst-case bound. Our framework also differentiates between mechanisms with similar worst-case performance, such as simultaneous uniform-price auctions and greedy combinatorial auctions, thereby providing new insights about which mechanisms are likely to perform well in realistic settings.

AAAI Conference 2015 Conference Paper

A Unifying Hierarchy of Valuations with Complements and Substitutes

• Uriel Feige
• Michal Feldman
• Nicole Immorlica
• Rani Izsak
• Brendan Lucier
• Vasilis Syrgkanis

We introduce a new hierarchy over monotone set functions, that we refer to as MPH (Maximum over Positive Hypergraphs). Levels of the hierarchy correspond to the degree of complementarity in a given function. The highest level of the hierarchy, MPH-m (where m is the total number of items) captures all monotone functions. The lowest level, MPH-1, captures all monotone submodular functions, and more generally, the class of functions known as XOS. Every monotone function that has a positive hypergraph representation of rank k (in the sense defined by Abraham, Babaioff, Dughmi and Roughgarden [EC 2012]) is in MPH-k. Every monotone function that has supermodular degree k (in the sense defined by Feige and Izsak [ITCS 2013]) is in MPH-(k+1). In both cases, the converse direction does not hold, even in an approximate sense. We present additional results that demonstrate the expressiveness power of MPH-k. One can obtain good approximation ratios for some natural optimization problems, provided that functions are required to lie in low levels of the MPH hierarchy. We present two such applications. One shows that the maximum welfare problem can be approximated within a ratio of k + 1 if all players hold valuation functions in MPH-k. The other is an upper bound of 2k on the price of anarchy of simultaneous first price auctions.

FOCS Conference 2014 Conference Paper

A Simple and Approximately Optimal Mechanism for an Additive Buyer

• Moshe Babaioff
• Nicole Immorlica
• Brendan Lucier
• S. Matthew Weinberg

We consider a monopolist seller with n heterogeneous items, facing a single buyer. The buyer hasa value for each item drawn independently according to(non-identical) distributions, and his value for a set ofitems is additive. The seller aims to maximize his revenue. It is known that an optimal mechanism in this setting maybe quite complex, requiring randomization [19] and menusof infinite size [15]. Hart and Nisan [17] have initiated astudy of two very simple pricing schemes for this setting: item pricing, in which each item is priced at its monopolyreserve; and bundle pricing, in which the entire set ofitems is priced and sold as one bundle. Hart and Nisan [17]have shown that neither scheme can guarantee more thana vanishingly small fraction of the optimal revenue. Insharp contrast, we show that for any distributions, thebetter of item and bundle pricing is a constant-factorapproximation to the optimal revenue. We further discussextensions to multiple buyers and to valuations that arecorrelated across items.

SODA Conference 2014 Conference Paper

Constrained Signaling in Auction Design

• Shaddin Dughmi
• Nicole Immorlica
• Aaron Roth 0001

TCS Journal 2013 Journal Article

Equilibrium pricing with positive externalities

• Nima AhmadiPourAnari
• Shayan Ehsani
• Mohammad Ghodsi
• Nima Haghpanah
• Nicole Immorlica
• Hamid Mahini
• Vahab Mirrokni

We study the problem of selling an item to strategic buyers in the presence of positive historical externalities, where the value of a product increases as more people buy and use it. This increase in the value of the product is the result of resolving bugs or security holes after more usage. We consider a continuum of buyers that are partitioned into types where each type has a valuation function based on the actions of other buyers. Given a fixed sequence of prices, or price trajectory, buyers choose a day on which to purchase the product, i. e. they have to decide whether to purchase the product early in the game or later after more people already own it. We model this strategic setting as a game, study existence and uniqueness of the equilibria, and design an FPTAS to compute an approximately revenue-maximizing pricing trajectory for the seller in two special cases: the symmetric settings in which there is just a single buyer type, and the linear settings that are characterized by an initial type-independent bias and a linear type-dependent influenceability coefficient.

STOC Conference 2012 Conference Paper

An analysis of one-dimensional schelling segregation

• Christina Brandt
• Nicole Immorlica
• Gautam Kamath 0001
• Robert Kleinberg

STOC Conference 2012 Conference Paper

On the limits of black-box reductions in mechanism design

• Shuchi Chawla 0001
• Nicole Immorlica
• Brendan Lucier

We consider the problem of converting an arbitrary approximation algorithm for a single-parameter optimization problem into a computationally efficient truthful mechanism. We ask for reductions that are black-box, meaning that they require only oracle access to the given algorithm and in particular do not require explicit knowledge of the problem constraints. Such a reduction is known to be possible, for example, for the social welfare objective when the goal is to achieve Bayesian truthfulness and preserve social welfare in expectation. We show that a black-box reduction for the social welfare objective is not possible if the resulting mechanism is required to be truthful in expectation and to preserve the worst-case approximation ratio of the algorithm to within a subpolynomial factor. Further, we prove that for other objectives such as makespan, no black-box reduction is possible even if we only require Bayesian truthfulness and an average-case performance guarantee.

STOC Conference 2011 Conference Paper

Dueling algorithms

• Nicole Immorlica
• Adam Tauman Kalai
• Brendan Lucier
• Ankur Moitra
• Andrew Postlewaite
• Moshe Tennenholtz

We revisit classic algorithmic search and optimization problems from the perspective of competition. Rather than a single optimizer minimizing expected cost, we consider a zero-sum game in which a search problem is presented to two players, whose only goal is to outperform the opponent . Such games are typically exponentially large zero-sum games, but they often have a rich structure. We provide general techniques by which such structure can be leveraged to find minmax-optimal and approximate minmax-optimal strategies. We give examples of ranking, hiring, compression, and binary search duels, among others. We give bounds on how often one can beat the classic optimization algorithms in such duels.

TCS Journal 2009 Journal Article

Coordination mechanisms for selfish scheduling

• Nicole Immorlica
• Li (Erran) Li
• Vahab S. Mirrokni
• Andreas S. Schulz

In machine scheduling, a set of jobs must be scheduled on a set of machines so as to minimize some global objective function, such as the makespan, which we consider in this paper. In practice, jobs are often controlled by independent, selfishly acting agents, which each select a machine for processing that minimizes the (expected) completion time. This scenario can be formalized as a game in which the players are job owners, the strategies are machines, and a player’s disutility is the completion time of its jobs in the corresponding schedule. The equilibria of these games may result in larger-than-optimal overall makespan. The price of anarchy is the ratio of the worst-case equilibrium makespan to the optimal makespan. In this paper, we design and analyze scheduling policies, or coordination mechanisms, for machines which aim to minimize the price of anarchy of the corresponding game. We study coordination mechanisms for four classes of multiprocessor machine scheduling problems and derive upper and lower bounds on the price of anarchy of these mechanisms. For several of the proposed mechanisms, we also prove that the system converges to a pure-strategy Nash equilibrium in a linear number of rounds. Finally, we note that our results are applicable to several practical problems arising in communication networks.

SODA Conference 2009 Conference Paper

Secretary problems: weights and discounts

• Moshe Babaioff
• Michael Dinitz
• Anupam Gupta 0001
• Nicole Immorlica
• Kunal Talwar

The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and this decision is irrevocable. Constant-competitive algorithms are known for the classical secretary problems (see, e. g. , the survey of Freeman [7]) and several variants. We study the following two extensions of the secretary problem: • In the discounted secretary problem, there is a time-dependent “discount” factor d ( t ), and the benefit derived from selecting an element/secretary e at time t is d ( t )· v ( e ). For this problem with arbitrary (not necessarily decreasing) functions d ( t ), we show a constant-competitive algorithm when the expected optimum is known in advance. With no prior knowledge, we exhibit a lower bound of, and give a nearly-matching O (log n )-competitive algorithm. • In the weighted secretary problem, up to K secretaries can be selected; when a secretary is selected (s)he must be irrevocably assigned to one of K positions, with position k having weight w ( k ), and assigning object/secretary e to position k has benefit w ( k ) · v ( e ). The goal is to select secretaries and assign them to positions to maximize Σ e, k w ( k ) · v ( e ) · x ek where x ek is an indicator variable that secretary e is assigned position k. We give constant-competitive algorithms for this problem. Most of these results can also be extended to the matroid secretary case (Babaioff et al. [2]) for a large family of matroids with a constant-factor loss, and an O (log rank) loss for general matroids. These results are based on a reduction from various matroids to partition matroids which present a unified approach to many of the upper bounds of Babaioff et al. These problems have connections to online mechanism design (see, e. g. , Hajiaghayi et al. [9]). All our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problems.

STOC Conference 2008 Conference Paper

The myth of the folk theorem

• Christian Borgs
• Jennifer T. Chayes
• Nicole Immorlica
• Adam Tauman Kalai
• Vahab Mirrokni
• Christos H. Papadimitriou

A well-known result in game theory known as "the Folk Theorem" suggests that finding Nash equilibria in repeated games should be easier than in one-shot games. In contrast, we show that the problem of finding any (approximate) Nash equilibrium for a three-player infinitely-repeated game is computationally intractable (even when all payoffs are in {-1,0,1}), unless all of PPAD can be solved in randomized polynomial time. This is done by showing that finding Nash equilibria of (k+1)-player infinitely-repeated games is as hard as finding Nash equilibria of k-player one-shot games, for which PPAD-hardness is known (Daskalakis, Goldberg and Papadimitriou, 2006; Chen, Deng and Teng, 2006; Chen, Teng and Valiant, 2007). This also explains why no computationally-efficient learning dynamics, such as the "no regret" algorithms, can be "rational" (in general games with three or more players) in the sense that, when one's opponents use such a strategy, it is not in general a best reply to follow suit.

FOCS Conference 2007 Conference Paper

Balloon Popping With Applications to Ascending Auctions

• Nicole Immorlica
• Anna R. Karlin
• Mohammad Mahdian
• Kunal Talwar

We study the power of ascending auctions in a scenario in which a seller is selling a collection of identical items to anonymous unit'demand bidders. We show that even with full knowledge of the set of bidders' private valuations for the items, if the bidders are ex-ante identical, no ascending auction can extract more than a constant. times the revenue of the best fixed-price scheme. This problem is equivalent to the problem of coming up with an optimal strategy for blowing up indistinguishable balloons with known capacities in order to maximize the amount of contained, air. We show that the algorithm which simply inflates all balloons to a fixed volume is close to optimal in this setting.

SODA Conference 2007 Conference Paper

Matroids, secretary problems, and online mechanisms

• Moshe Babaioff
• Nicole Immorlica
• Robert Kleinberg

TCS Journal 2006 Journal Article

Correlation clustering in general weighted graphs

• Erik D. Demaine
• Dotan Emanuel
• Amos Fiat
• Nicole Immorlica

We consider the following general correlation-clustering problem [N. Bansal, A. Blum, S. Chawla, Correlation clustering, in: Proc. 43rd Annu. IEEE Symp. on Foundations of Computer Science, Vancouver, Canada, November 2002, pp. 238–250]: given a graph with real nonnegative edge weights and a 〈 + 〉 / 〈 - 〉 edge labelling, partition the vertices into clusters to minimize the total weight of cut 〈 + 〉 edges and uncut 〈 - 〉 edges. Thus, 〈 + 〉 edges with large weights (representing strong correlations between endpoints) encourage those endpoints to belong to a common cluster while 〈 - 〉 edges with large weights encourage the endpoints to belong to different clusters. In contrast to most clustering problems, correlation clustering specifies neither the desired number of clusters nor a distance threshold for clustering; both of these parameters are effectively chosen to be the best possible by the problem definition. Correlation clustering was introduced by Bansal et al. [Correlation clustering, in: Proc. 43rd Annu. IEEE Symp. on Foundations of Computer Science, Vancouver, Canada, November 2002, pp. 238–250], motivated by both document clustering and agnostic learning. They proved NP-hardness and gave constant-factor approximation algorithms for the special case in which the graph is complete (full information) and every edge has the same weight. We give an O ( log n ) -approximation algorithm for the general case based on a linear-programming rounding and the “region-growing’’ technique. We also prove that this linear program has a gap of Ω ( log n ), and therefore our approximation is tight under this approach. We also give an O ( r 3 ) -approximation algorithm for K r, r -minor-free graphs. On the other hand, we show that the problem is equivalent to minimum multicut, and therefore APX-hard and difficult to approximate better than Θ ( log n ).

STOC Conference 2005 Conference Paper

Derandomization of auctions

• Gagan Aggarwal
• Amos Fiat
• Andrew V. Goldberg
• Jason D. Hartline
• Nicole Immorlica
• Madhu Sudan 0001

We study the problem of designing seller-optimal auctions, i.e. auctions where the objective is to maximize revenue. Prior to this work, the only auctions known to be approximately optimal in the worst case employed randomization. Our main result is the existence of deterministic auctions that approximately match the performance guarantees of these randomized auctions. We give a fairly general derandomization technique for turning any randomized mechanism into an asymmetric deterministic one with approximately the same revenue. In doing so, we bypass the impossibility result for symmetric deterministic auctions and show that asymmetry is nearly as powerful as randomization for solving optimal mechanism design problems. Our general construction involves solving an exponential-sized flow problem and thus is not polynomial-time computable. To complete the picture, we give an explicit polynomial-time construction for derandomizing a specific auction with good worst-case revenue. Our results are based on toy problems that have a flavor similar to the hat problem from [3].

SODA Conference 2005 Conference Paper

Limitations of cross-monotonic cost sharing schemes

• Nicole Immorlica
• Mohammad Mahdian
• Vahab Mirrokni

SODA Conference 2005 Conference Paper

Marriage, honesty, and stability

• Nicole Immorlica
• Mohammad Mahdian

SODA Conference 2004 Conference Paper

On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems

• Nicole Immorlica
• David R. Karger
• Maria Minkoff
• Vahab Mirrokni