Combinatorial Optimization with Competing Agents
Résumé
This chapter deals with three specific studies conducted within the combinatorial optimization for competing agents (COCA) project. It also deals with optimization problems arising from the relationship between members of a social network. A game theoretic model of this relationship is introduced and widely discussed. The chapter then focuses on developing a mechanism able to incentivize the self-interested network members to play the profile maximizing the social welfare. It devotes to a simple connection game. It first reviews the main results, where the price of anarchy of the game is studied. Then two protocols are discussed, and the goal is to induce a socially optimal configuration. The chapter focuses the design of truthful algorithms with performance guarantee regarding the social welfare. It illustrates a facility location problem and an allocation problem.