  The popular generalized second price (GSP) auction for sponsored search is
built upon a separable model of click-through-rates that decomposes the
likelihood of a click into the product of a "slot effect" and an "advertiser
effect" --- if the first slot is twice as good as the second for some bidder,
then it is twice as good for everyone. Though appealing in its simplicity, this
model is quite suspect in practice. A wide variety of factors including
externalities and budgets have been studied that can and do cause it to be
violated. In this paper we adopt a view of GSP as an iterated second price
auction (see, e.g., Milgrom 2010) and study how the most basic violation of
separability --- position dependent, arbitrary public click-through-rates that
do not decompose --- affects results from the foundational analysis of GSP
(Varian 2007, Edelman et al. 2007). For the two-slot setting we prove that for
arbitrary click-through-rates, for arbitrary bidder values, an efficient
pure-strategy equilibrium always exists; however, without separability there
always exist values such that the VCG outcome and payments cannot be realized
by any bids, in equilibrium or otherwise. The separability assumption is
therefore necessary in the two-slot case to match the payments of VCG but not
for efficiency. We moreover show that without separability, generic existence
of efficient equilibria is sensitive to the choice of tie-breaking rule, and
when there are more than two slots, no (bid-independent) tie-breaking rule
yields the positive result. In light of this we suggest alternative mechanisms
that trade the simplicity of GSP for better equilibrium properties when there
are three or more slots.
