Abstract
We study optimal advertisement allocation in native stream advertising, which exhibits notable fundamental differences from traditional web advertising. Our model highlights the influence of distance between consecutively projected ads on user engagement, which implies interesting negative externalities between ads: when there are fewer intervening posts between two ads, there is higher ad fatigue and lower user engagement. We study the problem of advertisement selection and placement in a stream so as to maximize social welfare. We fully characterize the computational complexity of the problem by demonstrating that it is tightly connected to a special form of interval scheduling. Next, we prove that it is strictly NP-hard (SNP-hard) but can be efficiently approximated to within 1 / 2 of the optimum. We complement this result by studying the mechanism design variant of the problem and develop a 1 / 2-approximation truthful-in-expectation mechanism. We also consider mechanisms that guarantee a stronger deterministic form of truthfulness. We believe that these results lay a valuable theoretical foundation for further research in the field.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Business Insider. Native ads will drive \(74\%\) of all ad revenue by 2021 (2016). http://www.businessinsider.com/the-native-ad-report-forecasts-2016-5
Lahaie, S., Pennock, D.M., Saberi, A., Vohra, R.V.: Sponsored search auctions. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory, chapter 28. Cambridge University Press (2007)
Ghosh, A., Mahdian, M.: Externalities in online advertising. In: 17th WWW, pp. 161–168 (2008)
Kempe, D., Mahdian, M.: A cascade model for externalities in sponsored search. In: 4th WINE, pp. 585–596 (2008)
Kuhn, H.W.: The hungarian method for the assignment problem. Naval Res. Logist. Q. 2, 83–97 (1955)
Koutsopoulos, I.: Optimal advertisement allocation in online social media feeds. In: 8th HotPOST, pp. 43–48 (2016)
Koutsopoulos, I., Spentzouris, P.: Native advertisement selection and allocation in social media post feeds. In: ECML PKDD, pp. 588–603 (2016)
Ieong, S., Mahdian, M., Vassilvitskii, S.: Advertising in a stream. In: 23rd WWW, pp. 29–38 (2014)
Lalmas, M., Lehmann, J., Shaked, G., Silvestri, F., Tolomei, G.: Promoting positive post-click experience for in-stream yahoo gemini users. In: 21th SIGKDD, pp. 1929–1938 (2015)
Barbieri, N., Silvestri, F., Lalmas, M.: Improving post-click user engagement on native ads via survival analysis. In: 25th WWW, pp. 761–770 (2016)
Zhou, K., Redi, M., Haines, A., Lalmas, M.: Predicting pre-click quality for native advertisements. In: 25th WWW, pp. 299–310 (2016)
Aggarwal, G., Goel, A., Motwani, R.: Truthful auctions for pricing search keywords. In: 7th EC, pp. 1–7 (2006)
Spieksma, F.C.R.: On the approximability of an interval scheduling problem. J. Sched. 2(5), 215–227 (1999)
Bar-Noy, A., Guha, S., Naor, J., Schieber, B.: Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput. 31(2), 331352 (2001)
Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069–1090 (2001)
Erlebach, T., Spieksma, F.C.R.: Interval selection: applications, algorithms, and lower bounds. J. Algorithms 46(1), 27–53 (2003)
Gamzu, I., Koutsopoulos, I.: Native Advertising via Interval Scheduling. https://www.dropbox.com/s/slaog50kf0w8ty0/TR-2018-extended.pdf?dl=0
Groves, T.: Incentives in teams. Econemetrica 41(4), 617–631 (1973)
Nisan, N., Ronen, A.: Computationally feasible vcg mechanisms. JAIR 29, 19–47 (2007)
Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58–73 (1981)
Azar, Y., Gamzu, I.: Truthful unification framework for packing integer programs with choices. In: 35th ICALP, pp. 833–844 (2008)
Lavi, R., Swamy, C.: Truthful and near-optimal mechanism design via linear programming. J. ACM 58(6), 25 (2011)
Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econ. Behav. 35(1–2), 166–196 (2001)
Acknowledgments
I. Koutsopoulos acknowledges the support of the project “Research Reinforcement” by the General Secretariat for Research and Technology (GSRT).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Gamzu, I., Koutsopoulos, I. (2019). Advertisement Allocation and Mechanism Design in Native Stream Advertising. In: Aiello, L., Cherifi, C., Cherifi, H., Lambiotte, R., Lió, P., Rocha, L. (eds) Complex Networks and Their Applications VII. COMPLEX NETWORKS 2018. Studies in Computational Intelligence, vol 813. Springer, Cham. https://doi.org/10.1007/978-3-030-05414-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-030-05414-4_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-05413-7
Online ISBN: 978-3-030-05414-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)