Title: Equilibrium in a two-agent Assignment Problem

Authors: Giovanni Felici, Mariagrazia Mecoli, Pitu B. Mirchandani, Andrea Pacifici

Addresses: Istituto di Analisi dei Sistemi ed Informatica del CNR, Viale Manzoni, 30, Roma, Italy. ' Universita degli Studi di Roma 'La Sapienza', Roma, Italy. ' SIE, University of Arizona, 1127 E. James E. Rogers Way, Engineering Building 20, P.O. Box 210020 Tucson, AZ, USA. ' Universita degli Studi di Roma di Tor Vergata, Via del Politecnico, 1, Roma, Italy

Abstract: In this paper we address a particular generalisation of the Assignment Problem (AP) in a Multi-Agent setting, where distributed agents share common resources. We consider the problem of determining Pareto-optimal solutions that satisfy a fairness criterion (equilibrium). We show that the solution obtained is equivalent to a Kalai–Smorodinsky solution of a suitably defined bargaining problem and characterise the computational complexity of finding such an equilibrium. Additionally, we propose an exact solution algorithm based on a branch-and-bound scheme that exploits bounds obtained by suitably rounding the solutions of the corresponding linear relaxation, and give the results of extensive computational experiments.

Keywords: competitive assignment; equilibrium; Pareto optimality; multi-agent systems; MAS; agent-based systems; fairness.

DOI: 10.1504/IJOR.2009.026241

International Journal of Operational Research, 2009 Vol.6 No.1, pp.4 - 26

Published online: 30 May 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article