We model the problem of bidding in ad auctions as a penalized multiple choice knapsack problem (PMCKP), a combination of the multiple choice knapsack problem (MCKP) and the penalized knapsack problem (PKP) [1]. We present two versions of PMCKP, GlobalPMCKP and LocalPMCKP, together with a greedy algorithm that solves the linear relaxation of a GlobalPMCKP optimally. We also develop a greedy heuristic for solving LocalPMCKP. Although our heuristic is not optimal, we show that it performs well in TAC AA games.
展开▼
