Cascade model with contextual externalities and bounded user memory for sponsored search auctions

In spite of the considerable research effort devoted to studying externalities in Sponsored Search Auctions (SSAs), even the basic question of modeling the problem has so far escaped a definitive answer. The popular cascade model appears too idealized to really describe the phenomenon yet it allows a good comprehension of the problem. Other models, instead, arguably describe the real setting more adequately but are too complex to permit a satisfactory theoretical analysis. In this work, we attempt to get the best of both approaches: (i) we generalize the cascade model along a number of directions in the attempt to have mathematical formulations that are close to SSAs in the real world and (ii) prove a host of results drawing a nearly complete picture about the computational complexity of the problem. We complement these approximability results with some considerations about mechanism design in our context.