Online Learning for Project Selection in Hedonic Project Games

Jaber Valizadeh, Dongmo Zhang, Omar Mubin, Ray Telikani
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:6851-6861, 2026.

Abstract

We study Hedonic Project Games, a model in which agents select projects with divisible rewards while holding subjective preferences over coalition composition. This framework addresses a key gap in existing models: agents simultaneously care about who they collaborate with and what they work on. We extend this framework to an online learning setting in which rewards and preferences are initially unknown and learned through repeated interactions. We develop a decentralized variance-reduced stochastic policy-gradient method that provably converges to approximate {Nash} equilibria using single-sample gradient estimates, and an unbiased momentum variant that achieves faster convergence at the cost of additional curvature computation. We provide sample-complexity guarantees for both methods and show that exploiting the game’s additive pairwise structure reduces the interactions required to reach an approximate equilibrium by a polynomial factor in the number of agents. Experiments on synthetic instances and a real-world crowdsourcing dataset validate the theoretical convergence rates and demonstrate the advantages of momentum-based variance reduction over momentum-free baselines.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-valizadeh26a, title = {Online Learning for Project Selection in Hedonic Project Games}, author = {Valizadeh, Jaber and Zhang, Dongmo and Mubin, Omar and Telikani, Ray}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {6851--6861}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/valizadeh26a/valizadeh26a.pdf}, url = {https://proceedings.mlr.press/v337/valizadeh26a.html}, abstract = {We study Hedonic Project Games, a model in which agents select projects with divisible rewards while holding subjective preferences over coalition composition. This framework addresses a key gap in existing models: agents simultaneously care about who they collaborate with and what they work on. We extend this framework to an online learning setting in which rewards and preferences are initially unknown and learned through repeated interactions. We develop a decentralized variance-reduced stochastic policy-gradient method that provably converges to approximate {Nash} equilibria using single-sample gradient estimates, and an unbiased momentum variant that achieves faster convergence at the cost of additional curvature computation. We provide sample-complexity guarantees for both methods and show that exploiting the game’s additive pairwise structure reduces the interactions required to reach an approximate equilibrium by a polynomial factor in the number of agents. Experiments on synthetic instances and a real-world crowdsourcing dataset validate the theoretical convergence rates and demonstrate the advantages of momentum-based variance reduction over momentum-free baselines.} }
Endnote
%0 Conference Paper %T Online Learning for Project Selection in Hedonic Project Games %A Jaber Valizadeh %A Dongmo Zhang %A Omar Mubin %A Ray Telikani %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-valizadeh26a %I PMLR %P 6851--6861 %U https://proceedings.mlr.press/v337/valizadeh26a.html %V 337 %X We study Hedonic Project Games, a model in which agents select projects with divisible rewards while holding subjective preferences over coalition composition. This framework addresses a key gap in existing models: agents simultaneously care about who they collaborate with and what they work on. We extend this framework to an online learning setting in which rewards and preferences are initially unknown and learned through repeated interactions. We develop a decentralized variance-reduced stochastic policy-gradient method that provably converges to approximate {Nash} equilibria using single-sample gradient estimates, and an unbiased momentum variant that achieves faster convergence at the cost of additional curvature computation. We provide sample-complexity guarantees for both methods and show that exploiting the game’s additive pairwise structure reduces the interactions required to reach an approximate equilibrium by a polynomial factor in the number of agents. Experiments on synthetic instances and a real-world crowdsourcing dataset validate the theoretical convergence rates and demonstrate the advantages of momentum-based variance reduction over momentum-free baselines.
APA
Valizadeh, J., Zhang, D., Mubin, O. & Telikani, R.. (2026). Online Learning for Project Selection in Hedonic Project Games. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:6851-6861 Available from https://proceedings.mlr.press/v337/valizadeh26a.html.

Related Material