Balasubramanian Sivan

ICML Conference 2024 Conference Paper

A Field Guide for Pacing Budget and ROS Constraints

• Santiago R. Balseiro
• Kshipra Bhawalkar
• Zhe Feng 0004
• Haihao Lu
• Vahab Mirrokni
• Balasubramanian Sivan
• Di Wang 0005

Budget pacing is a popular service that has been offered by major internet advertising platforms since their inception. In the past few years, autobidding products that provide real-time bidding as a service to advertisers have seen a prominent rise in adoption. A popular autobidding stategy is value maximization subject to return-on-spend (ROS) constraints. For historical or business reasons, the systems that govern these two services, namely budget pacing and ROS pacing, are not necessarily always a single unified and coordinated entity that optimizes a global objective subject to both constraints. The purpose of this work is to theoretically and empirically compare algorithms with different degrees of coordination between these two pacing systems. In particular, we compare (a) a fully-decoupled sequential algorithm; (b) a minimally-coupled min-pacing algorithm; (c) a fully-coupled dual-based algorithm. Our main contribution is to theoretically analyze the min-pacing algorithm and show that it attains similar guarantees to the fully-coupled canonical dual-based algorithm. On the other hand, we show that the sequential algorithm, even though appealing by virtue of being fully decoupled, could badly violate the constraints. We validate our theoretical findings empirically by showing that the min-pacing algorithm performs almost as well as the canonical dual-based algorithm on a semi-synthetic dataset that was generated from a large online advertising platform’s auction data.

SODA Conference 2023 Conference Paper

Optimal Pricing Schemes for an Impatient Buyer

• Yuan Deng
• Jieming Mao
• Balasubramanian Sivan
• Kangning Wang 0001

A patient seller aims to sell a good to an impatient buyer (i. e. , one who discounts utility over time). The buyer will remain in the market for a period of time T, and her private value is drawn from a publicly known distribution. What is the revenue-optimal pricing-curve (sequence of (price, time) pairs) for the seller? Is randomization of help here? Is the revenue-optimal pricing-curve computable in polynomial time? We answer these questions in this paper. We give an efficient algorithm for computing the revenue-optimal pricing curve. We show that pricing curves, that post a price at each point of time and let the buyer pick her utility maximizing time to buy, are revenue-optimal among a much broader class of sequential lottery mechanisms: namely, mechanisms that allow the seller to post a menu of lotteries at each point of time cannot get any higher revenue than pricing curves. We also show that the even broader class of mechanisms that allow the menu of lotteries to be adaptively set, can earn strictly higher revenue than that of pricing curves, and the revenue gap can be as big as the support size of the buyer's value distribution. * The full version of the paper can be accessed at https: //arxiv. org/abs/2106. 02149.

SODA Conference 2023 Conference Paper

Pricing Query Complexity of Revenue Maximization

• Renato Paes Leme
• Balasubramanian Sivan
• Yifeng Teng
• Pratik Worah

The common way to optimize auction and pricing systems is to set aside a small fraction of the traffic to run experiments. This leads to the question: how can we learn the most with the smallest amount of data? For truthful auctions, this is the sample complexity problem. For posted price auctions, we no longer have access to samples. Instead, the algorithm is allowed to choose a price p t; then for a fresh sample v t ~ D we learn the sign s t = sign( p t — v t ) ∈ {-1, +1}. How many pricing queries are needed to estimate a given parameter of the underlying distribution? We give tight upper and lower bounds on the number of pricing queries required to find an approximately optimal reserve price for general, regular and MHR distributions. Interestingly, for regular distributions, the pricing query and sample complexities match. But for general and MHR distributions, we show a strict separation between them. All known results on sample complexity for revenue optimization follow from a variant of using the optimal reserve price of the empirical distribution. In the pricing query complexity setting, we show that learning the entire distribution within an error of ε in Levy distance requires strictly more pricing queries than to estimate the reserve. Instead, our algorithm uses a new property we identify called relative flatness to quickly zoom into the right region of the distribution to get the optimal pricing query complexity. * The full version of the paper can be accessed at https: //arxiv. org/abs/2111. 03158

ICML Conference 2023 Conference Paper

Robust Budget Pacing with a Single Sample

