# Aranyak Mehta

### Research Areas

Authored Publications

Google Publications

Other Publications

Sort By

Incentive Compatibility in the Auto-bidding World

Yeganeh Alimohammadi

Andres Perlroth

24th ACM Conference on Economics and Computation, EC 2023

Preview abstract
Auto-bidding has recently become a popular feature in ad auctions. This feature enables advertisers to simply provide high-level constraints and goals to an automated agent, which optimizes their auction bids on their behalf. These auto-bidding intermediaries interact in a decentralized manner in the underlying auctions, leading to new interesting practical and theoretical questions on auction design, for example, in understanding the bidding equilibrium properties between auto-bidder intermediaries for different auctions. In this paper, we examine the effect of different auctions on the incentives of advertisers to report their constraints to the auto-bidder intermediaries. More precisely, we study whether canonical auctions such as first price auction (FPA) and second price auction (SPA) are auto-bidding incentive compatible (AIC): whether an advertiser can gain by misreporting their constraints to the autobidder.
View details

Simple Mechanisms for Welfare Maximization in Rich Advertising Auctions

Divyarthi Mohan

Alex Psomas

Advances in Neural Information Processing Systems 35 (NeurIPS 2022) Main Conference Track

Preview abstract
Internet ad auctions have evolved from a few lines of text to richer informational layouts that include images, sitelinks, videos, etc. Ads in these new formats occupy varying amounts of space, and an advertiser can provide multiple formats, only one of which can be shown.The seller is now faced with a multi-parameter mechanism design problem.Computing an efficient allocation is computationally intractable, and therefore the standard Vickrey-Clarke-Groves (VCG) auction, while truthful and welfare-optimal, is impractical. In this paper, we tackle a fundamental problem in the design of modern ad auctions. We adopt a
Myersonian'' approach and study allocation rules that are monotone both in the bid and set of rich ads. We show that such rules can be paired with a payment function to give a truthful auction. Our main technical challenge is designing a monotone rule that yields a good approximation to the optimal welfare. Monotonicity doesn't hold for standard algorithms, e.g. the incremental bang-per-buck order, that give good approximations to
knapsack-like'' problems such as ours. In fact, we show that no deterministic monotone rule can approximate the optimal welfare within a factor better than 2 (while there is a non-monotone FPTAS). Our main result is a new, simple, greedy and monotone allocation rule that guarantees a 3-approximation. In ad auctions in practice, monotone allocation rules are often paired with the so-called \emph{Generalized Second Price (GSP)} payment rule, which charges the minimum threshold price below which the allocation changes. We prove that, even though our monotone allocation rule paired with GSP is not truthful, its Price of Anarchy (PoA) is bounded. Under standard no-overbidding assumptions, we prove bounds on the a pure and Bayes-Nash PoA. Finally, we experimentally test our algorithms on real-world data.
View details

Auction design in an auto-bidding setting: Randomization improves efficiency beyond VCG

Proceedings of the ACM Web Conference 2022, pp. 173-181

Preview abstract
Auto-bidding is an area of increasing importance in the domain of online advertising. We study the problem of designing auctions in an auto-bidding setting with the goal of maximizing welfare at system equilibrium. Previous results showed that the price of anarchy (PoA) under VCG is 2 and also that this is tight even with two bidders. This raises an interesting question as to whether VCG yields the best efficiency in this setting, or whether the PoA can be improved upon. We present a prior-free randomized auction in which the PoA is approx. 1.896 for the case of two bidders, proving that one can achieve an efficiency strictly better than that under VCG in this setting. We also provide a stark impossibility result for the problem in general as the number of bidders increases -- we show that no (randomized) anonymous truthful auction can have a PoA strictly better than 2 asymptotically as the number of bidders per query increases. While it was shown in previous work that one can improve on the PoA of 2 if the auction is allowed to use the bidder's values for the queries in addition to the bidder's bids, we note that our randomized auction is prior-free and does not use such additional information; our impossibility result also applies to auctions without additional value information.
View details

Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions

Zhe Feng

Guru Prashanth Guruganesh

Chris Liaw

Abhishek Sethi

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21) (2021)

