# 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

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

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

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, 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)