  In many online advertisement (ad) exchanges, ad slots are each sold via a
separate second-price auction. This paper considers the bidder's problem of
maximizing the value of ads they purchase in these auctions, subject to budget
constraints. This 'second-price knapsack' problem presents challenges when
devising a bidding strategy because of the uncertain resource consumption:
bidders win if they bid the highest amount, but pay the second-highest bid,
unknown a priori. This is in contrast to the traditional online knapsack
problem, where posted prices are revealed when ads arrive, and for which there
exists a rich literature of primal and dual algorithms.
  The main results of this paper establish general methods for adapting these
primal and dual online knapsack selection algorithms to the second-price
knapsack problem, where the prices are revealed only after bidding. In
particular, a methodology is provided for converting deterministic and
randomized knapsack selection algorithms into second-price knapsack bidding
strategies, that purchase ads through an equivalent set of criteria and thereby
achieve the same competitive guarantees. This shows a connection between the
traditional knapsack selection algorithm and second-price auction bidding
algorithms, that has not previously been leveraged.
  Empirical analysis on real ad exchange data verifies the usefulness of this
method, and gives examples where it can outperform state-of-the-art techniques.
