2010 journal article

Two-group knapsack game

THEORETICAL COMPUTER SCIENCE, 411(7-9), 1094–1103.

By: Z. Wang*, W. Xing* & S. Fang n

co-author countries: China 🇨🇳 United States of America 🇺🇸
author keywords: Game theory; Knapsack problem; Nash equilibrium; Price of anarchy
Source: Web Of Science
Added: August 6, 2018

This paper presents a “two-group knapsack game”. A number of investors colligate into two groups to bid on a common pool of potential projects. Each investor has his/her own budget limit and a cost estimation for undertaking each possible project. Each group represents a power by its market share. Associated with each project, there is a potential profit that can be realized. Investors in the same group hold an internal agreement of putting the group’s collective interest ahead of the individual’s interest and not bidding on the same project by more than one investor in the group. The profit of a particular project can be wholly taken by the sole bidder or shared proportionally by two bidders in different groups according to their group power. The objective of each group may be based not only on its own group profit but also on the other group’s profit. Assuming that each investor acts in a selfish manner with the best response to optimize its group’s objective subject to the budget constraint, we show that a pure Nash equilibrium exists under certain conditions. We also have some interesting findings of the “price of anarchy” (the ratio of the worst Nash equilibrium to the social optimum) associated with a simplified version of the two-group knapsack game with three investors.