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
Preview abstract
We study the question of setting and testing reserve prices in single item auctions when the bidders are not identical. At a high level, there are two generalizations of the standard second price auction: in the lazy version we first determine the winner, and then apply reserve prices; in the eager version we first discard the bidders not meeting their reserves, and then determine the winner among the rest. We show that the two versions have dramatically different properties: lazy reserves are easy to optimize, and A/B test in production, whereas eager reserves always lead to higher welfare, but their optimization is NP-complete, and naive A/B testing will lead to incorrect conclusions. Despite their different characteristics, we show that the overall revenue for the two scenarios is always within a factor of 2 of each other, even in the presence of correlated bids. Moreover, we prove that the eager auction dominates the lazy auction on revenue whenever the bidders are independent or symmetric. We complement our theoretical results with simulations on real world data that show that even suboptimally set eager reserve prices are preferred from a revenue standpoint.
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)
Preview abstract
We examine several online matching problems, with applications to Internet advertising reservation systems. Consider an edge-weighted bipartite graph G, with partite sets L, R. We develop an 8-competitive algorithm for the following secretary problem: Initially given R, and the size of L, the algorithm receives the vertices of L sequentially, in a random order. When a vertex l \in L is seen, all edges incident to l are revealed, together with their weights. The algorithm must immediately either match l to an available vertex of R, or decide that l will remain unmatched.
Dimitrov and Plaxton show a 16-competitive algorithm for the transversal matroid secretary problem, which is the special case with weights on vertices, not edges. (Equivalently, one may assume that for each l \in L, the weights on all edges incident to l are identical.) We use a similar algorithm, but simplify and improve the analysis to obtain a better competitive ratio for the more general problem. Perhaps of more interest is the fact that our analysis is easily extended to obtain competitive algorithms for similar problems, such as to find disjoint sets of edges in hypergraphs where edges arrive online. We also introduce secretary problems with adversarially chosen groups. Finally, we give a 2e-competitive algorithm for the secretary problem on graphic matroids, where, with edges appearing online, the goal is to find a maximum-weight acyclic subgraph of a given graph.
View details
Online Ad Assignment with Free Disposal
Preview
S. Muthukrishnan
Workshop of Internet Economics (WINE) (2009), pp. 374-385
Preview abstract
In sponsored search, a number of advertising slots is available on a search results page, and have to be allocated among a set of advertisers competing to display an ad on the page. This gives rise to a bipartite matching market that is typically cleared by the way of
an automated auction. Several auction mechanisms have been proposed, with variants of the Generalized Second Price (GSP) being widely used in practice.
There is a rich body of work on bipartite matching markets that builds upon the stable marriage model of Gale and Shapley and the assignment model of Shapley and Shubik. This line of research offers deep insights into the structure of stable outcomes in such
markets and their incentive properties.
In this paper, we model advertising auctions in terms of an assignment model with linear utilities, extended with bidder and item specific maximum and minimum prices. Auction mechanisms like the commonly used GSP or the well-known Vickrey-Clarke-Groves (VCG) can be interpreted as simply computing a bidder-optimal stable matching in this model, for a suitably defined set of bidder preferences, but our model includes much richer bidders and preferences. We prove that in our model the existence of a stable matching is guaranteed, and under a non-degeneracy assumption a bidder-optimal stable matching exists as well. We give an algorithm to find such matching in polynomial time, and use it to design truthful mechanism that generalizes GSP, is truthful for profit-maximizing bidders, correctly implements features like bidder-specific minimum prices and position-specific bids, and works for rich mixtures of bidders and preferences. Our main technical contributions are the existence of bidder-optimal matchings and strategyproofness of the resulting mechanism, and are proved by induction on the progress of the matching algorithm.
View details
Improved Algorithms for Orienteering and Related Problems
Preview
Chandra Chekuri
Proc. 19th Annual Symposium on Discrete Algorithms (SODA), SIAM (2008)
A Truthful Mechanism for Offline Ad Slot Scheduling
Preview
S. Muthukrishnan
Evdokia Nikolova
Symposium on Algorithmic Game Theory (2008)
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
