Nikhil R. Devanur

SODA Conference 2020 Conference Paper

Algorithmic Price Discrimination

• Rachel Cummings
• Nikhil R. Devanur
• Zhiyi Huang 0002
• Xiangning Wang

We consider a generalization of the third degree price discrimination problem studied in [4](Bergemann et al. , 2015), where an intermediary between the buyer and the seller can design market segments to maximize any linear combination of consumer surplus and seller revenue. Unlike in [4], we assume that the intermediary only has partial information about the buyer's value. We consider three different models of information, with increasing order of difficulty. In the first model, we assume that the intermediary's information allows him to construct a probability distribution of the buyer's value. Next we consider the sample complexity model, where we assume that the intermediary only sees samples from this distribution. Finally, we consider a bandit online learning model, where the intermediary can only observe past purchasing decisions of the buyer, rather than her exact value. For each of these models, we present algorithms to compute optimal or near optimal market segmentation.

JMLR Journal 2019 Journal Article

Multi-scale Online Learning: Theory and Applications to Online Auctions and Pricing

• Sébastien Bubeck
• Nikhil R. Devanur
• Zhiyi Huang
• Rad Niazadeh

We consider revenue maximization in online auction/pricing problems. A seller sells an identical item in each period to a new buyer, or a new set of buyers. For the online pricing problem, both when the arriving buyer bids or only responds to the posted price, we design algorithms whose regret bounds scale with the best fixed price in-hindsight, rather than the range of the values. Under the bidding model, we further show our algorithms achieve a revenue convergence rate that matches the offline sample complexity of the single-item single-buyer auction. We also show regret bounds that are scale free, and match the offline sample complexity, when comparing to a benchmark that requires a lower bound on the market share. We further expand our results beyond pricing to multi-buyer auctions, and obtain online learning algorithms for auctions, with convergence rates matching the known sample complexity upper bound of online single-item multi-buyer auctions. These results are obtained by generalizing the classical learning from experts and multi-armed bandit problems to their multi-scale versions. In this version, the reward of each action is in a different range, and the regret with respect to a given action scales with its own range, rather than the maximum range. We obtain almost optimal multi-scale regret bounds by introducing a new Online Mirror Descent (OMD) algorithm whose mirror map is the multi-scale version of the negative entropy function. We further generalize to the bandit setting by introducing the stochastic variant of this OMD algorithm. [abs] [ pdf ][ bib ] &copy JMLR 2019. ( edit, beta )

SODA Conference 2018 Conference Paper

A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications

• Nikhil R. Devanur
• Jugal Garg
• Ruta Mehta
• Vijay V. Vazirani
• Sadra Yazdanbod

SODA Conference 2018 Conference Paper

Truthful Multi-Parameter Auctions with Online Supply: an Impossible Combination

• Nikhil R. Devanur
• Balasubramanian Sivan
• Vasilis Syrgkanis

STOC Conference 2017 Conference Paper

Stability of service under time-of-use pricing

• Shuchi Chawla 0001
• Nikhil R. Devanur
• Alexander E. Holroyd
• Anna R. Karlin
• James B. Martin
• Balasubramanian Sivan

We consider time-of-use pricing as a technique for matching supply and demand of temporal resources with the goal of maximizing social welfare. Relevant examples include energy, computing resources on a cloud computing platform, and charging stations for electric vehicles, among many others. A client/job in this setting has a window of time during which he needs service, and a particular value for obtaining it. We assume a stochastic model for demand, where each job materializes with some probability via an independent Bernoulli trial. Given a per-time-unit pricing of resources, any realized job will first try to get served by the cheapest available resource in its window and, failing that, will try to find service at the next cheapest available resource, and so on. Thus, the natural stochastic fluctuations in demand have the potential to lead to cascading overload events. Our main result shows that setting prices so as to optimally handle the expected demand works well: with high probability, when the actual demand is instantiated, the system is stable and the expected value of the jobs served is very close to that of the optimal offline algorithm.

STOC Conference 2016 Conference Paper

A duality based unified approach to Bayesian mechanism design

• Yang Cai 0001
• Nikhil R. Devanur
• S. Matthew Weinberg

