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. Copyright © 2009, Inderscience Publishers.
Felici, G., Mecoli, M., Mirchandani, P., Pacifici, A. (2009). Equilibrium in a two-agent assignment problem. INTERNATIONAL JOURNAL OF OPERATIONAL RESEARCH, 6(1), 4-26 [10.1504/IJOR.2009.026241].
Equilibrium in a two-agent assignment problem
PACIFICI, ANDREA
2009-01-01
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. Copyright © 2009, Inderscience Publishers.File | Dimensione | Formato | |
---|---|---|---|
IJOR 6(1) Paper 2.pdf
accesso aperto
Descrizione: Articolo principale
Dimensione
275.2 kB
Formato
Adobe PDF
|
275.2 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.