We study the problem of multi-dimensional revenue maximization when selling $m$ items to a buyer that has additive valuations for them, drawn from a (possibly correlated) prior distribution. Unlike traditional Bayesian auction design, we assume that the seller has a very restricted knowledge of this prior: they only know the mean $\mu_j$ and an upper bound $\sigma_j$ on the standard deviation of each item's marginal distribution. Our goal is to design mechanisms that achieve good revenue against an ideal optimal auction that has full knowledge of the distribution in advance. We show that selling the items via separate price lotteries achieves an $O(\log r)$ approximation ratio where $r=\max_j(\sigma_j/\mu_j)$ is the maximum coefficient of variation across the items. If forced to restrict ourselves to deterministic mechanisms, this guarantee degrades to $O(r^2)$. Assuming independence of the item valuations, these ratios can be further improved by pricing the full bundle. We demonstrate the optimality of the above mechanisms by providing matching lower bounds. Our tight analysis for the deterministic case resolves an open gap from the work of Azar and Micali [ITCS'13]. As a by-product, we also show how one can directly use our upper bounds to improve and extend previous results related to the parametric auctions of Azar et al. [SODA'13]. This talk is based on joint work with Yiannis Giannakopoulos and Alexandros Tsigonias-Dimitriadis.

face  Speaker: Diogo Poças  

Biografia: Diogo Poças did his MSc in Mathematics and Applications at Instituto Superior Técnico. He then went to McMaster University to pursue a PhD in Mathematics with Prof. Jeffery Zucker, on the topic of analog computing. Since January 2018, Diogo has been a postdoctoral research at TU Munich, specifically in the Operations Research Group, led by Prof. Andreas S. Schulz. His research interests are on theoretical computer science, at the intersection of mathematics and general computer science. Recently, he has been working in algorithmic game theory topics such as: the design of simple and efficient auction selling mechanisms; and the existence and computational complexity of finding Nash equilibria in games. Personal webpage: https://diogopocas1991.gitlab.io