本周日（3月27日）下午15:00，学堂112，吴瑾昭、闫书弈学长会分享自己的工作，时长约为一到两小时。
本次seminar是和北大信科peer talk合办的。
吴瑾昭：Learning Bilateral Trade from Finite Samples
吴瑾昭是北大图灵班2018级本科生，本次seminar他将会介绍他在机制设计方面的工作。
We study the problem of approximating social welfare in bilateral trade using a finite number of samples. The seminal result of Myerson(1983) shows that no Bayesian incentive compatible, individually rational, and budget balance mechanism can achieve the optimal social welfare even in bilateral trade, arguably the simplest two-sided market, where a seller is selling an item to a buyer. Recent results show that one can already obtain a constant factor approximation to the optimal welfare using a single sample from the seller’s distribution. In this paper, our goal is to understand what approximation ratios are possible if the designer has more than one but still finitely many samples. This is usually a technically more challenging regime. We propose a new family of mechanisms that we refer to as the “order statistic mechanisms” and provide a complete characterization of their approximation ratios for any fixed number of samples. Using the characterization, we numerically compute the approximation ratios obtained by the optimal order statistic mechanism for small sample sizes (no more than 10 samples), and observe that they significantly outperform the single sample mechanism.
闫书弈：The Power of Multiple Choices in Online Stochastic Matching
闫书弈是姚班2018级（计科80）本科生。本次seminar他将会介绍他在在线匹配问题上的研究。
Online stochastic matching is a model in which we know an i.i.d. distribution for online vertices and need to match each online vertex immediately and irrevocably. Despite a long line of research, existing algorithms still only consider two choices of offline neighbors for each online vertex because of the technical challenge in analyzing multiple choices. We introduce two approaches for designing and analyzing algorithms that use multiple choices. For unweighted and vertex-weighted matching, we adopt the online correlated selection (OCS) technique into the stochastic setting. For edge-weighted matching with free disposal, We directly characterize the progress of the whole matching instead of individual vertices, through a differential inequality.
Make IIIS Great Again!