We provide a unified view of many recent developments in Bayesian mechanism design, including the black-box reductions of Cai et. al., simple auctions for additive buyers, and posted-price mechanisms for unit-demand buyers. Additionally, we show that viewing these three previously disjoint lines of work through the same lens leads to new developments as well. First, we provide a duality framework for Bayesian mechanism design, which naturally accommodates multiple agents and arbitrary objectives/feasibility constraints. Using this, we prove that either a posted-price mechanism or the VCG auction with per-bidder entry fees achieves a constant-factor of the optimal Bayesian IC revenue whenever buyers are unit-demand or additive, unifying previous breakthroughs of Chawla et. al. and Yao, and improving both approximation ratios (from 33.75 to 24 and 69 to 8). Finally, we show that this view also leads to improved structural characterizations in the Cai et. al. framework.

SODA Conference 2016 Conference Paper

Simple Pricing Schemes For Consumers With Evolving Values

• Shuchi Chawla 0001
• Nikhil R. Devanur
• Anna R. Karlin
• Balasubramanian Sivan

We consider a pricing problem where a buyer is interested in purchasing/using a good, such as an app or music or software, repeatedly over time. The consumer discovers his value for the good only as he uses it, and the value evolves with each use. Optimizing for the seller's revenue in such dynamic settings is a complex problem and requires assumptions about how the buyer behaves before learning his future value(s), and in particular, how he reacts to risk. We explore the performance of a class of pricing mechanisms that are extremely simple for both the buyer and the seller to use: the buyer reacts to prices myopically without worrying about how his value evolves in the future; the seller needs to optimize for revenue over a space of only two parameters, and can do so without knowing the buyer's risk profile or fine details of the value evolution process. We present simple-versus-optimal type results, namely that under certain assumptions, simple pricing mechanisms of the above form are approximately optimal regardless of the buyer's risk profile. Our results assume that the buyer's value per usage evolves as a martingale. For our main result, we consider pricing mechanisms in which the seller offers the product for free for a certain number of uses, and then charges an appropriate fixed price per usage. We assume that the buyer responds by buying the product for as long as his value exceeds the fixed price. Importantly, the buyer does not need to know anything about how his future value will evolve, only how much he wants to use the product right now. Regardless of the buyers' initial value, our pricing captures as revenue a constant fraction of the total value that the buyers accumulate in expectation over time.

STOC Conference 2016 Conference Paper

The sample complexity of auctions with side information

• Nikhil R. Devanur
• Zhiyi Huang 0002
• Christos-Alexandros Psomas

Traditionally, the Bayesian optimal auction design problem has been considered either when the bidder values are i.i.d, or when each bidder is individually identifiable via her value distribution. The latter is a reasonable approach when the bidders can be classified into a few categories, but there are many instances where the classification of bidders is a continuum. For example, the classification of the bidders may be based on their annual income, their propensity to buy an item based on past behavior, or in the case of ad auctions, the click through rate of their ads. We introduce an alternate model that captures this aspect, where bidders are a priori identical, but can be distinguished based (only) on some side information the auctioneer obtains at the time of the auction. We extend the sample complexity approach of Dhangwatnotai et al. and Cole and Roughgarden to this model and obtain almost matching upper and lower bounds. As an aside, we obtain a revenue monotonicity lemma which may be of independent interest. We also show how to use Empirical Risk Minimization techniques to improve the sample complexity bound of Cole and Roughgarden for the non-identical but independent value distribution case.

UAI Conference 2015 Conference Paper

Budget Constraints in Prediction Markets

• Nikhil R. Devanur
• Miroslav Dudík
• Zhiyi Huang 0002
• David M. Pennock

We give a detailed characterization of optimal trades under budget constraints in a prediction market with a cost-function-based automated market maker. We study how the budget constraints of individual traders affect their ability to impact the market price. As a concrete application of our characterization, we give sufficient conditions for a property we call budget additivity: two traders with budgets B and B 0 and the same beliefs would have a combined impact equal to a single trader with budget B + B 0. That way, even if a single trader cannot move the market much, a crowd of like-minded traders can have the same desired effect. When the set of payoff vectors associated with outcomes, with coordinates corresponding to securities, is affinely independent, we obtain that a generalization of the heavily-used logarithmic market scoring rule is budget additive, but the quadratic market scoring rule is not. Our results may be used both descriptively, to understand if a particular market maker is affected by budget constraints or not, and prescriptively, as a recipe to construct markets.

SODA Conference 2015 Conference Paper

Fast Algorithms for Online Stochastic Convex Programming

• Shipra Agrawal 0001
• Nikhil R. Devanur

