Skip to Main content Skip to Navigation
Conference papers

Nash balanced assignment problem

Abstract : In this paper, we consider a variant of the classic Assignment Problem (AP), called the Balanced Assignment Problem (BAP) [2]. The BAP seeks to find an assignment solution which has the smallest value of max-min distance: the difference between the maximum assignment cost and the minimum one. However, by minimizing only the max-min distance, the total cost of the BAP solution is neglected and it may lead to a very inefficient solution in terms of total cost. Hence, we propose a fair way based on Nash equilibrium [1] [3], [4] to inject the total cost into the objective function of the BAP for finding assignment solutions having a better trade-off between the two objectives: the first aims at minimizing the total cost and the second aims at minimizing the max-min distance. For this purpose, we introduce the concept of Nash Fairness (NF) solutions based on the definition of proportional-fair scheduling adapted in the context of the AP: a transfer of utilities between the total cost and the max-min distance is considered to be fair if the percentage increase in the total cost is smaller than the percentage decrease in the max-min distance and vice versa. We first show the existence of a NF solution for the AP which is exactly the optimal solution minimizing the product of the total cost and the max-min distance. However, finding such a solution may be difficult as it requires to minimize a concave function. The main result of this paper is to show that finding all NF solutions can be done in polynomial time. For that, we propose a Newton-based iterative algorithm converging to NF solutions in polynomial time. It consists in optimizing a sequence of linear combinations of the two objective based on Weighted Sum Method [5]. Computational results on various instances of the AP are presented and commented.
Document type :
Conference papers
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03656133
Contributor : Minh Hieu NGUYEN Connect in order to contact the contributor
Submitted on : Sunday, May 1, 2022 - 3:02:24 PM
Last modification on : Monday, May 16, 2022 - 6:27:48 PM

File

ISCO_2022 extension.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03656133, version 1

Citation

Minh Hieu Nguyen, Mourad Baiou, Viet Hung Nguyen. Nash balanced assignment problem. 7th International Symposium on Combinatorial Optimization (ISCO), May 2022, Online Conference, France. ⟨hal-03656133⟩

Share

Metrics

Record views

5

Files downloads

3