Negotiation criteria for multiagent resource allocation

Karthik Iyer; Michael N. Huhns; Karthik Iyer; Michael N. Huhns

doi:10.1017/S0269888909000204

Abstract: Negotiation in a multiagent system is a topic of active interest for enabling the allocation of scarce resources among autonomous agents. This paper presents a discussion of the research on negotiation criteria, which puts in context the contributions to resource allocation from the fields of economics, mathematics, and multiagent systems. We group the criteria based on how they relate to each other as well as their historical origin. In addition, we present three new criteria: verifiability, dimensionality, and topology. The criteria are organized into five categories. The allocation category contains criteria concerning fairness and envy-freeness with respect to how resources are allocated to agents. The protocol category covers criteria for stability, strategy-proofness, and communication costs. The procedure category includes criteria about the complexity of allocation procedures. The resource category has criteria for the properties that various resources can take and how they affect allocation. The paper concludes with a discussion of the criteria for agent utility functions. The overall objectives of this paper are (1) to create a starting point for protocol engineering by future negotiation designers and (2) to enumerate the criteria and their measures that enable negotiation and allocation mechanisms to be compared objectively.

Other Articles By Authors

Negotiation criteria for multiagent resource allocation

Department of Computer Science and Engineering

Published online: 01 June 2009

Abstract: Abstract: Negotiation in a multiagent system is a topic of active interest for enabling the allocation of scarce resources among autonomous agents. This paper presents a discussion of the research on negotiation criteria, which puts in context the contributions to resource allocation from the fields of economics, mathematics, and multiagent systems. We group the criteria based on how they relate to each other as well as their historical origin. In addition, we present three new criteria: verifiability, dimensionality, and topology. The criteria are organized into five categories. The allocation category contains criteria concerning fairness and envy-freeness with respect to how resources are allocated to agents. The protocol category covers criteria for stability, strategy-proofness, and communication costs. The procedure category includes criteria about the complexity of allocation procedures. The resource category has criteria for the properties that various resources can take and how they affect allocation. The paper concludes with a discussion of the criteria for agent utility functions. The overall objectives of this paper are (1) to create a starting point for protocol engineering by future negotiation designers and (2) to enumerate the criteria and their measures that enable negotiation and allocation mechanisms to be compared objectively.

HTML

Acknowledgments

We would like to sincerely thank our two anonymous referees for their valuable input to improve various aspects of the paper. Their detailed comments on each aspect of the paper helped us in presenting this material in a clear and succinct manner.

Agents can be designed with one of the following priorities ranked higher than the others: 1. Agents want as much of the resource as possible (individual rationality). 2. Agents want a portion of the resource whose value is greater than or equal to that of any other agent (envy-freeness). 3. Agents want portions whose value is greater than a certain threshold (egalitarianism).
Our statement holds if priority #2 overrides the other two.

We do not provide any concrete references to the criteria as we encountered only passing discussions on these criteria in the existing literature.

The moving-knife procedure is so-called, because it is assumed that a knife moves smoothly over a cake demarcating an increasingly larger portion until an agent calls ‘Stop’, to indicate the portion is satisfactory to the agent.

We use the comparison ‘discrete vs. continuous’ for characterizing procedures. This comparison could also apply to the discussion in Section 5.1 on resources. However, they carry different semantics in the two places. In order to reduce confusion, we use the term ‘divisibility’ when discussing resources.

The Selfridge–Conway procedure is mentioned by Brams and Taylor in their book Fair Division: From Cake-Cutting to Dispute Resolution, on page 116. Regarding their source for the procedure, they state, ‘Such a procedure was found about 1960 by John L. Selfridge and, later but independently, by John H. Conway […] Although never published by either, the procedure was quickly and widely disseminated by Richard K. Guy and others’.

An excellent exposition of how agent preferences can be represented is discussed by Chevaleyre et al. (2006). The reader is referred to their paper for further details on the topic of agent preferences. We briefly enumerate the types of agent preferences in this paper for the sake of completeness. In addition, we add a few other types to round off this section.

Rights and permissions

References (32)

About this article

Cite this article

Karthik Iyer, Michael N. Huhns. 2009. Negotiation criteria for multiagent resource allocation. The Knowledge Engineering Review. 24:4 doi: 10.1017/S0269888909000204

Karthik Iyer, Michael N. Huhns. 2009. Negotiation criteria for multiagent resource allocation. The Knowledge Engineering Review. 24:4 doi: 10.1017/S0269888909000204

{{lists.name}}

Negotiation criteria for multiagent resource allocation

Abstract

Rights and permissions

References

About this article

Cite this article

Article Metrics

Access History

Other Articles By Authors