We introduce the online stochastic Convex Programming (CP) problem, a very general version of stochastic online problems which allows arbitrary concave objectives and convex feasibility constraints. Many well-studied problems like online stochastic packing and covering, online stochastic matching with concave returns, etc. form a special case of online stochastic CP. We present fast algorithms for these problems, which achieve near-optimal regret guarantees for both the i. i. d. and the random permutation models of stochastic inputs. When applied to the special case online packing, our ideas yield a simpler and faster primal-dual algorithm for this well studied problem, which achieves the optimal competitive ratio. Our techniques make explicit the connection of primal-dual paradigm and online learning to online stochastic CP.

SODA Conference 2015 Conference Paper

Perfect Bayesian Equilibria in Repeated Sales

• Nikhil R. Devanur
• Yuval Peres
• Balasubramanian Sivan

A special case of Myerson's classic result describes the revenue-optimal equilibrium when a seller offers a single item to a buyer. We study a natural repeated sales extension of this model: a seller offers to sell a single fresh copy of an item to the same buyer every day via a posted price. The buyer's value for the item is unknown to the seller but is drawn initially from a publicly known distribution F and remains the same throughout. One key aspect of this game is revelation of the buyer's type through his actions: while the seller might try to learn this value to extract more revenue, the buyer is motivated to hide it to induce lower prices. If the seller is able to commit to future prices, then it is known that the best he can do is extract the Myerson optimal revenue each day. In a more realistic scenario, the seller is unable to commit and must play a perfect Bayesian equilibrium. It is known that not committing to future prices does not help the seller. Thus extracting Myerson optimal revenue each day is a natural upper bound and revenue benchmark in a setting without commitment. We study this setting without commitment and find several suprises. First, if the horizon is fixed, previous work showed that an equilibrium always exists, and all equilibria yield a very low revenue, often times only a constant amount of revenue. This is unintuitive and a far cry from the linearly growing benchmark of obtaining Myerson optimal revenue each day. Our first result shows that this is because the buyer strategies in these equilibria are necessarily unnatural. We restrict to a natural class of buyer strategies, which we call threshold strategies, and show that pure strategy threshold equilibria rarely exist. This offers an explanation for the non-prevalence of bizarre outcomes predicted by previous results. Second, if the seller can commit not to raise prices upon purchase, while still retaining the possibility of lowering prices in future, we recover the natural threshold equilibria by showing that they exist for a large class of distributions including the power law family of distributions. As an example, if the distribution F is uniform in [0, 1], the seller can extract revenue of order in n rounds as opposed to the constant revenue obtainable when he is unable to make any commitments. Finally, we consider the infinite horizon game with partial commitment, where both the seller and the buyer discount the future utility by a factor of 1 – δ ∊ [0, 1). When the value distribution is uniform in [0, 1], there exists a threshold equilibrium with expected revenue at least of the Myerson optimal revenue benchmark. Under some mild assumptions, this equilibrium is also unique.

SODA Conference 2014 Conference Paper

Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms

• Nikhil R. Devanur
• Zhiyi Huang 0002

We consider the problem of online scheduling of jobs on unrelated machines with dynamic speed scaling to minimize the sum of energy and weighted flow time. We give an algorithm with an almost optimal competitive ratio for arbitrary power functions. (No earlier results handled arbitrary power functions for minimizing flow time plus energy with unrelated machines.) For power functions of the form f ( s ) = s α for some constant α > 1, we get a competitive ratio of, improving upon a previous competitive ratio of O ( α 2 ) by Anand et al. [3], along with a matching lower bound of. Further, in the resource augmentation model, with a 1+ ∊ speed up, we give a competitive algorithm, with essentially the same techniques, improving the bound of by Gupta et al. [15] and matching the bound of Anand et al. [3] for the special case of fixed speed unrelated machines. Unlike the previous results most of which used an amortized local competitiveness argument or dual fitting methods, we use a primal-dual method, which is useful not only to analyze the algorithms but also to design the algorithm itself.

SODA Conference 2013 Conference Paper

Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching

• Nikhil R. Devanur
• Kamal Jain
• Robert Kleinberg

