# Jon Feldman

Dr. Feldman graduated from Dartmouth College (BS, 97) and MIT (Ph.D., 03). He was an NSF postdoc at Columbia University before joining as a Research Scientist at Google, NY. His research has been in Algorithms, Coding Theory, and other areas of Theoretical Computer Science. Currently he is working on algorithms and systems for sponsored search advertising at Google.

Authored Publications

Google Publications

Other Publications

Sort By

Multiplicative Bidding in Online Advertising

Sam Chiu-wai Wong

ACM Conference on Economics and Computation (EC) (2014)

Preview abstract
In this paper, we initiate the study of the multiplicative bidding language adopted by major Internet search companies. In multiplicative bidding, the effective bid on a particular search auction is the product of a base bid and bid adjustments that are dependent on features of the search (for example, the geographic location of the user, or the platform on which the search is conducted). We consider the task faced by the advertiser when setting these bid adjustments, and establish a foundational optimization problem that captures the core difficulty of bidding under this language. We give matching algorithmic and approximation hardness results for this problem; these results are against an information-theoretic bound, and thus have implications on the power of the multiplicative bidding language itself. Inspired by empirical studies of search engine price data, we then codify the relevant restrictions of the problem, and give further algorithmic and hardness results. Our main technical contribution is an O(log n)-approximation for the case of multiplicative prices and monotone values. We also provide empirical validations of our problem restrictions, and test our algorithms on real data against natural benchmarks. Our experiments show that they perform favorably compare with the baseline.
View details

Reduce and aggregate: similarity ranking in multi-categorical bipartite graphs

Stefano Leonardi

WWW (2014), pp. 349-360

Preview abstract
We study the problem of computing similarity rankings in large-scale multi-categorical bipartite graphs, where the two sides of the graph represent actors and items, and the items are partitioned into an arbitrary set of categories. The problem has several real-world applications, including identifying competing advertisers and suggesting related queries in an online advertising system or finding users with similar interests and suggesting content to them. In these settings, we are interested in computing on-the-fly rankings of similar actors, given an actor and an arbitrary subset of categories of interest. Two main challenges arise: First, the bipartite graphs are huge and often lopsided (e.g. the system might receive billions of queries while presenting only millions of advertisers). Second, the sheer number of possible combinations of categories prevents the pre-computation of the results for all of them. We present a novel algorithmic framework that addresses both issues for the computation of several graph-theoretical similarity measures, including # common neighbors, and Personalized PageRank. We show how to tackle the imbalance in the graphs to speed up the computation and provide efficient real-time algorithms for computing rankings for an arbitrary subset of categories. Finally, we show experimentally the accuracy of our approach with real-world data, using both public graphs and a very large dataset from Google AdWords.
View details

Yield Optimization of Display Advertising with Ad Exchange

S. Muthukrishnan

ACM Conference on Electronic Commerce (2011)

Preview abstract
In light of the growing market of Ad Exchanges for the real-time sale of advertising slots, publishers face new challenges in choosing between the allocation of contract-based reservation ads and spot market ads. In this setting, the publisher should take into account the tradeoff between short-term revenue from an Ad Exchange and quality of allocating reservation ads. In this paper, we formalize this combined optimization problem as a stochastic control problem and derive an efficient policy for online ad allocation in settings with general joint distribution over placement quality and exchange bids. We prove asymptotic optimality of this policy in terms of any trade-off between quality of delivered reservation ads and revenue from the exchange, and provide a rigorous bound for its convergence rate to the optimal policy. We also give experimental results on data derived from real publisher inventory, showing that our policy can achieve any pareto-optimal point on the quality vs. revenue curve. Finally, we study a parametric training-based algorithm in which instead of learning the dual variables from a sample data (as is done in non-parametric training-based algorithms), we learn the parameters of the distribution and construct those dual variables from the learned parameter values. We compare parametric and non-parametric ways to estimate from data both analytically and experimentally in the special case without the ad exchange, and show that though both methods converge to the optimal policy as the sample size grows, our parametric method converges faster, and thus performs better on smaller samples.
View details

Online Stochastic Packing Applied to Display Ad Allocation

Monika Henzinger

Clifford Stein

ESA (1) (2010), pp. 182-194

