ConferencePresented as Oral
Online Learning of Fair Coalition Structures
Proceedings of the 28th European Conference on Artificial Intelligence ECAI 2025
Abstract
Coalition formation concerns partitioning agents into disjoint coalitions based on their preferences for one another. In online learning of coalition structures, agents’ true preferences may be initially unknown. Thus, coalitions are repeatedly formed based on preferences learned online from iterative feedback derived from interactions in those coalitions. This work introduces a new fairness-oriented approach to online learning in coalition formation, relying only on partial noisy feedback observed after agents interact. We analyze the system in terms of envy-based fairness notions. Envy-freeness is a popular criterion, where no agent prefers another agent’s coalition over her own. While trivial envy-free solutions exist for unconstrained number of coalitions and coalition sizes, constraints may make envy-free partitions unattainable. We thus present a new envy-freeness-based metric into hedonic games: minimax envy partitions, which minimize the maximum envy experienced by any agent. We devise an algorithm designed to minimize maximum envy, proven to attain sublinear envy regret.
Cite
Saar Cohen and Noa Agmon. Online Learning of Fair Coalition Structures. In Proceedings of the 28th European Conference on Artificial Intelligence (ECAI), 2025.
@inproceedings{cohen2025onlineb,
title = {{Online Learning of Fair Coalition Structures}},
author = {Saar Cohen and Noa Agmon},
booktitle = {Proceedings of the 28th European Conference on Artificial Intelligence},
series = {Frontiers in Artificial Intelligence and Applications},
year = {2025},
doi = {10.3233/FAIA251405}
}