• Santiago R. Balseiro
• Rachitesh Kumar
• Vahab Mirrokni
• Balasubramanian Sivan
• Di Wang 0005

Major Internet advertising platforms offer budget pacing tools as a standard service for advertisers to manage their ad campaigns. Given the inherent non-stationarity in an advertiser’s value and also competing advertisers’ values over time, a commonly used approach is to learn a target expenditure plan that specifies a target spend as a function of time, and then run a controller that tracks this plan. This raises the question: how many historical samples are required to learn a good expenditure plan? We study this question by considering an advertiser repeatedly participating in $T$ second-price auctions, where the tuple of her value and the highest competing bid is drawn from an unknown time-varying distribution. The advertiser seeks to maximize her total utility subject to her budget constraint. Prior work has shown the sufficiency of $T\log T$ samples per distribution to achieve the optimal $O(\sqrt{T})$-regret. We dramatically improve this state-of-the-art and show that just one sample per distribution is enough to achieve the near-optimal $\tilde O(\sqrt{T})$-regret, while still being robust to noise in the sampling distributions.

STOC Conference 2022 Conference Paper

Approximately efficient bilateral trade

• Yuan Deng
• Jieming Mao
• Balasubramanian Sivan
• Kangning Wang 0001

We study bilateral trade between two strategic agents. The celebrated result of Myerson and Satterthwaite states that in general, no incentive-compatible, individually rational and weakly budget balanced mechanism can be efficient. I.e., no mechanism with these properties can guarantee a trade whenever buyer value exceeds seller cost. Given this, a natural question is whether there exists a mechanism with these properties that guarantees a constant fraction of the first-best gains-from-trade, namely a constant fraction of the gains-from-trade attainable whenever buyer’s value weakly exceeds seller’s cost. In this work, we positively resolve this long-standing open question on constant-factor approximation, mentioned in several previous works, using a simple mechanism that obtains a 1/8.23 ≈ 0.121 fraction of the first-best.

IJCAI Conference 2021 Conference Paper

Jointly Learning Prices and Product Features

• Ehsan Emamjomeh-Zadeh
• Renato Paes Leme
• Jon Schneider
• Balasubramanian Sivan

Product Design is an important problem in marketing research where a firm tries to learn what features of a product are more valuable to consumers. We study this problem from the viewpoint of online learning: a firm repeatedly interacts with a buyer by choosing a product configuration as well as a price and observing the buyer's purchasing decision. The goal of the firm is to maximize revenue throughout the course of $T$ rounds by learning the buyer's preferences. We study both the case of a set of discrete products and the case of a continuous set of allowable product features. In both cases we provide nearly tight upper and lower regret bounds.

ICML Conference 2021 Conference Paper

Learning to Price Against a Moving Target

• Renato Paes Leme
• Balasubramanian Sivan
• Yifeng Teng
• Pratik Worah

In the Learning to Price setting, a seller posts prices over time with the goal of maximizing revenue while learning the buyer’s valuation. This problem is very well understood when values are stationary (fixed or iid). Here we study the problem where the buyer’s value is a moving target, i. e. , they change over time either by a stochastic process or adversarially with bounded variation. In either case, we provide matching upper and lower bounds on the optimal revenue loss. Since the target is moving, any information learned soon becomes out-dated, which forces the algorithms to keep switching between exploring and exploiting phases.

NeurIPS Conference 2019 Conference Paper

Prior-Free Dynamic Auctions with Low Regret Buyers

• Yuan Deng
• Jon Schneider
• Balasubramanian Sivan

We study the problem of how to repeatedly sell to a buyer running a no-regret, mean-based algorithm. Previous work [Braverman et al. , 2018] shows that it is possible to design effective mechanisms in such a setting that extract almost all of the economic surplus, but these mechanisms require the buyer's values each round to be drawn independently and identically from a fixed distribution. In this work, we do away with this assumption and consider the prior-free setting where the buyer's value each round is chosen adversarially (possibly adaptively). We show that even in this prior-free setting, it is possible to extract a $(1-\varepsilon)$-approximation of the full economic surplus for any $\varepsilon > 0$. The number of options offered to a buyer in any round scales independently of the number of rounds $T$ and polynomially in $\varepsilon$. We show that this is optimal up to a polynomial factor; any mechanism achieving this approximation factor, even when values are drawn stochastically, requires at least $\Omega(1/\varepsilon)$ options. Finally, we examine what is possible when we constrain our mechanism to a natural auction format where overbidding is dominated. Braverman et al. [2018] show that even when values are drawn from a known stochastic distribution supported on $[1/H, 1]$, it is impossible in general to extract more than $O(\log\log H / \log H)$ of the economic surplus. We show how to achieve the same approximation factor in the prior-independent setting (where the distribution is unknown to the seller), and an approximation factor of $O(1 / \log H)$ in the prior-free setting (where the values are chosen adversarially).

