TWO-PERSON KNAPSACK GAME

摘要

In this paper, we study a two-person knapsack game. Two investors, each with an individual budget, bid on a common pool of potential projects. To undertake a project, investors have their own cost estimation to be charged against their budgets. Associated with each project, there is a potential market profit that can be taken by the only bidder or shared proportionally by both bidders. The objective function of each investor is assumed to be a linear combination of the two bidders' profits. Both investors act in a selfish manner with best-response to optimize their own objective functions by choosing portfolios under the budget restriction. We show that pure Nash equilibrium exists under certain conditions. In this case, no investor can improve the objective by changing individual bid unilaterally. A pseudo polynomial-time algorithm is presented for generating a pure Nash equilibrium. We also investigate the price of anarchy (the ratio of the worst Nash equilibrium to the social optimum) associated with a simplified two-person knapsack game.