Jump to Content
Jon Feldman

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
  • Title
  • Title, desc
  • Year
  • Year, desc
    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
    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
    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
    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
    Florin Constantin
    S. Muthukrishnan
    Fourth Workshop on Ad Auctions; Symposium on Discrete Algorithms (SODA) (2009)
    Preview
    Position Auctions with Bidder-Specific Minimum Prices
    Eyal Even-Dar
    Yishay Mansour
    S. Muthukrishnan
    Fourth Workshop on Ad Auctions; Workshop on Internet and Network Economics (WINE) (2008)
    Preview
    A Truthful Mechanism for Offline Ad Slot Scheduling
    S. Muthukrishnan
    Evdokia Nikolova
    Symposium on Algorithmic Game Theory (2008)
    Preview
    Algorithmic Methods for Sponsored Search Advertising
    S. Muthukrishnan
    Performance Modeling and Engineering (Proc. SIGMETRICS 2008 Tutorial Sessions), Springer, pp. 91-124
    Preview
    Theory research at Google
    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
    Preview
    On Distributing Symmetric Streaming Computations
    S. Muthukrishnan
    Anastasios Sidiropoulos
    Cliff Stein
    Proc. 19th Annual Symposium on Discrete Algorithms (SODA) (2008)
    Preview
    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
    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
    Ryan O'Donnell
    Rocco A. Servedio
    Proc. 19th Annual Conference on Learning Theory (COLT) (2006)
    Preview
    Growth Codes: Maximizing Sensor Network Data Persistence
    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
    Preview
    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
    Guy Even
    Guy Kortsarz
    Zeev Nutov
    ACM Trans. Algorithms, vol. 5 (2009), pp. 1-17
    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
    Ryan O'Donnell
    Rocco A. Servedio
    FOCS (2005), pp. 501-510
    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
    Clifford Stein
    SODA (2005), pp. 460-469
    Decoding turbo-like codes via linear programming
    David R. Karger
    J. Comput. Syst. Sci., vol. 68 (2004), pp. 733-752
    Decoding Turbo-Like Codes via Linear Programming
    David R. Karger
    FOCS (2002), pp. 251-260
    A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set
    Guy Even
    Guy Kortsarz
    Zeev Nutov
    RANDOM-APPROX (2001), pp. 90-101
    Computing an Optimal Orientation of a Balanced Decomposition Tree for Linear Arrangement Problems
    Reuven Bar-Yehuda
    Guy Even
    Joseph Naor
    J. Graph Algorithms Appl., vol. 5 (2001)
    Parallel processor scheduling with delay constraints
    Daniel W. Engels
    David R. Karger
    Matthias Ruhl
    SODA (2001), pp. 577-585
    The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
    Matthias Ruhl
    FOCS (1999), pp. 299-308