Preview abstract
The connection between games and no-regret algorithms has been widely studied in the literature. A
fundamental result is that when all players play no-regret strategies, this produces a sequence of actions
whose time-average is a coarse-correlated equilibrium of the game. However, much less is known about
equilibrium selection in the case that multiple equilibria exist.
In this work, we study the convergence of no-regret bidding algorithms in auctions. Besides being of
theoretical interest, bidding dynamics in auctions is an important question from a practical viewpoint as
well. We study repeated game between bidders in which a single item is sold at each time step and the
bidder’s value is drawn from an unknown distribution. We show that if the bidders use any mean-based
learning rule then the bidders converge with high probability to the truthful pure Nash Equilibrium in a
second price auction, in VCG auction in the multi-slot setting and to the Bayesian Nash equilibrium in a
first price auction. We note mean-based algorithms cover a wide variety of known no-regret algorithms
such as Exp3, UCB, -Greedy etc. Also, we analyze the convergence of the individual iterates produced by
such learning algorithms, as opposed to the time-average of the sequence. Our experiments corroborate
our theoretical findings and also find a similar convergence when we use other strategies such as Deep
Q-Learning.
View details

Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics

Alex Psomas

Aviad Rubinstein

Advances in Neural Information Processing Systems (2020)

Preview abstract
We consider the fundamental problem of selecting k out of n random variables
in a way that the expected highest or second-highest value is maximized. This
question captures several applications where we have uncertainty about the quality
of candidates (e.g. auction bids, search results) and have the capacity to explore
only a small subset due to an exogenous constraint. For example, consider a second
price auction where system constraints (e.g., costly retrieval or model computation)
allow the participation of only k out of n bidders, and the goal is to optimize the
expected efficiency (highest bid) or expected revenue (second highest bid).
We study the case where we are given an explicit description of each random
variable. We give a PTAS for the problem of maximizing the expected highest value.
For the second-highest value, we prove a hardness result: assuming the Planted
Clique Hypothesis, there is no constant factor approximation algorithm that runs
in polynomial time. Surprisingly, under the assumption that each random variable
has monotone hazard rate (MHR), a simple score-based algorithm, namely picking
the k random variables with the largest 1/\sqrt{k} top quantile value, is a constant
approximation to the expected highest and second highest value, simultaneously.
View details

A new dog learns old tricks: RL finds classic optimization algorithms

Weiwei Kong

Christopher Liaw

D. Sivakumar

Seventh International Conference on Learning Representations (ICLR) (2019)

Preview abstract
We ask whether reinforcement learning can find theoretically optimal algorithms for online optimization problems, and introduce a novel learning framework in this setting. To answer this question, we introduce a number of key ideas from traditional algorithms and complexity theory. Specifically, we introduce the concept of adversarial distributions (universal and high-entropy training sets), which are distributions that encourage the learner to find algorithms that work well in the worst case. We test our new ideas on the AdWords problem, the online knapsack problem, and the secretary problem. Our results indicate that the models have learned behaviours that are consistent with the optimal algorithms for these problems derived using the online primal-dual framework.
View details

Biobjective Online Bipartite Matching

Yang Cai

George Pierrakos

Workshop in Internet and Network Economics, Springer (2014), pp. 218-231

Preview abstract
Motivated by Online Ad allocation when there are multiple conflicting objectives, we introduce and study the problem of Biobjective Online Bipartite Matching, a strict generalization of the standard setting of Karp, Vazirani and Vazirani, where we are allowed to have edges of two colors, and the goal is to find a matching that is both large and balanced at the same time. We study both deterministic and randomized algorithms for
this problem; after showing that the single color upper bounds of 1/2 and 1 − 1/e carry over to our biobjective setting as well, we show that a very natural, albeit hard to analyze, deterministic algorithm achieves a competitive ratio of 0.343. We next show how a natural randomized algorithm matches this ratio, through a simpler analysis, and how a clever – and perhaps not immediately obvious – generalization of Ranking can beat the 1/2 bound and get a competitive ratio of 0.573, coming close to matching the upper bound of 0.63.
View details

Optimizing Budget Constrained Spend in Search Advertising

Chinmay Karande

Sixth ACM International Conference on Web Search and Data Mining, WSDM 2013, ACM, pp. 697-706

Preview abstract
Search engine ad auctions typically have a significant fraction of advertisers who are budget constrained, i.e., if allowed to participate in every auction that they bid on, they would spend more than their budget. This yields an important problem: selecting the ad auctions in which these advertisers participate, in order to optimize different system objectives such as the return on investment for advertisers, and the quality of ads shown to users. We present a system and algorithms for optimizing such budget constrained spend. The system is designed be deployed in a large search engine, with hundreds of thousands of advertisers, millions of searches per hour, and with the query stream being only partially predictable. We have validated the system design by implementing it in the Google ads serving system and running experiments on live traffic. We have also compared our algorithm to previous work that casts this problem as a large linear programming problem limited to popular queries, and show that our algorithms yield substantially better results.
View details

