Multi-agent Coordination using Local Search
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 953-957.
Abstract
We consider the problem of coordinating the behavior of multiple self-interested agents. It involves constraint optimization problems that often can only be solved by local search algorithms. Using local search poses problems of incentivecompatibility and individual rationality. We thus define a weaker notion of bounded-rational incentive-compatibility where manipulation is made impossible with high probability through computational complexity. We observe that in real life, manipulation of complex situations is often impossible because the effect of the manipulation cannot be predicted with sufficient accuracy. We show how randomization schemes in local search can make predicting its outcome hard and thus form a bounded-rational incentive-compatible coordination algorithm.
@inproceedings{ijcai2005p129,
title = {Multi-agent Coordination using Local Search},
author = {Faltings, Boi and Nguyen, Quang Huy},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {953--957},
year = {2005},
url = {https://ijcai.org/proceedings/2005/129},
}
TY - CPAPER TI - Multi-agent Coordination using Local Search AU - Faltings, Boi AU - Nguyen, Quang Huy T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 953 EP - 957 UR - https://ijcai.org/proceedings/2005/129 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
