Algorithms for Social Good in Online Platforms with Guarantees on Honest Participation and Fairness

Abstract

Recent decades have seen a revolution in the way people communicate, buy products, learn new things, and share life experiences. This has spurred the growth of online platforms that enable users from all over the globe to buy/review/recommend products and services, ask questions and provide responses, participate in online learning, etc. There are certain crucial requirements that are required to be satisfied by the online forums for ensuring their trustworthiness and sustainability. In this thesis, we are concerned with three of these requirements: social welfare maximization, honest participation by the users, and fairness in decision making. In particular, we address three contemporary problems in online platforms and obtain principled solutions that achieve social welfare maximization while satisfying honest participation and fairness of allocation. The three problems considered are set in the context of three different platforms: online review or QandA forums, online discussion forums, and online search platforms. In each case, we develop an abstraction of the problem and solve it in its generality. 1) Ballooning Multi-armed Bandits. In our first problem, we consider online platforms where the users are shown user generated content such as reviews on an e-commerce platform or answers on a QandA platform. The number of reviews/answers increases over time. We seek to design an algorithm that quickly learns the best review/best answer and displays it prominently. We model this problem as a novel multi-armed bandit formulation (which we call ballooning bandits) in which the set of arms expands over time. We first show that when the number of arms grows linearly with time, one cannot achieve sub-linear regret. In a realistic special case, where the best answer is likely to arrive early enough, we prove that we can achieve optimal sublinear regret guarantee. We prove our results for best answer arrival time distributions that have sub-exponetal or sub-Pareto tails...