Equilibrium in a two-agent assignment problem (Q840620)

Summary: 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. Last, we give the results of extensive computational experiments.