Partage équitable de ressources communes: (2) Éléments de complexité et d'algorithmique

摘要

Le partage de ressources communes est un problème rencontré par de nombreuses organisations industrielles et économiques. Il s'agit, pour un ensemble d'agents ayant financé une ressource commune, d'exploiter conjointement celle-ci de manière équitable et efficace. Dans un article précédent [FAR 04], nous avons proposé un modèle générique et formel de ce problème combinatoire, et montré son application à un problème de partage de ressources satellitaires. Dans le présent article, nous apportons des éléments concernant la complexité théorique du problème et proposons des algorithmes pour le résoudre.%Many industrial and economic organizations come up against the problem of sharing common property resources. In this problem, a set of agents, having co-funded a common property resource, must exploit it in a fair and efficient way. In a previous article [FAR 04], we described a generic and formal model for this problem, and showed its application to a satellite resource sharing problem. In the present article, we characterize the theoretical complexity of this problem under different hypothesis, and discuss some algorithms for solving it.