Preview abstract
Inspired by online ad allocation, we study online stochastic packing integer programs from theoretical and practical standpoints. We first present a near-optimal online algorithm for a general class of packing integer programs which model various online resource allocation problems including online variants of routing, ad allocations, generalized assignment, and combinatorial auctions. As our main theoretical result, we prove that a simple dual training-based algorithm achieves a (1 − o(1))-approximation guarantee in the random order stochastic model. This is a significant improvement over logarithmic or constant-factor approximations for the adversarial variants of the same problems (e.g. factor 1−1e1−1e for online ad allocation, and log(m) for online routing). We then focus on the online display ad allocation problem and study the efficiency and fairness of various training-based and online allocation algorithms on data sets collected from real-life display ad allocation system. Our experimental evaluation confirms the effectiveness of training-based algorithms on real data sets, and also indicates an intrinsic trade-off between fairness and efficiency.
View details

Auctions with intermediaries: extended abstract

S. Muthukrishnan

Mallesh M. Pai

ACM Conference on Electronic Commerce (2010), pp. 23-32

Preview abstract
Inspired by online advertisement exchange systems, we study a setting where potential buyers of a unique, indivisible good attempt to purchase from a central seller via a set of intermediaries. Each intermediary has captive buyers, and runs an auction for a 'contingent' good. Based on the outcome, the intermediary bids in a subsequent upstream auction run by the seller. In this paper, we study the equilibria and incentives of intermediaries and the central seller.
We find that combining the notion of optimal auction design with the double-marginalization arising from the presence of intermediaries yields new strategic elements not present in either setting individually: we show that in equilibrium, revenue-maximizing intermediaries will use an auction with a randomized reserve price chosen from an interval. We characterize the interval and the probability distribution from which this reserve price is chosen as a function of the distribution of buyers' types. Furthermore, we characterize the revenue maximizing auction for the central seller by taking into account the effect of his choice of mechanism on the mechanisms offered by the intermediaries. We find that the optimal reserve price offered by the seller decreases with the number of buyers (but remains strictly positive); in contrast to the classical optimal auction without intermediaries, where the reserve price is independent of the number of buyers.
View details

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

An Online Mechanism for Ad Slot Reservations with Cancellations

Preview
Florin Constantin

S. Muthukrishnan

Fourth Workshop on Ad Auctions; Symposium on Discrete Algorithms (SODA) (2009)

Online Ad Assignment with Free Disposal

Preview
S. Muthukrishnan

Workshop of Internet Economics (WINE) (2009), pp. 374-385

Position Auctions with Bidder-Specific Minimum Prices

Preview
Eyal Even-Dar

Yishay Mansour

S. Muthukrishnan

Fourth Workshop on Ad Auctions; Workshop on Internet and Network Economics (WINE) (2008)

A Truthful Mechanism for Offline Ad Slot Scheduling

Preview
S. Muthukrishnan

Evdokia Nikolova

Symposium on Algorithmic Game Theory (2008)

Algorithmic Methods for Sponsored Search Advertising

Preview
S. Muthukrishnan

Performance Modeling and Engineering (Proc. SIGMETRICS 2008 Tutorial Sessions), Springer, pp. 91-124

Theory research at Google

Preview
Nir Ailon

Florin Constantin

Eyal Even-Dar

Gereon Frahling

Monika R. Henzinger

S. Muthukrishnan

Noam Nisan

Anastasios Sidiropoulos

SIGACT News, vol. 39 (2008), pp. 10-28

On Distributing Symmetric Streaming Computations

Preview
S. Muthukrishnan

Anastasios Sidiropoulos

Cliff Stein

Proc. 19th Annual Symposium on Discrete Algorithms (SODA) (2008)

Sponsored Search Auctions for Markovian Users

S. Muthukrishnan

Fourth Workshop on Ad Auctions; Workshop on Internet and Network Economics (WINE). (2008)

Preview abstract
Sponsored search involves running an auction among advertisers who bid in order to have their ad shown next to search results for specific keywords. The most popular auction for sponsored search is the “Generalized Second Price” (GSP) auction where advertisers are assigned to slots in the decreasing order of their score, which is defined as the product of their bid and click-through rate. One of the main advantages of this simple ranking is that bidding strategy is intuitive: to move up to a more prominent slot on the results page, bid more. This makes it simple for advertisers to strategize. However this ranking only maximizes efficiency under the assumption that the probability of a user clicking on an ad is independent of the other ads shown on the page. We study a Markovian user model that does not make this assumption. Under this model, the most efficient assignment is no longer a simple ranking function as in GSP. We show that the optimal assignment can be found efficiently (even in near-linear time). As a result of the more sophisticated structure of the optimal assignment, bidding dynamics become more complex: indeed it is no longer clear that bidding more moves one higher on the page. Our main technical result is that despite the added complexity of the bidding dynamics, the optimal assignment has the property that ad position is still monotone in bid. Thus even in this richer user model, our mechanism retains the core bidding dynamics of the GSP auction that make it useful for advertisers.
View details

