Secretary Problems: Weights and Discounts (2009)
Moshe Babaioff, Michael Dinitz, Anupam Gupta, 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...
A Combinatorial Allocation Mechanism With Penalties For Banner Advertising (2009)
Uriel Feige, Nicole Immorlica, Hamid Nazerzadeh, Vahab S. Mirrokni
Most current banner advertising is sold through negotiation thereby incurring large transaction costs and possibly suboptimal allocations. We propose a new automated system for selling banner...
Secretary Problems: Weights and Discounts (2009)
Moshe Babaioff, Michael Dinitz, Anupam Gupta, 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...
The Unsplittable Stable Marriage Problem (2008)
Brian C. Dean, Michel X. Goemans, Nicole Immorlica
Abstract. The Gale-Shapley “propose/reject ” algorithm is a wellknown procedure for solving the classical stable marriage problem. In this paper we study this algorithm in the context of the...
Nicole Immorlica, Evdokia Nikolova
We study first-price auction mechanisms for auctioning flow between given nodes in a graph. A first-price auction is any auction in which links on winning paths are paid their bid amount; the...
Gagan Aggarwal, Jason D. Hartline, Nicole Immorlica, Andrew V. Goldberg
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...
F.2 [Theory of Computation]: ANALYSIS OF AL- GORITHMS AND PROBLEM COMPLEXITY (2008)
Redmond Wa, Nicole Immorlica, Jennifer Chayes, Kamal Jain, Omid Etesami, Mohammad Mahdian
We consider the problem of online keyword advertising auctions among multiple bidders with limited budgets, and study a natural bidding heuristic in which advertisers attempt to optimize their...
Correlation Clustering in General Weighted Graphs (2008)
Erik D. Demaine, Dotan Emanuel, Amos Fiat, Nicole Immorlica
We consider the following general correlation-clustering problem [1]: given a graph with real nonnegative edge weights and a 〈+〉/〈− 〉 edge labeling, partition the vertices into clusters to...
Abstract Matroids, Secretary Problems, and Online Mechanisms (2008)
Moshe Babaioff, Nicole Immorlica, Robert Kleinberg
We study a generalization of the classical secretary problem which we call the “matroid secretary problem”. In this problem, the elements of a matroid are presented to an online algorithm in...
F.2 [Theory of Computation]: ANALYSIS OF AL- GORITHMS AND PROBLEM COMPLEXITY (2008)
Redmond Wa, Nicole Immorlica, Jennifer Chayes, Kamal Jain, Omid Etesami, Mohammad Mahdian
We consider the problem of online keyword advertising auctions among multiple bidders with limited budgets, and study a natural bidding heuristic in which advertisers attempt to optimize their...
Abstract Matroids, Secretary Problems, and Online Mechanisms (2008)
Moshe Babaioff, Nicole Immorlica, Robert Kleinberg
We study a generalization of the classical secretary problem which we call the “matroid secretary problem”. In this problem, the elements of a matroid are presented to an online algorithm in...
Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni
of cross-monotonic cost sharing schemes
Gagan Aggarwal, Jason D. Hartline, Nicole Immorlica, Andrew V. Goldberg
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...
Tutorial Proposal: Mechanism Design for Online Advertisement (2008)
Nicole Immorlica, Mohammad Mahdian
Online advertising is a booming industry and is developing into a major advertising outlet for millions of firms. In 2004, in United States alone, firms spent $9.6 billion on online advertising, a...
Balloon Popping With Applications to Ascending Auctions (2008)
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...
Game-Theoretic Aspects of Designing Hyperlink Structures (2008)
Nicole Immorlica, Kamal Jain, Mohammad Mahdian
Abstract. We study the problem of designing the hyperlink structure between the web pages of a web site in order to maximize the revenue generated from the traffic on the web site. We show this...
A Knapsack Secretary Problem with Applications (2008)
Moshe Babaioff, Nicole Immorlica, David Kempe
Fellowship. Portions of this work were completed while the author was a postdoctoral fellow at UC Berkeley. Abstract. We consider situations in which a decision-maker with a fixed budget faces a...
The Unsplittable Stable Marriage Problem (2008)
Brian C. Dean, Michel X. Goemans, Nicole Immorlica
Abstract. The Gale-Shapley “propose/reject ” algorithm is a wellknown procedure for solving the classical stable marriage problem. In this paper we study this algorithm in the context of the...
Abstract Matroids, Secretary Problems, and Online Mechanisms (2008)
Moshe Babaioff, Nicole Immorlica, Robert Kleinberg
We study a generalization of the classical secretary problem which we call the “matroid secretary problem”. In this problem, the elements of a matroid are presented to an online algorithm in...
Gagan Aggarwal, Jason D. Hartline, Nicole Immorlica, Andrew V. Goldberg
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...
The myth of the folk theorem (2008)
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, Christos Papadimitriou
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 (epsilon) Nash equilibrium for a...
The myth of the folk theorem (2008)
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, Christos 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...
Dynamics of bid optimization in online advertisement auctions (2007)
Christian Borgs, Nicole Immorlica, Jennifer Chayes, Kamal Jain
We consider the problem of online keyword advertising auctions among multiple bidders with limited budgets, and study a natural bidding heuristic in which advertisers attempt to optimize their...
Dynamics of bid optimization in online advertisement auctions (2007)
Christian Borgs, Nicole Immorlica, Jennifer Chayes, Kamal Jain
We consider the problem of online keyword advertising auctions among multiple bidders with limited budgets, and study a natural bidding heuristic in which advertisers attempt to optimize their...
Dynamics of bid optimization in online advertisement auctions (2007)
Christian Borgs, Jennifer Chayes, Omid Etesami, Nicole Immorlica, Kamal Jain, Mohammad Mahdian
We consider the problem of online keyword advertising auctions among multiple bidders with limited budgets, and propose a bidding heuristic to optimize the utility for bidders by equalizing the...
A knapsack secretary problem with applications (2007)
Moshe Babaioff, Nicole Immorlica, David Kempe
Fellowship. Portions of this work were completed while the author was a postdoctoral
Secretary problems with competing employers (2006)
Nicole Immorlica, Robert Kleinberg, Mohammad Mahdian
Abstract. In many decentralized labor markets, job candidates are offered positions at very early stages in the hiring process. It has been argued that these early offers are an effect of the...
Secretary problems with competing employers (2006)
Nicole Immorlica, Robert Kleinberg, Mohammad Mahdian
Abstract. In many decentralized labor markets, job candidates are offered positions at very early stages in the hiring process. It has been argued that these early offers are an effect of the...
Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan
We study the problem of designing seller optimal auctions. Prior to this work, the only previously known auctions that are approximately optimal in worst case employ randomization. Our main result is...
Multi-unit auctions with budget-constrained bidders (2005)
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Mohammad Mahdian
We study a multi-unit auction with multiple bidders, each of whom has a private valuation and a budget. The truthful mechanisms of such an auction are characterized, in the sense that, under standard...
Multi-unit auctions with budget-constrained bidders (2005)
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Mohammad Mahdian
We study a multi-unit auction with multiple bidders, each of whom has a private valuation and a budget. The truthful mechanisms of such an auction are characterized, in the sense that, under standard...
Semantic Similarity between Search Engine Queries Using Temporal Correlation (2005)
We investigate the idea of finding semantically related search engine queries based on their temporal correlation; in other words, we infer that two queries are related if their popularities behave...
A First Look at Peer-to-Peer Worms: Threats and Defenses (2005)
Lidong Zhou, Lintao Zhang, Frank Mcsherry, Nicole Immorlica, Manuel Costa, Steve Chien
Peer-to-peer (P2P) worms exploit common vulnerabilities in member hosts of a P2P network and spread topologically in the P2P network, a potentially more effective strategy than random scanning for...
Marriage, honesty, and stability (2005)
Nicole Immorlica, Mohammad Mahdian
Many centralized two-sided markets form a matching between participants by running a stable marriage algorithm. It is a well-known fact that no matching mechanism based on a stable marriage algorithm...
First-price path auctions (2005)
Nicole Immorlica, Evdokia Nikolova, David Karger, Rahul Sami
We study first-price auction mechanisms for auctioning flow between given nodes in a graph. A first-price auction is any auction in which links on winning paths are paid their bid amount; the...
Click Fraud Resistant Methods for Learning Click-Through Rates (2005)
Nicole Immorlica, Kamal Jain, Mohammad Mahdian, Kunal Talwar
Abstract. In pay-per-click online advertising systems like Google, Overture, or MSN, advertisers are charged for their ads only when a user clicks on the ad. While these systems have many advantages...
Coordination mechanisms for selfish scheduling (2005)
Nicole Immorlica, Li (erran Li, Vahab S. Mirrokni, Andreas Schulz
Abstract. In machine scheduling, a set of n jobs must be scheduled on a set of m machines. Each job i incurs a processing time of pij on machine j and the goal is to schedule jobs so as to minimize...
Multi-unit auctions with budget-constrained bidders (2005)
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Mohammad Mahdian, Amin Saberi
We study a multi-unit auction with multiple agents, each of whom has a private valuation and budget. The truthful mechanisms of such an auction are characterized, in the sense that, under standard...
Computing With Strategic Agents (2005)
Nicole Immorlica, Erik D. Demaine
This dissertation studies mechanism design for various combinatorial problems in the presence of strategic agents. A mechanism is an algorithm for allocating a resource among a group of participants,...
Marriage, Honesty, and Stability (2003)
Immorlica, Nicole, Mahdian, Mohammad
Many centralized two-sided markets form a matching between participantsby running a stable marriage algorithm. It is a well-knownfact that no matching mechanism based on a stable marriage...
Marriage, Honesty, and Stability (2003)
Immorlica, Nicole, Mahdian, Mohammad
Many centralized two-sided markets form a matching between participantsby running a stable marriage algorithm. It is a well-knownfact that no matching mechanism based on a stable marriage...
Mohammadtaghi Hajiaghayi, Nicole Immorlica, Vahab S. Mirrokni
In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power while...
Correlation clustering with partial information (2003)
Erik D. Demaine, Nicole Immorlica
Abstract. We consider the following general correlation-clustering problem [1]: given a graph with real edge weights (both positive and negative), partition the vertices into clusters to minimize the...
Power Optimization in Fault-Tolerant Topology Control Algorithms for (2003)
Mohammadtaghi Hajiaghayi, Nicole Immorlica
ABSTRACT In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power...
Lower Bounds for Cost Sharing and Group-Strategyproof Mechanisms
Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni
A cost-sharing scheme is a set of rules defining how to share the cost of a service (often computed by solving a combinatorial optimization problem) amongst serviced customers. A cost-sharing scheme...