# Martin Pál

Martin Pál graduated from Comenius University in Slovakia ("mgr." '00) and Cornell University (PhD '04). He held a postdoc at Rutgers and Bell Labs in '04/'05, and has been working as an engineer at Google since then.

Martin's interests include approximation algorithms, combinatorial optimization, auctions and game theory.

Authored Publications

Google Publications

Other Publications

Sort By

Improved Approximations for Posted Price and Second-price Mechanisms

Hedyeh Beyhaghi

Negin Golrezaei

Operations Research (2020)

Preview abstract
We study the fundamental problem of selling a single indivisible good to one ofnbuyers with independentvaluations. We seek to design improved approximations to the optimal revenue achievable through two simpleand widely used mechanisms: second price auction with eager personalized reserve prices, and sequentialposted price mechanisms. Until recently, the best known approximation for both these mechanisms was 1−1e.We give improved approximations of 1−1e+0.022∼0.6543 for the sequential posted price mechanism and1−1e+0.029∼0.662 for the second price auction with eager reserve prices. We also make some progresstowards the problem of computing the optimal personalized eager reserve prices for a second price auction.
View details

Showing Relevant Ads via Lipschitz Context Multi-Armed Bandits

Tyler Lu

Dávid Pál

Thirteenth International Conference on Artificial Intelligence and Statistics, Journal of Machine Learning Research (2010)

Preview abstract
We study contextual multi-armed bandit problems where the context comes from a metric space and the payoff satisfies a Lipschitz condition with respect to the metric. Abstractly, a contextual multi-armed bandit problem models a situation where, in a sequence of independent trials, an online algorithm chooses, based on a given context (side information), an action from a set of possible actions so as to maximize the total payoff of the chosen actions. The payoff depends on both the action chosen and the context. In contrast, context-free multi-armed bandit problems, a focus of much previous research, model situations where no side information is available and the payoff depends only on the action chosen. Our problem is motivated by sponsored web search, where the task is to display ads to a user of an Internet search engine based on her search query so as to maximize the click-through rate (CTR) of the ads displayed. We cast this problem as a contextual multi-armed bandit problem where queries and ads form metric spaces and the payoff function is Lipschitz with respect to both the metrics. For any $\epsilon > 0$ we present an algorithm with regret $O(T^{\frac{a+b+1}{a+b+2} + \epsilon})$ where $a,b$ are the covering dimensions of the query space and the ad space respectively. We prove a lower bound $\Omega(T^{\frac{\tilde{a}+\tilde{b}+1}{\tilde{a}+\tilde{b}+2} \epsilon})$ for the regret of any algorithm where $\tilde{a}, \tilde{b}$ are packing dimensions of the query spaces and the ad space respectively. For finite spaces or convex bounded subsets of Euclidean spaces, this gives an almost matching upper and lower bound.
View details

Online Ad Assignment with Free Disposal

Preview
S. Muthukrishnan

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

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)

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

Improved Algorithms for Orienteering and Related Problems

Preview
Chandra Chekuri

Proc. 19th Annual Symposium on Discrete Algorithms (SODA), SIAM (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

A Truthful Mechanism for Offline Ad Slot Scheduling

Preview
S. Muthukrishnan

Evdokia Nikolova

Symposium on Algorithmic Game Theory (2008)

Stochastic Models for Budget Optimization in Search-Based Advertising

Preview
S. Muthukrishnan

Internet and Network Economics (WINE), Springer, San Diego (2007), pp. 131-142

Sharing the cost more efficiently: Improved approximation for multicommodity rent-or-buy

Preview
L. Becchetti

J. Könemann

S. Leonardi

ACM Transactions on Algorithms, vol. 3, no 2 (2007), pp. 23

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

Maximizing a Submodular Set Function subject to a Matroid Constraint

Preview
Chandra Chekuri

Gruia Calinescu

Jan Vondrák

Proceedings of the Twelfth Conference on Integer Programming and Combinatorial Optimization (IPCO) 2007

Proportional Fairness in Multi-Rate Wireless LANs