A competitive analysis of online failure-aware assignment

Mengjing Chen, Pingzhong Tang, Zihe Wang, Shenke Xiao, Xiwang Yang
Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, PMLR 180:317-325, 2022.

Abstract

Motivated by a new generation of Internet advertising that has emerged in the live streaming e-commerce markets (e.g., Tiktok) over the past five years, we study a variant of online bipartite matching problem: advertisers send ad requests to influencers (aka, key opinion leaders) on a social media platform. Each influencer has a maximum number of ad requests she can accommodate. We assign a fixed number of influencers to an advertiser when she enters the platform. The advertiser then matches with each of the assigned influencers with a probability, which can be thought of as a set of negotiations between the advertiser and the set of assigned influencers. Unlike the standard online assignment problems, the outcome of any of these matches is not revealed throughout the session (negotiations take time). Our goal is to maximize the expected number of matches between advertisers and influencers. We put forward a new deterministic algorithm with a competitive ratio of $1/2$ and prove that no deterministic algorithm can achieve a better competitive ratio. We also show that the competitive ratio can be improved when randomness is allowed. We then study a setting where a match is successful with either probability 0 or a fixed $p$. We present an optimal randomized algorithm that achieves a competitive ratio of $1-1/e$ in this setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v180-chen22a, title = {A competitive analysis of online failure-aware assignment}, author = {Chen, Mengjing and Tang, Pingzhong and Wang, Zihe and Xiao, Shenke and Yang, Xiwang}, booktitle = {Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence}, pages = {317--325}, year = {2022}, editor = {Cussens, James and Zhang, Kun}, volume = {180}, series = {Proceedings of Machine Learning Research}, month = {01--05 Aug}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v180/chen22a/chen22a.pdf}, url = {https://proceedings.mlr.press/v180/chen22a.html}, abstract = {Motivated by a new generation of Internet advertising that has emerged in the live streaming e-commerce markets (e.g., Tiktok) over the past five years, we study a variant of online bipartite matching problem: advertisers send ad requests to influencers (aka, key opinion leaders) on a social media platform. Each influencer has a maximum number of ad requests she can accommodate. We assign a fixed number of influencers to an advertiser when she enters the platform. The advertiser then matches with each of the assigned influencers with a probability, which can be thought of as a set of negotiations between the advertiser and the set of assigned influencers. Unlike the standard online assignment problems, the outcome of any of these matches is not revealed throughout the session (negotiations take time). Our goal is to maximize the expected number of matches between advertisers and influencers. We put forward a new deterministic algorithm with a competitive ratio of $1/2$ and prove that no deterministic algorithm can achieve a better competitive ratio. We also show that the competitive ratio can be improved when randomness is allowed. We then study a setting where a match is successful with either probability 0 or a fixed $p$. We present an optimal randomized algorithm that achieves a competitive ratio of $1-1/e$ in this setting.} }
Endnote
%0 Conference Paper %T A competitive analysis of online failure-aware assignment %A Mengjing Chen %A Pingzhong Tang %A Zihe Wang %A Shenke Xiao %A Xiwang Yang %B Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2022 %E James Cussens %E Kun Zhang %F pmlr-v180-chen22a %I PMLR %P 317--325 %U https://proceedings.mlr.press/v180/chen22a.html %V 180 %X Motivated by a new generation of Internet advertising that has emerged in the live streaming e-commerce markets (e.g., Tiktok) over the past five years, we study a variant of online bipartite matching problem: advertisers send ad requests to influencers (aka, key opinion leaders) on a social media platform. Each influencer has a maximum number of ad requests she can accommodate. We assign a fixed number of influencers to an advertiser when she enters the platform. The advertiser then matches with each of the assigned influencers with a probability, which can be thought of as a set of negotiations between the advertiser and the set of assigned influencers. Unlike the standard online assignment problems, the outcome of any of these matches is not revealed throughout the session (negotiations take time). Our goal is to maximize the expected number of matches between advertisers and influencers. We put forward a new deterministic algorithm with a competitive ratio of $1/2$ and prove that no deterministic algorithm can achieve a better competitive ratio. We also show that the competitive ratio can be improved when randomness is allowed. We then study a setting where a match is successful with either probability 0 or a fixed $p$. We present an optimal randomized algorithm that achieves a competitive ratio of $1-1/e$ in this setting.
APA
Chen, M., Tang, P., Wang, Z., Xiao, S. & Yang, X.. (2022). A competitive analysis of online failure-aware assignment. Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 180:317-325 Available from https://proceedings.mlr.press/v180/chen22a.html.

Related Material