Cost-Optimal Planning by Self-Interested Agents

Raz Nissim, Ronen I. BrafmanAAAI 2013 · DOI

Abstract

This paper presents the first distributed mechanism for multi-agent planning that is simultaneously cost-optimal, strategy-proof, and privacy-preserving. By integrating the Vickrey-Clarke-Groves (VCG) mechanism with a distributed A search (MAD-A), the proposed framework enables self-interested agents to collaborate on complex tasks without a trusted central authority or the disclosure of proprietary internal processes. We introduce a "Multigoal Search" optimization to handle the computational demands of calculating VCG payments in a distributed setting. Experimental evaluations on standard benchmarks demonstrate that while maintaining privacy incurs a performance cost, the system remains efficient enough for practical application.

Introduction

In classical AI planning, agents are typically assumed to be perfectly cooperative. However, real-world scenarios—such as independent logistics companies coordinating deliveries—involve self-interested agents. Two primary challenges emerge in these settings: manipulation and privacy. Agents may misreport their costs to maximize individual profit, leading to global inefficiency, and they are often unwilling to reveal their private states or local actions to competitors.

While mechanism design has addressed incentive compatibility in simpler domains like network routing, AI planning is significantly more complex because the state space is implicit and exponentially large. This paper addresses these challenges by proposing Selfish-MAD-A*.

Methodology

The Selfish-MAD-A* framework combines three core elements:

  1. MA-STRIPS Model: This framework partitions planning into "public" actions (visible to others) and "private" actions (internal to the agent), providing a foundation for privacy-preserving coordination.
  2. VCG Mechanism: To ensure strategy-proofness, the system calculates payments based on each agent's "social cost"—the difference in the global plan's cost with and without that agent's participation. This makes truth-telling the dominant strategy.
  3. MAD-A* Algorithm: A distributed version of A* where agents explore the state space in parallel, sharing only public state transitions via messages.

To calculate VCG payments efficiently, the authors developed a Multigoal Search optimization. Instead of running $k+1$ separate searches (one for the global plan and one for each marginal problem where an agent is excluded), they utilize a single distributed search space. States are tagged with the set of participating agents, allowing the algorithm to find all necessary optimal paths simultaneously.

Experimental Results

The researchers evaluated the approach using standard benchmark domains from the International Planning Competition (IPC), including Rovers, Satellite, Transport, and Zenotravel. These tests compared centralized A (A), a centralized version of the multi-agent algorithm (Cen), a basic distributed version (Dis), and the optimized distributed version (OptDis).

Comparative performance of centralized and distributed planning algorithms across IPC benchmarks.

The results, summarized in the table above, highlight several key findings. While there is a performance gap between centralized and distributed approaches—largely due to the "cost of privacy" affecting heuristic accuracy—the OptDis algorithm significantly outperforms the basic distributed version. By reducing redundant state generation, OptDis manages to solve most benchmark problems within a 30-minute window, proving the viability of the multigoal search optimization.

Key Insights and Discussion

  • The Cost of Privacy vs. Selfishness: The study reveals that the computational overhead required to make the system strategy-proof (selfishness) is relatively low. The primary bottleneck is the overhead of maintaining privacy in a distributed search, which limits the effectiveness of global heuristics.
  • Ex Post Faithfulness: The authors prove that their implementation is "ex post faithful." If other agents follow the protocol, it is in an individual agent's best interest to follow it as well, both in reporting costs and executing search steps.
  • Implicit Graphs: Unlike previous incentive-compatible routing methods, this approach handles transition systems that are never explicitly constructed, making it suitable for complex planning tasks.

Conclusion and Future Work

Selfish-MAD-A* represents a significant step forward in multi-agent coordination. While it successfully addresses optimality, strategy-proofness, and privacy, some limitations remain. The mechanism currently assumes a "trusted bank" for final payments and does not yet account for agent collusion. Future work will focus on improving heuristic accuracy in private settings and addressing potential scalability issues in extremely large-scale environments where the cost of privacy is most pronounced.

Summary updated

BibTeX
@inproceedings{nissim2013cost,
  author = {Raz Nissim and Ronen I. Brafman},
  title = {{Cost-Optimal Planning by Self-Interested Agents}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8640},
}
Figure