Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-25T07:41:40.788Z Has data issue: false hasContentIssue false
  • English
  • Français

THE MAGIC OF NASH SOCIAL WELFARE IN OPTIMIZATION: DO NOT SUM, JUST MULTIPLY!

Part of: Operations research and management science Game theory

Published online by Cambridge University Press:  07 July 2022

HADI CHARKHGARD Open the ORCID record for HADI CHARKHGARD [Opens in a new window] ,
KIMIA KESHANIAN Open the ORCID record for KIMIA KESHANIAN [Opens in a new window] ,
RASUL ESMAEILBEIGI Open the ORCID record for RASUL ESMAEILBEIGI [Opens in a new window]  and
PARISA CHARKHGARD Open the ORCID record for PARISA CHARKHGARD [Opens in a new window]
HADI CHARKHGARD*
Affiliation:
Department of Industrial and Management Systems Engineering, University of South Florida, Tampa, FL33620, USA
KIMIA KESHANIAN
Affiliation:
Information and Technology Management Department, University of Tampa, Tampa, FL33606, USA; e-mail: [email protected]
RASUL ESMAEILBEIGI
Affiliation:
School of Information Technology, Deakin University, Geelong, Victoria3220, Australia; e-mail: [email protected]
PARISA CHARKHGARD
Affiliation:
School of Mathematical and Physical Sciences, University of Newcastle, New South Wales2308, Australia; e-mail: [email protected]
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We explain some key challenges when dealing with a single- or multi-objective optimization problem in practice. To overcome these challenges, we present a mathematical program that optimizes the Nash social welfare function. We refer to this mathematical program as the Nash social welfare program (NSWP). An interesting property of the NSWP is that it can be constructed for any single- or multi-objective optimization problem. We show that solving the NSWP could result in more desirable solutions in practice than its single- or multi-objective counterpart. We also discuss several promising approaches that could be employed to solve the NSWP in practice.

Keywords

Nash social welfareequitysingle-objective optimizationmulti-objective optimizationmultiplicative program

MSC classification

Primary: 90C29: Multi-objective and goal programming
Secondary: 90B50: Management decision making, including multiple objectives 91A12: Cooperative games
Type
Research Article
Information
The ANZIAM Journal , Volume 64 , Issue 2 , April 2022 , pp. 119 - 134
Check for updates
Copyright
© The Author(s), 2022. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Acuna, J. A., Zayas-Castro, J. L. and Charkhgard, H., “Ambulance allocation optimization model for the overcrowding problem in US emergency departments: a case study in Florida”, Socio-Econ. Plann. Sci. 71 (2019) 100747; doi:10.1016/j.seps.2019.100747.CrossRefGoogle Scholar
Ben-Tal, A. and Nemirovski, A., “On polyhedral approximations of the second-order cone”, Math. Oper. Res. 26 (2001) 193–205; doi:10.1287/moor.26.2.193.10561.CrossRefGoogle Scholar
Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N. and Wang, J., “The unreasonable fairness of maximum Nash welfare”, Proc. 2016 ACM Conf. Economics and Computation, EC’16 (ACM, New York, 2016) 305–322; https://doi.org/10.1145/2940716.2940726.CrossRefGoogle Scholar
Charkhgard, H., Savelsbergh, M. and Talebian, M., “A linear programming based algorithm to solve a class of optimization problems with a multi-linear objective function and affine constraints”, Comput. Oper. Res. 89 (2018) 17–30; doi:10.1016/j.cor.2017.07.015.CrossRefGoogle Scholar
Charkhgard, H., Savelsbergh, M. and Talebian, M., “Nondominated Nash points: application of biobjective mixed integer programming”, 4OR 16 (2018) 151–171; doi:10.1007/s10288-017-0354-2.Google Scholar
Cole, R. and Gkatzelis, V., “Approximating the Nash social welfare with indivisible items”, SIAM J. Comput. 47 (2018) 1211–1236; doi:10.1137/15M1053682.CrossRefGoogle Scholar
Ehrgott, M., Multicriteria optimization, 2nd edn (Springer, New York, 2005) doi:10.1007/3-540-27659-9.Google Scholar
Jorge, J. M., “An algorithm for optimizing a linear function over an integer efficient set”, European J. Oper. Res. 195 (2009) 98–103; doi:10.1016/j.ejor.2008.02.005.CrossRefGoogle Scholar
Kalai, E., “Nonsymmetric Nash solutions and replications of 2-person bargaining”, Internat. J. Game Theory 6 (1977) 129–133; doi:10.1007/BF01774658.CrossRefGoogle Scholar
Mariotti, M., “Fair bargains: distributive justice and Nash bargaining theory”, Rev. Econ. Stud. 66 (1999) 733–741; doi:10.1111/1467-937X.00106.CrossRefGoogle Scholar
Melendez, K. A., Subramanian, V., Das, T. K. and Kwon, C., “Empowering end-use consumers of electricity to aggregate for demand-side participation ”, Appl. Energy 248 (2019) 372–382; doi:10.1016/j.apenergy.2019.04.092.CrossRefGoogle Scholar
Mendoza-Alonzo, J., Zayas-Castro, J. L. and Charkhgard, H., “Office-based and home-care for older adults in primary care: a comparative analysis using the Nash bargaining solution”, Socio-Econ. Plann. Sci. 69 (2019) 100710; doi:10.1016/j.seps.2019.05.001.Google Scholar
Moulin, H., Fair division and collective welfare (The MIT Press, Cambridge, MA, 2003); doi:10.7551/mitpress/2954.001.0001.CrossRefGoogle Scholar
Nash, J. F., “The bargaining problem”, Econometrica 18 (1950) 155–162; doi:10.2307/1907266.Google Scholar
Rao, S., “Game theory approach for multiobjective structural optimization”, Comput. & Struct. 25 (1987) 119–127; doi:10.1016/0045-7949(87)90223-9.CrossRefGoogle Scholar
Saghand, P. G. and Charkhgard, H., “A criterion space search algorithm for mixed integer linear maximum multiplicative programs: a multiobjective optimization approach”, Int. Trans. Oper. Res. 29 (2022) 1659–1687; doi:10.1111/itor.12964.CrossRefGoogle Scholar
Saghand, P. G. and Charkhgard, H., “Exact solution approaches for integer linear generalized maximum multiplicative programs through the lens of multi-objective optimization”, Comput. Oper. Res. 137 (2022) 105549; doi:10.1016/j.cor.2021.105549.CrossRefGoogle Scholar
Saghand, P. G., Charkhgard, H. and Kwon, C., “A branch-and-bound algorithm for a class of mixed integer linear maximum multiplicative programs”, Comput. Oper. Res. 101 (2019) 263–274; doi:10.1016/j.cor.2018.08.004.CrossRefGoogle Scholar
Serrano, R., “Fifty years of the Nash program 1953–2003”, Investigaciones Econ. 29 (2005) 219–258; doi:10.2139/ssrn.724233.Google Scholar
Sierra-Altamiranda, A., Charkhgard, H., Eaton, M., Martin, J., Yurek, S. and Udell, B. J., “Spatial conservation planning under uncertainty using modern portfolio theory and Nash bargaining solution”, Ecol. Model. 423 (2020) 109016; doi:10.1016/j.ecolmodel.2020.109016.Google Scholar
Vazirani, V. V., “The notion of a rational convex program, and an algorithm for the Arrow–Debreu Nash bargaining game”, J. ACM 59 (2012) 1–36; doi:10.1145/2160158.2160160.CrossRefGoogle Scholar