We give a simple proof that the ranking algorithm of Karp, Vazirani and Vazirani [KVV90] is 1-1/e competitive for the online bipartite matching problem. The proof is via a randomized primal-dual argument. Primal-dual algorithms have been successfully used for many online algorithm problems, but the dual constraints are always satisfied deterministically. This is the first instance of a non-trivial randomized primal-dual algorithm in which the dual constraints only hold in expectation. The approach also generalizes easily to the vertex-weighted version considered by Agarwal et al. [AGKM11]. Further we show that the proof is very similar to the deterministic primal-dual argument for the online budgeted allocation problem with small bids (also called the AdWords problem) of Mehta et al. [MSVV05].

STOC Conference 2013 Conference Paper

Tatonnement beyond gross substitutes? : gradient descent to the rescue

• Yun Kuen Cheung
• Richard Cole 0001
• Nikhil R. Devanur

Tatonnement is a simple and natural rule for updating prices in Exchange (Arrow-Debreu) markets. In this paper we define a class of markets for which tatonnement is equivalent to gradient descent. This is the class of markets for which there is a convex potential function whose gradient is always equal to the negative of the excess demand and we call it Convex Potential Function (CPF) markets. We show the following results. CPF markets contain the class of Eisenberg Gale (EG) markets, defined previously by Jain and Vazirani. The subclass of CPF markets for which the demand is a differentiable function contains exactly those markets whose demand function has a symmetric negative semi-definite Jacobian. We define a family of continuous versions of tatonnement based on gradient descent using a Bregman divergence. As we show, all processes in this family converge to an equilibrium for any CPF market. This is analogous to the classic result for markets satisfying the Weak Gross Substitutes property. A discrete version of tatonnement converges toward the equilibrium for the following markets of complementary goods; its convergence rate for these settings is analyzed using a common potential function. Fisher markets in which all buyers have Leontief utilities. The tatonnement process reduces the distance to the equilibrium, as measured by the potential function, to an ε fraction of its initial value in O(1/ε) rounds of price updates. Fisher markets in which all buyers have complementary CES utilities. Here, the distance to the equilibrium is reduced to an ε fraction of its initial value in O(log(1/ε)) rounds of price updates. This shows that tatonnement converges for the entire range of Fisher markets when buyers have complementary CES utilities, in contrast to prior work, which could analyze only the substitutes range, together with a small portion of the complementary range.

STOC Conference 2012 Conference Paper

Online matching with concave returns

• Nikhil R. Devanur
• Kamal Jain

We consider a significant generalization of the Adwords problem by allowing arbitrary concave returns, and we characterize the optimal competitive ratio achievable . The problem considers a sequence of items arriving online that have to be allocated to agents, with different agents bidding different amounts. The objective function is the sum, over each agent i, of a monotonically non-decreasing concave function M i : R + -> R + of the total amount allocated to i. All variants of online matching problems (including the Adwords problem) studied in the literature consider the special case of budgeted linear functions, that is, functions of the form M i (u i ) = min {u i ,B i } for some constant B i . The distinguishing feature of this paper is in allowing arbitrary concave returns. The main result of this paper is that for each concave function M, there exists a constant F(M) ≤ 1 such that: there exists an algorithm with competitive ratio of min i F(M i ), independent of the sequence of items. No algorithm has a competitive ratio larger than F(M) over all instances with M i = M for all i. Our algorithm is based on the primal-dual paradigm and makes use of convex programming duality. The upper bounds are obtained by formulating the task of finding the right counterexample as an optimization problem. This path takes us through the calculus of variations which deals with optimizing over continuous functions. The algorithm and the upper bound are related to each other via a set of differential equations, which points to a certain kind of duality between them.

SODA Conference 2010 Conference Paper

Monotonicity in Bargaining Networks

• Yossi Azar
• Nikhil R. Devanur
• Kamal Jain
• Yuval Rabani

TARK Conference 2009 Conference Paper

A computational theory of awareness and decision making

• Nikhil R. Devanur
• Lance Fortnow

We exhibit a new computational-based definition of awareness, informally that our level of unawareness of an object is the amount of time needed to generate that object within a certain environment. We give several examples to show this notion matches our intuition in scenarios where one organizes, accesses and transfers information. We also give a formal process-independent definition of awareness based on Levin’s universal enumeration. We show the usefulness of computational awareness by showing how it relates to decision making, and how others can manipulate our decision making with appropriate advertising, in particular, we show connections to sponsored search and brand awareness. Understanding awareness can also help rate the effectiveness of various user interfaces designed to access information.

FOCS Conference 2009 Conference Paper

Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks

