AN OPTIMIZATION PROBLEM CONCERNING CUSTOMER’S RANKING OF GOODS
Thinh Duc Nguyen · 2018
We prove the $\mathrm{NP}$-hardness of an optimization problem originating from algorithmic game theory. In this problem, we have a list containing each customer's ranking of some goods from a set $U$ of items in a store. We want to select a subset $L\subseteq U$ of goods from which each customer will buy their highest ranked item. The objective is to maximize the sum of the rank values of bought items.