PhD Proposal: The power of stochastic modeling, beating theoretically proven lower bounds of optimization problems

Several optimization problems have been studied in the literature of game theory, online algorithms, mechanism design, and economics, most of which are motivated by their vast applications in real world or their applicability to other theoretical problems. In all of these problems, the goal is to design either an algorithm or a mechanism that guarantees the highest performance in the worst case scenarios. In many cases, this is achieved by taking a significant hit on the average outcome of the algorithm. In real world, however, adversarial scenarios are not always the case. Therefore, a new line of research is necessary to study these optimization problems with a more realistic setting. An effective and fruitful means to rule out unlikely scenarios is limiting the uncertain parameters of the problem by adding stochastic assumptions. This has been applied to many problems in different areas with names such as ``Bayesian setting", ``Prophet inequality", etc.
In this work we revisit well-known and classical problems in game theory, mechanism design, social networks, economics, and online algorithms in stochastic settings. Some of these problems have been posed in previous works and were left as open questions. For all of these problems we propose mechanisms/algorithms that are almost optimal with respect to the stochastic inputs, i.e., no other mechanism/algorithm can achieve a relatively higher performance unless either a constraint of the problem is violated or a widely believed conjecture fails. We show that we can beat the theoretically proved lower bounds for general problems by considering the stochastic inputs. As an example, the currently known lower bound on the competitive ratio of the the $k$-server problem is $k$, whereas we prove logarithmically small (and even constant in some cases) upper bounds on the approximation ratio of our algorithm for the stochastic version of the problem.
Examining Committee:
Dr. Mohammad Taghi Hajiaghayi, Chair
Dr. VS Subrahmanian, Dept. Representative
Dr. Samir Khuller, Committee Member
Dr. Brendan Lucier, Committee Member