• Yossi Azar
• Benjamin E. Birnbaum
• L. Elisa Celis
• Nikhil R. Devanur
• Yuval Peres

Bargaining games on exchange networks have been studied by both economists and sociologists. A Balanced Outcome for such a game is an equilibrium concept that combines notions of stability and fairness. In a recent paper, Kleinberg and Tardos introduced balanced outcomes to the computer science community and provided a polynomial-time algorithm to compute the set of such outcomes. Their work left open a pertinent question: are there natural, local dynamics that converge quickly to a balanced outcome? In this paper, we provide a partial answer to this question by showing that simple edge-balancing dynamics converge to a balanced outcome whenever one exists.

FOCS Conference 2008 Conference Paper

Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents

• Nikhil R. Devanur
• Ravindran Kannan

We consider markets in the classical Arrow-Debreu model. There are n agents and m goods. Each buyer has a concave utility function (of the bundle of goods he/she buys) and an initial bundle. At an ldquoequilibriumrdquo set of prices for goods, if each individual buyer separately ex-changes the initial bundle for an optimal bundle at the set prices, the market clears, i. e. , all goods are exactly consumed. Classical theorems guarantee the existence of equilibria, but computing them has been the subject of much recent research. In the related area of Multi-Agent Games, much attention has been paid to the complexity as well as algorithms. While most general problems are hard, polynomial time algorithms have been developed for restricted classes of games, when one assumes the number of strategies is constant. For the Market Equilibrium problem, several important special cases of utility functions have been tackled. Here we begin a program for this problem similar to that for multi-agent games, where general utilities are considered. We begin by showing that if the utilities are separable piece-wise linear concave (PLC) functions, and the number of goods(or alternatively the number of buyers) is constant, then we can compute an exact equilibrium in polynomial time. Our technique for the constant number of goods is to de-compose the space of price vectors into cells using certain hyperplanes, so that in each cell, each buyerpsilas threshold marginal utility is known. Still, one needs to solve a linear optimization problem in each cell. We then show the main result - that for general (non-separable) PLC utilities, an exact equilibrium can be found in polynomial time provided the number of goods is constant. The starting point of the algorithm is a ldquocell-decompositionrdquo of the space of price vectors using polynomial surfaces (instead of hyperplanes). We use results from computational algebraic geometry to bound the number of such cells. For solving the problem inside each cell, we introduce and use a novel LP-duality based method. We note that if the number of buyers and agents both can vary, the problem is PPAD hard even for the very special case of PLC utilities - namely Leontief utilities.

STOC Conference 2006 Conference Paper

Integrality gaps for sparsest cut and minimum linear arrangement problems

• Nikhil R. Devanur
• Subhash Khot
• Rishi Saket
• Nisheeth K. Vishnoi

Arora, Rao and Vazirani [2] showed that the standard semi-definite programming (SDP) relaxation of the Sparsest Cut problem with the triangle inequality constraints has an integrality gap of O(√log n). They conjectured that the gap is bounded from above by a constant. In this paper, we disprove this conjecture (referred to as the ARV-Conjecture) by constructing an Ω(log log n) integrality gap instance. Khot and Vishnoi [16] had earlier disproved the non-uniform version of the ARV-Conjecture.A simple "stretching" of the integrality gap instance for the Sparsest Cut problem serves as an Ω(log log n) integrality gap instance for the SDP relaxation of the Minimum Linear Arrangement problem. This SDP relaxation was considered in [6, 11], where it was shown that its integrality gap is bounded from above by O(√log n log log n).

STOC Conference 2004 Conference Paper

The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results

• Nikhil R. Devanur

The traditional model of market equilibrium supports impressive existence results, including the celebrated Arrow-Debreu Theorem. However, in this model, polynomial time algorithms for computing (or approximating) equilibria are known only for linear utility functions. We present a new, and natural, model of market equilibrium that not only admits existence and uniqueness results paralleling those for the traditional model but is also amenable to efficient algorithms.

FOCS Conference 2002 Conference Paper

Market Equilibrium via a Primal-Dual-Type Algorithm

• Nikhil R. Devanur
• Christos H. Papadimitriou
• Amin Saberi
• Vijay V. Vazirani

Although the study of market equilibria has occupied center stage within mathematical economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We provide the first such algorithm for the linear version of a problem defined by Irving Fisher in 1891. Our algorithm is modeled after Kuhn's (1995) primal-dual algorithm for bipartite matching.