Online Matching and Ad Allocation

Foundations and Trends in Theoretical Computer Science, vol. 8 (4) (2013), pp. 265-368

Preview abstract
Matching is a classic problem with a rich history and a significant impact, both on the theory of algorithms and in practice. Recently there has been a surge of interest in the online version of matching and its generalizations, due to the important new application domain of Internet advertising. The theory of online matching and allocation has played a critical role in designing algorithms for ad allocation. This monograph surveys the key problems, models and algorithms from online matchings, as well as their implication in the practice of ad allocation. The goal is to provide a classification of the problems in this area, an introduction into the techniques used, a glimpse into the practical impact, and to provide direction in terms of open questions. Matching continues to find core applications in diverse domains, and the advent of massive online and streaming data emphasizes the future applicability of the algorithms and techniques surveyed here.
View details

Designing Markets for Daily Deals

Preview
Yang Cai

Bo Waggoner

Conference on Web and Internet Economics (WINE) (2013) (to appear)

Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations

Chinmay Karande

Proceedings of ACM-SIAM Symposium on Discrete Algorithms (2011)

Preview abstract
We study the following vertex-weighted online bipartite matching problem: G(U, V, E) is a bipartite graph. The vertices in U have weights and are known ahead of time, while the vertices in V arrive online in an arbitrary order and have to be matched upon arrival. The goal is to maximize the sum of weights of the matched vertices in U. When all the weights are equal, this reduces to the classic online bipartite matching problem for which Karp, Vazirani and Vazirani gave an optimal (1 − 1/e)-competitive algorithm in their seminal work [KVV90]. Our main result is an optimal (1 − 1/e)-competitive randomized algorithm for general vertex
weights. We use random perturbations of weights by appropriately chosen multiplicative factors. Our solution constitutes the ﬁrst known generalization of the algorithm in [KVV90] in this model and provides new insights into the role of randomization in online allocation problems. It also effectively solves the problem of online budgeted allocations [MSVV05] in the case when an agent makes the same bid for any desired item, even if the bid is comparable to his budget - complementing the results of [MSVV05, BJN07] which apply when the bids are much smaller than the budgets.
View details

A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model.

Preview
Bahman Bahmani

Rajeev Motwani

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010,, SIAM, pp. 31-39

Efficiency of (Revenue-)Optimal Mechanisms

Proceedings of the 10th ACM Conference on Electronic Commerce (2009)

Preview abstract
We compare the expected efficiency of revenue maximizing (or optimal) mechanisms with that of efficiency maximizing ones. We show that the efficiency of the revenue maximizing mechanism for selling a single item with (k + log_{e / e−1} k + 1) bidders is at least as much as the efficiency of the efficiency-maximizing mechanism with k bidders, when bidder valuations are drawn i.i.d. from a Monotone Hazard Rate distribution. Surprisingly, we also show that this bound is tight within a small additive constant of 5.7. In other words, Θ(log k) extra bidders suffice for the revenue maximizing mechanism to match the efficiency of the efficiency maximizing mechanism, while o(log k) do not. This is in contrast to the result of Bulow and Klemperer comparing the revenue of the two mechanisms, where only one extra bidder suffices. More precisely, they show that the revenue of the efficiency maximizing mechanism with k + 1 bidders is no less than the revenue of the revenue maximizing mechanism with k bidders.
We extend our result for the case of selling t identical items and show that 2.2 log k + tΘ(log log k) extra bidders suffice for the revenue maximizing mechanism to match the
efficiency of the efficiency maximizing mechanism.
In order to prove our results, we do a classification of Monotone Hazard Rate (MHR) distributions and identify a family of MHR distributions, such that for each class in our classification, there is a member of this family that is point-wise lower than every distribution in that class. This lets us prove interesting structural theorems about distributions with Monotone Hazard Rate.
View details

On the Fourier spectrum of symmetric Boolean functions

Preview
Mihail N. Kolountzakis

Richard J. Lipton

Evangelos Markakis

Nisheeth K. Vishnoi

Combinatorica, vol. 29 (2009), pp. 363-387

