---
title: "Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents"
authors:
  - "Yoram Bachrach"
  - "Jeffrey S. Rosenschein"
doi: ""
url: "https://ijcai.org/proceedings/2005/265"
pdf: "https://ijcai.org/proceedings/2005/0265.pdf"
venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence"
year: 2005
pages: "1653-1653"
track: ""
keywords:
---

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

Yoram Bachrach, Jeffrey S. Rosenschein

*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.