This thesis deals with the algorithmic construction of collective solutions for a group of agents (e.g. election, allocation of items, etc.). For several reasons, time can be an obstacle when one wants to make and implement a collective decision. Between the start of the process and its end, the context is likely to evolve: the group of agents may be modified, and the agents’ preferences can also change.
Thus, the complete input data is rarely known when the decision process starts. Instead, the data is revealed and updated over time though partial decisions have to made. Despite this lack of knowledge, we need methods which eventually provides a good solution.
With the development of the Internet, today’s society is full of unpredictable situations: opinions, prices, demands, and available resources rapidly evolve. The goal of this thesis is to study social choice problems (matching, voting, allocation of items, etc.) in a dynamic context. That is, we want concepts or tools for assessing the quality of a solution and algorithmic methods for computing those solutions.
We search for an excellent and highly motivated student with a background in computer science. In particular, we need someone with a good knowledge of algorithms for combinatorial optimization, game theory and social choice. Some notions of online and robust optimization would be an asset.