  Most recent papers addressing the algorithmic problem of allocating
advertisement space for keywords in sponsored search auctions assume that
pricing is done via a first-price auction, which does not realistically model
the Generalized Second Price (GSP) auction used in practice. Towards the goal
of more realistically modeling these auctions, we introduce the Second-Price Ad
Auctions problem, in which bidders' payments are determined by the GSP
mechanism. We show that the complexity of the Second-Price Ad Auctions problem
is quite different than that of the more studied First-Price Ad Auctions
problem. First, unlike the first-price variant, for which small constant-factor
approximations are known, it is NP-hard to approximate the Second-Price Ad
Auctions problem to any non-trivial factor. Second, this discrepancy extends
even to the 0-1 special case that we call the Second-Price Matching problem
(2PM). In particular, offline 2PM is APX-hard, and for online 2PM there is no
deterministic algorithm achieving a non-trivial competitive ratio and no
randomized algorithm achieving a competitive ratio better than 2. This stands
in contrast to the results for the analogous special case in the first-price
model, the standard bipartite matching problem, which is solvable in polynomial
time and which has deterministic and randomized online algorithms achieving
better competitive ratios. On the positive side, we provide a 2-approximation
for offline 2PM and a 5.083-competitive randomized algorithm for online 2PM.
The latter result makes use of a new generalization of a classic result on the
performance of the "Ranking" algorithm for online bipartite matching.
