Faculté informatique et communications IC, Section d'informatique, Programme doctoral Informatique, Communications et Information, Institut d'informatique fondamentale IIF (Laboratoire d'intelligence artificielle LIA)

Local search techniques for multi-agent constraint optimization problems

Nguyen, Quang Huy ; Faltings, Boi V. (Dir.)

Thèse Ecole polytechnique fédérale de Lausanne EPFL : 2008 ; no 4074.

Ajouter à la liste personnelle
    Combinatorial optimization problems in the real world are ubiquitous. Practical applications include planning, scheduling, distributed control, resource allocation, etc. These problems often involve multiple agents and can be formulated as a Multi-agent Constraint Optimization Problem (MCOP). A major challenge in such systems is the agent coordination, such that a global optimal outcome is achieved. This thesis is devoted to two major issues that arise in MCOP: efficient optimization algorithms and manipulations from self-interested agents. We introduce a new randomized local search optimization algorithm called Random Subset Optimization (RSO). The RSO algorithm is tested on various applications and demonstrated to converge faster than other local search techniques while achieving competitive performance. For self-interested agents, we define a new form of incentive compatibility called size-limited incentive compatibility and show that RSO algorithm can be used to prevent agents' manipulations.