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.B., & 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

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.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore MAT/09 - Ricerca Operativa
English
Competitive assignment; Equilibrium; Pareto-optimality
Felici, G., Mecoli, M., Mirchandani, P.B., & Pacifici, A. (2009). Equilibrium in a two-agent assignment problem. INTERNATIONAL JOURNAL OF OPERATIONAL RESEARCH, 6(1), 4-26 [10.1504/IJOR.2009.026241].
Felici, G; Mecoli, M; Mirchandani, P; Pacifici, A
Articolo su rivista
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2108/34747
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact