ConferencePresented as Spotlight
Online Friends Partitioning under Uncertainty
Proceedings of the 27th European Conference on Artificial Intelligence ECAI 2024
Abstract
We study the friendship-based online coalition formation problem, in which agents that appear one at a time should be partitioned into coalitions, and an agent’s utility for a coalition is the number of her neighbors (i.e., friends) within the coalition. Unlike prior work, agents’ friendships may be uncertain. We analyze the desirability of the resulting partition in the common term of optimality, aiming to maximize the social welfare. We design an online algorithm termed Maximum Predicted Coalitional Friends (MPCF), which is enhanced with predictions of each agent’s number of friends within any possible coalition. For common classes of random graphs, we prove that MPCF is optimal, and, for certain graphs, provides the same guarantee as the best known competitive algorithm for settings without uncertainty.
Cite
Saar Cohen and Noa Agmon. Online Friends Partitioning under Uncertainty. In Proceedings of the 27th European Conference on Artificial Intelligence (ECAI), 2024.
@inproceedings{cohen2024online,
title = {{Online Friends Partitioning under Uncertainty}},
author = {Saar Cohen and Noa Agmon},
booktitle = {Proceedings of the 27th European Conference on Artificial Intelligence},
series = {Frontiers in Artificial Intelligence and Applications},
year = {2024},
doi = {10.3233/FAIA240882}
}