2019-12-26 | Yingkai Li: Benchmark Design and Prior-independent Optimization
We compare two leading approaches for robust optimization in the models of online algorithms and mechanism design. Competitive analysis compares the performance of an online algorithm to an offline benchmark in worst-case over inputs, and prior-independent mechanism design compares the expected performance of a mechanism on an unknown distribution (of inputs, i.e., agent values) to the optimal mechanism for the distribution in worst case over distributions. For competitive analysis, a critical concern is the choice of benchmark. We give a method for selecting a good benchmark. We show that optimal algorithm/mechanism for the optimal benchmark are equal to the prior-independent optimal algorithm/mechanism.
We solve a central open question in prior-independent mechanism design, namely we identify the prior-independent revenue-optimal mechanism for selling a single item to two agents with i.i.d. and regularly distributed values. Via this solution and the above equivalence of prior-independent mechanism design and competitive analysis (a.k.a. prior-free mechanism design) we show that the standard method for lower bounds of prior-free mechanisms is not generally tight for the benchmark design program. (Joint work with Aleck Johnsen and Jason Hartline.)
Yingkai Li is a second year PhD student at the Department of Computer Science, Northwestern University under the supervision of Prof. Jason Hartline. He received his BS in Computer Science from Shanghai Jiaotong University in 2015 and MS in Computer Science from Stony Brook University in 2018.
His research lies in the intersection of computer science and economics, with the focus on mechanism design and online algorithms.