NeurIPS Conference 2019 Conference Paper

Strategizing against No-regret Learners

• Yuan Deng
• Jon Schneider
• Balasubramanian Sivan

How should a player who repeatedly plays a game against a no-regret learner strategize to maximize his utility? We study this question and show that under some mild assumptions, the player can always guarantee himself a utility of at least what he would get in a Stackelberg equilibrium. When the no-regret learner has only two actions, we show that the player cannot get any higher utility than the Stackelberg equilibrium utility. But when the no-regret learner has more than two actions and plays a mean-based no-regret strategy, we show that the player can get strictly higher than the Stackelberg equilibrium utility. We construct the optimal game-play for the player against a mean-based no-regret learner who has three actions. When the no-regret learner's strategy also guarantees him a no-swap regret, we show that the player cannot get anything higher than a Stackelberg equilibrium utility.

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.

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.

SODA Conference 2016 Conference Paper

Towards Optimal Algorithms for Prediction with Expert Advice

• Nikolai Gravin
• Yuval Peres
• Balasubramanian Sivan

We study the classical problem of prediction with expert advice in the adversarial setting with a geometric stopping time. In 1965, Cover gave the optimal algorithm for the case of 2 experts. In this paper, we design the optimal algorithm, adversary and regret for the case of 3 experts. Further, we show that the optimal algorithm for 2 and 3 experts is a probability matching algorithm (analogous to Thompson sampling) against a particular randomized adversary. Remarkably, our proof shows that the probability matching algorithm is not only optimal against this particular randomized adversary, but also minimax optimal. Our analysis develops upper and lower bounds simultaneously, analogous to the primal-dual method. Our analysis of the optimal adversary goes through delicate asymptotics of the random walk of a particle between multiple walls. We use the connection we develop to random walks to derive an improved algorithm and regret bound for the case of 4 experts, and, provide a general framework for designing the optimal algorithm and adversary for an arbitrary number of experts.

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.

STOC Conference 2013 Conference Paper

Prior-independent mechanisms for scheduling

• Shuchi Chawla 0001
• Jason D. Hartline
• David L. Malec
• Balasubramanian Sivan

We study the makespan minimization problem with unrelated selfish machines under the assumption that job sizes are stochastic. We design simple truthful mechanisms that under different distributional assumptions provide constant and sublogarithmic approximations to expected makespan. Our mechanisms are prior-independent in that they do not rely on knowledge of the job size distributions. Prior-independent approximations were previously known only for the revenue maximization objective [13, 11, 26]. In contrast to our results, in prior-free settings no truthful anonymous deterministic mechanism for the makespan objective can provide a sublinear approximation [3].

SODA Conference 2012 Conference Paper

Optimal crowdsourcing contests

• Shuchi Chawla 0001
• Jason D. Hartline
• Balasubramanian Sivan

STOC Conference 2010 Conference Paper

Multi-parameter mechanism design and sequential posted pricing

• Shuchi Chawla 0001
• Jason D. Hartline
• David L. Malec
• Balasubramanian Sivan

We study the classic mathematical economics problem of Bayesian optimal mechanism design where a principal aims to optimize expected revenue when allocating resources to self-interested agents with preferences drawn from a known distribution. In single parameter settings (i.e., where each agent's preference is given by a single private value for being served and zero for not being served) this problem is solved [20]. Unfortunately, these single parameter optimal mechanisms are impractical and rarely employed [1], and furthermore the underlying economic theory fails to generalize to the important, relevant, and unsolved multi-dimensional setting (i.e., where each agent's preference is given by multiple values for each of the multiple services available) [25].