Maximizing Nash Social Welfare Based on Greedy Algorithm and Estimation of Distribution Algorithm

Abstract

The Nash social welfare (NSW) problem is relevant not only to the economic domain but also extends its applicability to the field of computer science. However, maximizing Nash social welfare is an APX-hard problem. In this study, we propose two approaches to enhance the maximization of Nash social welfare. First, a general greedy algorithm (GA) capable of addressing the Nash social welfare problem for both agents with identical and differing valuations was presented. It is proven that the proposed algorithm aligns with the previous greedy algorithm when all agents possess identical valuations. Second, an innovative method for solving the Nash social welfare problems using evolutionary algorithms was developed. This approach integrates the Estimation of Distribution Algorithms (EDAs) with neighborhood search techniques to improve the maximization process of Nash social welfare. Finally, the proposed algorithms were implemented across a range of instances with the objective of maximizing Nash social welfare. The experimental results indicate that the approximation solutions derived from the Estimation of Distribution Algorithm outperform those obtained via the greedy algorithm.The Nash social welfare (NSW) problem is relevant not only to the economic domain but also extends its applicability to the field of computer science. However, maximizing Nash social welfare is an APX-hard problem. In this study, we propose two approaches to enhance the maximization of Nash social welfare. First, a general greedy algorithm (GA) capable of addressing the Nash social welfare problem for both agents with identical and differing valuations was presented. It is proven that the proposed algorithm aligns with the previous greedy algorithm when all agents possess identical valuations. Second, an innovative method for solving the Nash social welfare problems using evolutionary algorithms was developed. This approach integrates the Estimation of Distribution Algorithms (EDAs) with neighborhood search techniques to improve the maximization process of Nash social welfare. Finally, the proposed algorithms were implemented across a range of instances with the objective of maximizing Nash social welfare. The experimental results indicate that the approximation solutions derived from the Estimation of Distribution Algorithm outperform those obtained via the greedy algorithm.