Budget Optimization in Search-Based Advertising Auctions

S. Muthukrishnan

Cliff Stein

Proc. ACM Conference on Electronic Commerce, ACM, San Diego (2007)

Preview abstract
Internet search companies sell advertisement slots based on users' search queries via an auction. While there has been previous work onthe auction process and its game-theoretic aspects, most of it focuses on the Internet company. In this work, we focus on the advertisers, who must solve a complex optimization problem to decide how to place bids on keywords to maximize their return (the number of user clicks on their ads) for a given budget. We model the entire process and study this budget optimization problem. While most variants are NP-hard, we show, perhaps surprisingly, that simply randomizing between two uniform strategies that bid equally on all the keywordsworks well. More precisely, this strategy gets at least a 1-1/ε fraction of the maximum clicks possible. As our preliminary experiments show, such uniform strategies are likely to be practical. We also present inapproximability results, and optimal algorithms for variants of the budget optimization problem.
View details

Using Many Machines to Handle an Enormous Error-Correcting Code

Preview
Proc. IEEE Information Theory Workshop (ITW) (2006)

Bidding to the Top: VCG and Equilibria of Position-Based Auctions

S. Muthukrishnan

Proceedings of the Fourth Workshop on Approximation and Online Algorithms (WAOA) (2006)

Preview abstract
Many popular search engines run an auction to determine the placement of advertisements next to search results. Current auctions at Google and Yahoo! let advertisers specify a single amount as their bid in the auction. This bid is interpreted as the maximum amount the advertiser is willing to pay per click on its ad. When search queries arrive, the bids are used to rank the ads linearly on the search result page. Advertisers seek to be high on the list, as this attracts more attention and more clicks. The advertisers pay for each user who clicks on their ad, and the amount charged depends on the bids of all the advertisers participating in the auction.
We study the problem of ranking ads and associated pricing mechanisms when the advertisers not only specify a bid, but additionally express their preference for positions in the list of ads. In particular, we study prefix position auctions where advertiser i can specify that she is interested only in the top κi positions.
We present a simple allocation and pricing mechanism that generalizes the desirable properties of current auctions that do not have position constraints. In addition, we show that our auction has an envy-free or symmetric Nash equilibrium with the same outcome in allocation and pricing as the well-known truthful Vickrey-Clarke-Groves (VCG) auction. Furthermore, we show that this equilibrium is the best such equilibrium for the advertisers in terms of the profit made by each advertiser. We also discuss other position-based auctions.
View details

PAC Learning Mixtures of Gaussians with No Separation Assumption

Preview
Ryan O'Donnell

Rocco A. Servedio

Proc. 19th Annual Conference on Learning Theory (COLT) (2006)

Growth Codes: Maximizing Sensor Network Data Persistence

Preview
Abhinav Kamra

Vishal Misra

Dan Rubenstein

Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, ACM, Pisa, Italy, pp. 255-266

Online Stochastic Ad Allocation: Efficiency and Fairness

Monika Henzinger

Clifford Stein

CoRR, vol. abs/1001.5076 (2010)

A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2

Using linear programming to Decode Binary linear codes

Martin J. Wainwright

David R. Karger

IEEE Transactions on Information Theory, vol. 51 (2005), pp. 954-972

Learning mixtures of product distributions over discrete domains

Data persistence in sensor networks: towards optimal encoding for data recovery in partial network failures

Abhinav Kamra

Vishal Misra

Dan Rubenstein

SIGMETRICS Performance Evaluation Review, vol. 33 (2005), pp. 24-26

LP decoding achieves capacity

Decoding turbo-like codes via linear programming

Decoding Turbo-Like Codes via Linear Programming

Computing an Optimal Orientation of a Balanced Decomposition Tree for Linear Arrangement Problems

Parallel processor scheduling with delay constraints

The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals