Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents

Bachrach, Yoram; Rosenschein, Jeffrey S.

Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents

Download BibTeX Cite

Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 1653-1653.

Abstract

Vickrey-Clarke-Groves (VCG) mechanisms are a framework for finding a solution to a distributed optimization problem in systems of self-interested agents. VCG mechanisms have received wide attention in the AI community because they are efficient and strategy-proof; a special case of the Groves family of mechanisms, VCG mechanisms are the only direct-revelation mechanisms that are allocatively efficient and strategy-proof. Unfortunately, they are only weakly budget-balanced. We consider self-interested agents in a network flow domain, and show that in this domain, it is possible to design a mechanism that is both allocatively-efficient and almost completely budget-balanced. This is done by choosing a mechanism that is not strategy-proof but rather strategyresistant. Instead of using the VCG mechanism, we propose a mechanism in which finding a beneficial manipulation is an NP-complete problem, and the payments from the agents to the mechanism may be minimized as much as desired.

Yoram Bachrach, and Jeffrey S. Rosenschein. 2005. Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05. IJCAI, 1653–1653. https://ijcai.org/proceedings/2005/265

@inproceedings{ijcai2005p265,
  title     = {Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents},
  author    = {Bachrach, Yoram and Rosenschein, Jeffrey S.},
  booktitle = {Proceedings of the Nineteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-05}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  pages     = {1653--1653},
  year      = {2005},
  url       = {https://ijcai.org/proceedings/2005/265},
}

TY  - CPAPER
TI  - Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents
AU  - Bachrach, Yoram
AU  - Rosenschein, Jeffrey S.
T2  - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2005
SP  - 1653
EP  - 1653
UR  - https://ijcai.org/proceedings/2005/265
ER  -