---
title: "K-Swaps: Cooperative Negotiation for Solving Task-Allocation Problems"
authors:
  - "Xiaoming Zheng"
  - "Sven Koenig"
doi: ""
url: "https://ijcai.org/proceedings/2009/70"
pdf: "https://ijcai.org/proceedings/2009/0070.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "373-378"
track: ""
keywords:
---

# K-Swaps: Cooperative Negotiation for Solving Task-Allocation Problems

Xiaoming Zheng, Sven Koenig

*Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence*, pages 373-378.

## Abstract

In this paper, we study distributed algorithms for cooperative agents that allow them to exchange their assigned tasks in order to reduce their team cost. We define a new type of contract, called K-swaps, that describes multiple task exchanges among multiple agents at a time, which generalizes the concept of single task exchanges. We design a distributed algorithm that constructs all possible K-swaps that reduce the team cost of a given task allocation and show that each agent typically only needs to communicate a small part of its local computation results to the other agents. We then demonstrate empirically that K-swaps can reduce the team costs of several existing task-allocation algorithms significantly even if K is small.Xiaoming Zheng, Sven Koenig