Fair Algorithms for Multi-Agent Multi-Armed Bandits
We propose a multi-agent variant of the classical multi-armed bandit problem, in which there are $N$ agents and $K$ arms, and pulling an arm generates a (possibly different) stochastic reward for each agent. Unlike the classical multi-armed bandit problem, the goal is not to learn the "best arm"; indeed, each agent may perceive a different arm to be the best for her personally. Instead, we seek to learn a fair distribution over the arms. Drawing on a long line of research in economics and computer science, we use the Nash social welfare as our notion of fairness. We design multi-agent variants of three classic multi-armed bandit algorithms and show that they achieve sublinear regret, which is now measured in terms of the lost Nash social welfare.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessMulti-Armed BanditsSimilar Papers 제목 키워드 기반
Multi-agent Multi-armed Bandits with Minimum Reward Guarantee Fairness
We investigate the problem of maximizing social welfare while ensuring fairness in a multi-agent multi-armed bandit (MA-MAB) setting. In this problem, a centralized decision-maker takes actions over time, generating rand…
FairnessMulti-Armed BanditsAn Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret
Recently a multi-agent variant of the classical multi-armed bandit was proposed to tackle fairness issues in online learning. Inspired by a long line of work in social choice and economics, the goal is to optimize the Na…
2kFairnessNo-Regret Learning for Fair Multi-Agent Social Welfare Optimization
We consider the problem of online multi-agent Nash social welfare (NSW) maximization. While previous works of Hossain et al. [2021], Jones et al. [2023] study similar problems in stochastic multi-agent multi-armed bandit…
FairnessMulti-Armed BanditsFair Contextual Multi-Armed Bandits: Theory and Experiments
When an AI system interacts with multiple users, it frequently needs to make allocation decisions. For instance, a virtual agent decides whom to pay attention to in a group setting, or a factory robot selects a worker to…
Decision MakingFairnessMulti-Armed BanditsAchieving Fairness in Stochastic Multi-armed Bandit Problem
We study an interesting variant of the stochastic multi-armed bandit problem, called the Fair-SMAB problem, where each arm is required to be pulled for at least a given fraction of the total available rounds. We investig…
FairnessMulti-Armed Bandits