Abstract
Sponsored Search Auctions (SSAs) arguably represent
the problem at the intersection of computer science and economics
with the deepest applications in real life. Within the realm of SSAs,
the study of the effects that showing one ad has on the other ads,
a.k.a. externalities in economics, is of utmost importance and has so
far attracted the attention of much research. However, even the basic
question of modeling the problem has so far escaped a definitive
answer. The popular cascade model is arguably too idealized to really
describe the phenomenon yet it allows a good comprehension of
the problem. Other models, instead, describe the 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:
firstly, we define a number of general mathematical formulations for
the problem in the attempt to have a rich description of externalities
in SSAs and, secondly, 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.
Original language | English |
---|---|
DOIs | |
Publication status | Published - Aug 2016 |
Event | European Conference on Artificial Intelligence 2016 - The Hague, Netherlands Duration: 29 Aug 2016 → 2 Sept 2016 http://ebooks.iospress.nl/volumearticle/44833 |
Conference
Conference | European Conference on Artificial Intelligence 2016 |
---|---|
Abbreviated title | ECAI 2016 |
Country/Territory | Netherlands |
City | The Hague |
Period | 29/08/16 → 2/09/16 |
Internet address |