Optimization Lunchtime Seminar
Optimization Lunchtime Seminar
The Knapsack Game
Friday 31 May 2013
Optimizing a company's revenues depends on the strategies of its competitors. With this in mind, we formulate a generalization of the 0-1 knapsack problem as non-cooperative game. Here, there is a set projects for which each player associates a profit and the required investment. Simultaneously, each player decides the projects to invest for such that its budget constraint is satisfied. The rule is simple: a player receives a profit for each of his/her projects proportional to the number of players that chose it. Our work addresses methodologies to compute efficient Nash equilibria for the knapsack game.
Margarida Carvalho and JoÃO PEDRO PEDROSO, INESC Porto and FCUP