Combinatorial Optimization for Competing Agents – COCA

The project deals with problems at the interface between combinatorial optimization and game theory. Combinatorial optimization is a very active field in computer science. This is certainly due to the numerous real world applications (e.g. in telecommunications, transportation, engineering design...). However the strategic context where these problems arise is often put aside. That is, a context in which an individual's success in making choices depends on the choices of others. This is typically the case when several self-interested agents share (and compete for) a common resource (e.g. a network, a market). With the development of Internet and electronic commerce, this kind of problems involving both a combinatorial and strategic dimension grows in computer science. If no central entity monitors the agents' decisions then it is unlikely that they spontaneously reach a socially good configuration. Indeed conflicting interests and interfering decisions often lead to a poor use of the resource. The aim of this project is to bring operational solutions that can avoid or minimize this waste (in a combinatorial setting), by studying the impact that can have an external entity that tries to influence the game towards a socially good equilibrium. The focus is on algorithmic solutions. The use of game theoretic tools for these problems is particularly relevant because the purpose of game theory is to describe rational behavior for interactive decision problems.