Modèles et algorithmes pour les problèmes d'optimisation combinatoire du partage des ressources entre les agents (traduction Google)

In this talk, I will present models and algorithms for combinatorial optimization problems of resource sharing. The resources can be time and machines (scheduling problems), machines in datacenters (assignment of tasks), or more generic resources (generalized assignment problem). Therefore, the problems studied will mainly be scheduling and assignment problems. Our aim will be to design and study algorithms for resource sharing between independent agents, in order to optimize a social-choice function (social welfare). When the agents can have the choice between different strategies, this will fall into the field of algorithmic game theory, and we will try to design systems which induce good equilibria. We will also see how a trusted third entity can help in obtaining good solutions for the social choice function. When the agents have private information, this will fall into the mechanism design field, and we will be interested in the quality (in term of approximation ratio) of truthful algorithms. When the aim is to compute a solution which will be common to all the agents (the agents having preferences on the resources), we will use tools from the multi-objective combinatorial optimization field and the computational social choice field.

4 Docteurs 2013 - 2023