Online matching and resource allocation under stochasticity

Abstract

In this dynamic world, optimization problems in real-life scenarios often need to consider the uncertainty of what will happen in the future and give immediate feedback to enormous queries without any information of future timespan. Research on online algorithms rises from these real-life applications, in which two problems lie in the center of the literature: online bipartite matching and online resource allocation. Moreover, the problem may also be stochastic, leading to increased difficulty to capture the whole picture. In this thesis, we study the online matching and resource allocation under stochasticity, specifically, online stochastic matching and online maximization of Nash social welfare without predictions. In the online stochastic matching part, we propose a new Poisson arrival model that removes the dependency between different types of online vertices, also asymptotically equivalent to the original one. Based on this model, we first go further in pair sampling and improve the performance in unweighted and vertex-weighted cases. We also propose algorithms that consider all unmatched neighbors upon arrival of each online vertex, as well as a new whole-match analysis framework via differential inequality. In the online Nash social welfare maximization part, previous works requires fairly accurate predictions on monopoly utilities of each agent. We remove these predictions and parametrize the instance by balance ratio and impartiality ratio. We give online algorithms whose competitive ratios are logarithmic in the aforementioned ratios of agents’ utilities and the number of agents.