Online Stochastic Matching: Beating 1-1/e

S. Muthukrishnan

Symposium on the Foundations of Computer Science (FOCS) (2009)

Preview abstract
We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani and Vazirani gives an approximation ratio of 1−1e≃0.632, a very familiar bound that holds for many online problems; further, the bound is tight in this case. In the online, stochastic case when nodes are drawn repeatedly from a known distribution, the greedy algorithm matches this approximation ratio, but still, no algorithm is known that beats the 1−1e bound.Our main result is a 0.67-approximation online algorithm for stochastic bipartite matching, breaking this 1−1e barrier. Furthermore, we show that no online algorithm can produce a 1−ϵ approximation for an arbitrarily small ϵ for this problem. Our algorithms are based on computing an optimal offline solution to the expected instance, and using this solution as a guideline in the process of online allocation. We employ a novel application of the idea of the power of two choices from load balancing: we compute two disjoint solutions to the expected instance, and use both of them in the online algorithm in a prescribed preference order. To identify these two disjoint solutions, we solve a max flow problem in a boosted flow graph, and then carefully decompose this maximum flow to two edge-disjoint (near-) matchings. In addition to guiding the online decision making, these two offline solutions are used to characterize an upper bound for the optimum in any scenario. This is done by identifying a cut whose value we can bound under the arrival distribution. At the end, we discuss extensions of our results to more general bipartite allocations that are important in a display ad application.
View details

Online budgeted matching in random input models with applications to Adwords

Preview
Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, SIAM, San Francisco (2008), pp. 982-991

Adwords Auctions with Decreasing Valuation Bids

Preview
Internet and Network Economics (WINE), Springer, San Diego (2007), pp. 335-340

Is Shapley Cost Sharing Optimal?

S. Dobzinski

T. Roughgarden

M. Sundararajan

Lecture Notes in Computer Science (SAGT), vol. 4997 (2008), pp. 327

Greedy list intersection

R. Krauthgamer

V. Raman

A. Rudra

IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008, pp. 1033-1042

Beyond moulin mechanisms

Pricing commodities, or how to sell when buyers have restricted valuations

Is Shapley Cost Sharing Optimal?

A note on approximate Nash equilibria

Inapproximability results for combinatorial auctions with submodular utility functions

Some results on approximating the minimax solution in approval voting

R. LeGrand

E. Markakis

Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems (2007)

Beyond moulin mechanisms

Tim Roughgarden

ACM Conference on Electronic Commerce (2007), pp. 1-10

Progress in approximate Nash equilibria

C. Daskalakis

C. Papadimitriou

Proceedings of the 8th ACM conference on Electronic commerce (2007), pp. 355-358

An auction-based market equilibrium algorithm for a production model

Design is as easy as optimization

D. Chakrabarty

V.V. Vazirani

Lecture Notes In Computer Science (ICALP), vol. 4051 (2006), pp. 477

On earthmover distance, metric labeling, and 0-extension

H. Karloff

S. Khot

Y. Rabani

Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (2006), pp. 547-556

Posted price profit maximization for multicast by approximating fixed points

S. Shenker

V.V. Vazirani

Journal of Algorithms (conference version in Electronic Commerce), vol. 58 (2006), pp. 150-164

Fairness and optimality in congestion games

D. Chakrabarty

V. Nagarajan

Proceedings of the 6th ACM Conference on Electronic Commerce (2005), pp. 52-57

A Simple Characterization for Truth-Revealing Single-Item Auctions

On the fourier spectrum of symmetric boolean functions with applications to learning symmetric juntas

RJ Lipton

E. Markakis

NK Vishnoi

Computational Complexity, 2005. Proceedings. Twentieth Annual IEEE Conference on, pp. 112-119

Learning symmetric k-juntas in time n\^ o (k)

Randomized truthful auctions of digital goods are randomizations over truthful auctions

V.V. Vazirani

Proceedings of the 5th ACM conference on Electronic commerce (2004), pp. 120-124

Playing large games using simple strategies

R.J. Lipton

E. Markakis

Proceedings of the 4th ACM conference on Electronic commerce (2003), pp. 36-41

Randomized time-space tradeoffs for directed graph connectivity

Caching with expiration times

P. Gopalan

H. Karloff

M. Mihail

N. Vishnoi

Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (2002), pp. 540-547

Keeping Track of the Latest Gossip in Shared Memory Systems