Sponsored Search Auctions (SSAs) arguably representudthe problem at the intersection of computer science and economicsudwith the deepest applications in real life. Within the realm of SSAs,udthe study of the effects that showing one ad has on the other ads,uda.k.a. externalities in economics, is of utmost importance and has soudfar attracted the attention of much research. However, even the basicudquestion of modeling the problem has so far escaped a definitiveudanswer. The popular cascade model is arguably too idealized to reallyuddescribe the phenomenon yet it allows a good comprehension ofudthe problem. Other models, instead, describe the setting more adequatelyudbut are too complex to permit a satisfactory theoretical analysis.udIn this work, we attempt to get the best of both approaches:udfirstly, we define a number of general mathematical formulations forudthe problem in the attempt to have a rich description of externalitiesudin SSAs and, secondly, prove a host of results drawing a nearly completeudpicture about the computational complexity of the problem.Weudcomplement these approximability results with some considerationsudabout mechanism design in our context.
展开▼
