Gagan Aggarwal
Research Areas
Authored Publications
Sort By
Online Advertising with Spatial Interactions
Yifan Wang
Mingfei Zhao
Proceedings of the ACM Web Conference 2026, Association for Computing Machinery, New York, NY, USA, 213–224
Preview abstract
Online advertising platforms must decide how to allocate multiple ads across limited screen real estate, where each ad's effectiveness depends not only on its own placement but also on nearby ads competing for user attention. Such spatial externalities — arising from proximity, clutter, or crowding — can significantly alter welfare and revenue outcomes, yet existing auction and allocation models typically treat ad slots as independent or ordered along a single dimension. We introduce a new framework for spatial externalities in online advertising, in which the value of an ad depends on both its slot and the configuration of surrounding ads. We model ad slots as points in a metric space, and model an advertiser's value as a function of both their bid and a discount factor determined by the configuration of other displayed ads.
Within this framework, we analyze two natural models. For the Nearest-Neighbor model, where the value suppression depends only on the closest neighboring ad, we present a polynomial-time algorithm that achieves a constant approximation for the general case. We show that the allocation rule is monotone and can be implemented as a truthful mechanism. For a structured setting of 2D Euclidean space, we provide a PTAS. In contrast, for the Product-Distance model, where interference is aggregated multiplicatively across all neighbors, we establish a strong (and nearly-tight) hardness of approximation -- no polynomial-time algorithm can achieve any polynomial-factor approximation unless P=NP, via a reduction from Max-Independent-Set. Our results provide a foundation for reasoning about spatial externalities in ad allocation and for designing efficient, truthful mechanisms under such interactions.
View details
Platform Competition in the Autobidding World
Ariel Schvartzman
Andres Perlroth
Mingfei Zhao
Proceedings of the ACM Web Conference 2026, Association for Computing Machinery, New York, NY, USA, 87–98
Preview abstract
We study the problem of auction design for advertising platforms that face strategic advertisers who are bidding across platforms. Each advertiser's goal is to maximize their total value or conversions while satisfying some constraint(s) across all the platforms they participates in. In this paper, we focus on advertisers with return-over-investment (henceforth, ROI) constraints, i.e. each advertiser is trying to maximize value while making sure that their ROI across all platforms is no less than some target value. An advertiser interacts with the platforms through autobidders -- for each platform, the advertiser strategically chooses a target ROI to report to the platform's autobidder, which in turn uses a uniform bid multiplier to bid on the advertiser's behalf on the queries owned by the given platform.
Our main result is an auction comparator theorem that can be used to choose between different auction mechanisms by a revenue-maximizing platform operating in a competitive environment. Analogous to the Linkage Principle for interdependent values, our comparator demonstrates that, for a broad class of advertiser valuations, second-price auctions may sometimes generate higher revenue than first-price auctions. This contrasts sharply with the single-platform setting, where first-price auctions are optimal for both revenue and welfare. Our findings highlight the critical importance of considering inter-platform competition when designing optimal auctions.
View details
Mechanism Design for Delagated Resource Allocation
Marios Mertzanidis
Alex Psomas
The 20th Conference on Web and Internet Economics (2024)
Preview abstract
We study delegation in resource allocation. Specifically, we study a problem in which agents do not participate directly in a mechanism. Instead, each agent has a representative (who represents potentially many agents) that participates in the mechanism on their behalf. The mechanism decides on an allocation of items for each representative, which the representative then splits among the agents it represents in a way that maximizes some p-mean objective (e.g., maximizes the minimum utility/egalitarian welfare, the social welfare, or the geometric mean/Nash welfare). We are motivated by numerous real-world scenarios, e.g., how Feeding America allocates food to food-insecure individuals, where the representatives are the food banks, bidding in Feeding America's so-called Choice System.
Our contribution: We focus on the case where the mechanism is an auction with artificial currency, and the amount of currency each representative gets is proportional to the number of agents it represents. We analyze the behavior of each auction at the worst-case Nash equilibrium, with respect to the optimal (global) p-mean objective.
We prove that the trading post mechanism, which fractionally splits each item j among the agents that bid for it in a proportional manner, coupled with an all-pay payment rule, achieves a good price of anarchy, under a low-rank/incoherence assumption, for all p-mean objectives simultaneously (Thm 1). For the notable case of Nash welfare, the low-rank/incoherence assumption is not necessary. However, for the case of egalitarian welfare and social welfare, we prove that the low-rank/incoherence assumption is necessary (Thm 2). Next, we show that the first price auction, a very popular auction format, and the current auction Feeding America runs, has a terrible price of anarchy, even with the aforementioned incoherence assumption, for all p-mean objectives (Thm 3).
View details
Auto-bidding and Auctions in Online Advertising: A Survey
Ashwinkumar Badanidiyuru Varadaraja
Christopher Liaw
Haihao (Sean) Lu
Andres Perlroth
Georgios Piliouras
Ariel Schvartzman
Kelly Spendlove
Hanrui Zhang
Mingfei Zhao
Wennan Zhu
ACM SIGecom Exchanges, 22 (2024)
Preview abstract
In this survey, we summarize recent developments in research fueled by the growing adoption of automated bidding strategies in online advertising. We explore the challenges and opportunities that have arisen as markets embrace this autobidding and cover a range of topics in this area, including bidding algorithms, equilibrium analysis and efficiency of common auction formats, and optimal auction design.
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
Preview abstract
Autobidding is becoming increasingly important in the domain of online advertising, and has become a critical tool used by many advertisers for optimizing their ad campaigns. We formulate fundamental questions around the problem of bidding for performance under very general affine cost constraints. We design optimal single-agent bidding strategies for the general bidding problem, in multi-slot truthful auctions. We show that there is an intimate connection between bidding and auction design, in that the bidding formula is optimal if and only if the underlying auction is truthful. We show how a MWU algorithm can be used to learn this optimal bidding formula.
Next, we move from the single-agent view to taking a full-system view: What happens when all advertisers adopt optimal autobidding? We prove that in general settings, there exists an equilibrium between the bidding agents for all the advertisers. Further, we prove a Price of Anarchy result: For the general affine constraints, the total value (conversions) obtained by the advertisers in the bidding agent equilibrium is no less than 1/2 of what we could generate via a centralized ad allocation scheme, one which does not consider any auction incentives or provide any per-advertiser guarantee.
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
Online Selection of Diverse Results
Debmalya Panigrahi
Atish Das Sarma
Proceedings of the 5th ACM international Conference on Web Search and Data Mining (2012), pp. 263-272
Preview abstract
The phenomenal growth in the volume of easily accessible information via various web-based services has made it essential for service providers to provide users with personalized representative summaries of such information. Further, online commercial services including social networking and micro-blogging websites, e-commerce portals, leisure and entertainment websites, etc. recommend interesting content to users that is simultaneously diverse on many different axes such as topic, geographic specificity, etc.
The key algorithmic question in all these applications is the generation of a succinct, representative, and relevant summary from a large stream of data coming from a variety of sources. In this paper, we formally model this optimization problem, identify its key structural characteristics, and use these observations to design an extremely scalable and efficient algorithm. We analyze the algorithm using theoretical techniques to show that it always produces a nearly optimal solution. In addition, we perform large-scale experiments on both real-world and synthetically generated datasets, which confirm that our algorithm performs even better than its analytical guarantees in practice, and also outperforms other candidate algorithms for the problem by a wide margin.
View details
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 first 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
Achieving anonymity via clustering
Tomás Feder
Krishnaram Kenthapadi
Samir Khuller
Rina Panigrahy
Dilys Thomas
An Zhu
ACM Transactions on Algorithms, 6 (2010), 49:1-49:19
Preview abstract
Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of
de-identifying records is to remove identifying fields such as social security number, name etc. However, recent research has shown that a large fraction of the US population can be
identified using non-key attributes (called quasi-identifiers) such as date of birth, gender, and zip code. Sweeney proposed the k-anonymity model for privacy where non-key
attributes that leak information are suppressed or generalized so that, for every record in the modified table, there are at least k−1 other records having exactly the same values for
quasi-identifiers. We propose a new method for anonymizing data records, where quasi-identifiers of data records are first clustered and then cluster centers are published. To
ensure privacy of the data records, we impose the constraint that each cluster must contain no fewer than a pre-specified number of data records. This technique is more general since we have a much larger choice for cluster centers than k-Anonymity. In many cases, it lets us release a lot more information without compromising privacy. We also provide constant-factor approximation algorithms to come up with such a clustering. This is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k. We further observe that a few outlier points can significantly increase the cost of anonymization. Hence, we extend our algorithms to allow an epsilon fraction of points to remain unclustered, i.e., deleted from the anonymized publication. Thus, by not releasing a small fraction of the database records, we can ensure that the data published for analysis has less distortion and hence is more useful. Our approximation algorithms for new clustering objectives are of independent interest and could be applicable in other clustering scenarios as well.
View details
