Stability-Accuracy Tradeoffs in Decentralized Online Learning of Coalition Structures by Selfish Agents

Abstract

Coalition formation involves self-organized coalitions generated through strategic collaborations of autonomous selfish agents. In online learning of coalition structures, agents’ preferences toward each other are initially unknown before agents interact. Coalitions are formed iteratively based on preferences that agents learn online from repeated feedback resulting from their interactions. In this work, we introduce online learning in coalition formation through the lens of distributed decision-making, where self-interested agents operate without global coordination or information sharing, and learn only from their own experience. Under the selfish perspective, each agent seeks to maximize her own utility. Hence, we analyze the system in terms of Nash stability, where no agent can improve her utility by unilaterally deviating. Our goal is therefore designing sample-efficient decentralized algorithms for selfish agents that minimize their Nash regret, yielding approximately Nash stable solutions. This poses a natural tension between an algorithm’s performance in the short- and long-term, trading off between the accuracy of the utility estimation at each round and the long-term objective of minimizing Nash regret to reach approximately Nash stable outcomes. Specifically, we first devise an algorithm where each agent sacrifices accuracy at each single time step by using only one utility feedback per round to update her strategy, but still has Nash regret and sample complexity bounds that are optimal up to logarithmic factors. To control the error incurred at any individual time instant, we then propose a method using multiple samples per round, yet at the expense of obtaining suboptimal Nash regret and sample complexity bounds.