Existing approaches to fairness in stochastic multi-armed bandits (MAB) primarily focus on exposure guarantee to individual arms. When arms are naturally grouped by certain attribute(s), we propose Bi-Level Fairness, which considers two levels of fairness. At the first level, Bi-Level Fairness guarantees a certain minimum exposure to each group. To address the unbalanced allocation of pulls to individual arms within a group, we consider meritocratic fairness at the second level, which ensures that each arm is pulled according to its merit within the group. Our work shows that we can adapt a UCB-based algorithm to achieve a Bi-Level Fairness by providing (i) anytime Group Exposure Fairness guarantees and (ii) ensuring individual-level Meritocratic Fairness within each group. We first show that one can decompose regret bounds into two components: (a) regret due to anytime group exposure fairness and (b) regret due to meritocratic fairness within each group. Our proposed algorithm BF-UCB balances these two regrets optimally to achieve the upper bound of $O(\sqrt{T})$ on regret; $T$ being the stopping time. With the help of simulated experiments, we further show that BF-UCB achieves sub-linear regret; provides better group and individual exposure guarantees compared to existing algorithms; and does not result in a significant drop in reward with respect to UCB algorithm, which does not impose any fairness constraint.

We consider a two-player resource allocation polytope game, in which the strategy of a player is restricted by the strategy of the other player, with common coupled constraints. With respect to such a game, we formally introduce the notions of independent optimal strategy profile, which is the profile when players play optimally in the absence of the other player; and common contiguous set, which is the set of top nodes in the preference orderings of both the players that are exhaustively invested on in the independent optimal strategy profile. We show that for the game to have a unique PSNE, it is a necessary and sufficient condition that the independent optimal strategies of the players do not conflict, and either the common contiguous set consists of at most one node or all the nodes in the common contiguous set are invested on by only one player in the independent optimal strategy profile. We further derive a socially optimal strategy profile, and show that the price of anarchy cannot be bound by a common universal constant. We hence present an efficient algorithm to compute the price of anarchy and the price of stability, given an instance of the game. Under reasonable conditions, we show that the price of stability is 1. We encounter a paradox in this game that higher budgets may lead to worse outcomes.

In social choice theory, preference aggregation refers to computing an aggregate preference over a set of alternatives given individual preferences of all the agents. In real-world scenarios, it may not be feasible to gather preferences from all the agents. Moreover, determining the aggregate preference is computationally intensive. In this paper, we show that the aggregate preference of the agents in a social network can be computed efficiently and with sufficient accuracy using preferences elicited from a small subset of critical nodes in the network. Our methodology uses a model developed based on real-world data obtained using a survey on human subjects, and exploits network structure and homophily of relationships. Our approach guarantees good performance for aggregation rules that satisfy a property which we call expected weak insensitivity. We demonstrate empirically that many practically relevant aggregation rules satisfy this property. We also show that two natural objective functions in this context satisfy certain properties, which makes our methodology attractive for scalable preference aggregation over large scale social networks. We conclude that our approach is superior to random polling while aggregating preferences related to individualistic metrics, whereas random polling is acceptable in the case of social metrics.