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 Q&A 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 Q&A 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.

2) Strategy-proof Allocation of Indivisible Goods with Fairness Guarantees.

Second, we consider the problem of fairness in online search platforms. We view the sponsored ad-slots on these platforms as indivisible goods to be allocated in a fair manner among competing advertisers. We use envy-freeness up to one good (EF1) and maximin fair share (MMS) allocation as the fairness notions. The problem is to maximize the overall social welfare subject to these fairness constraints. We first prove under a single parameter setting that the problem of social welfare maximization under EF1 is NP-hard. We complement this result by showing that any EF1 allocation satisfies an 1/2-approximation guarantee and present an algorithm with a (1, 1/2) bi-criteria approximation guarantee. We finally show in a strategic setting that one can design a truthful mechanism with the proposed fair allocation.

3) Coalition Resistant Credit Score Functions.

In the third problem, we study manipulation in online discussion forums. We consider a specific but a common form of manipulation namely manipulation by coalition formation. We design a manipulation resistant credit scoring rule that assigns to each user a score such that forming a coalition is discouraged. In particular, we study the graph generated by the interactions on the platform and use community detection algorithms. We show that the community scores given by community detection algorithms that maximize modularity lead to a coalition resistant credit scoring rule. This in turn leads to sustainable discussion forums with honest participation from users, devoid of any coalitional manipulation.