Bayesian-robust Algorithms Analysis with Applications in Mechanism Design

Johnsen, Aleck

doi:https://doi.org/10.21985/n2-w786-ex12

Work

Bayesian-robust Algorithms Analysis with Applications in Mechanism Design

Public

Download PDF

Download All Files (.zip)

This thesis studies Bayesian-robustness of algorithm design. The main perspective requires for a single fixed algorithm that its performance is an approximation of the optimal performance when its inputs are independent and identical draws (i.i.d.) from every unknown distribution which is an element of a known, large class of distributions. Formally this information framework is the prior independent setting. Generally this thesis studies design structure that is common to arbitrary algorithms problems for which the prior independent setting is appropriate. The questions addressed by this thesis were largely motivated by questions within mechanism design and thus application of its general results focuses on mechanism design problems. As a major contribution, this thesis gives a method - the Blends Technique - that is agnostic to algorithm problem setting for proving lower bounds on the prior independent approximation factor of any algorithm. The method constructs a correlated distribution over inputs that can be generated both as a distribution over i.i.d. good-for-algorithms distributions and as a distribution over i.i.d. bad-for-algorithms distributions. Prior independent algorithms are upper-bounded by the optimal algorithm for the latter distribution even when the true distribution is the former. Thus, the ratio of the expected performances of the Bayesian optimal algorithms for these two decompositions is a lower bound on the prior independent approximation ratio. The structure of the Blends Technique connects prior independent algorithm design, Yao’s Minimax Principle, information design, tensor decomposition, and benchmark design for the prior free information setting (i.e., worst-case over inputs / competitive analysis). This framework is applied to give novel lower bounds on canonical prior independent mechanism design problems. Another main contribution of this thesis is to use the objective of Bayesian-robustness to inform prior free benchmark design. Benchmarks are free parameters in worst-case algorithm design and choice of benchmark is of critical concern for algorithm analysis. This thesis gives a framework for optimal benchmark design from a requirement that approximation of a prior free benchmark must further hold as a prior independent approximation guarantee. Subsequently, it shows that benchmark design from this framework is equivalent to optimal prior independent algorithm design. This thesis includes the solution to a central open question in prior independent mechanism design, namely it identifies the prior independent revenue-optimal mechanism for selling a single item to two agents with i.i.d. values from a regular distribution. This optimal mechanism is used in the construction of an optimal solution to the corresponding benchmark design problem.

Creator