Adaptive Budget Allocation for Maximizing Influence of Advertisements

Hatano, Daisuke; Fukunaga, Takuro; Kawarabayashi, Ken-ichi

Adaptive Budget Allocation for Maximizing Influence of Advertisements

Daisuke Hatano, Takuro Fukunaga, Ken-ichi Kawarabayashi

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 3600-3607.

Abstract

The budget allocation problem is an optimization problem arising from advertising planning. In the problem, an advertiser has limited budgets to allocate across media, and seeks to optimize the allocation such that the largest fraction of customers can be influenced. It is known that this problem admits a (1 – 1/e)-approximation algorithm. However, no previous studies on this problem considered adjusting the allocation adaptively based upon the effect of the past campaigns, which is a usual strategy in the real setting. Our main contribution in this paper is to analyze adaptive strategies for the budget allocation problem. We define a greedy strategy, referred to as the insensitive policy, and then give a provable performance guarantee. This result is obtained by extending the adaptive submodularity, which is a concept studied in the context of active learning and stochastic optimization, to the functions over an integer lattice.

Daisuke Hatano, Takuro Fukunaga, and Ken-ichi Kawarabayashi. 2016. Adaptive Budget Allocation for Maximizing Influence of Advertisements. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 3600–3607. https://ijcai.org/proceedings/2016/507

@inproceedings{ijcai2016p507,
  title     = {Adaptive Budget Allocation for Maximizing Influence of Advertisements},
  author    = {Hatano, Daisuke and Fukunaga, Takuro and Kawarabayashi, Ken-ichi},
  booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
               Artificial Intelligence, {IJCAI-16}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Subbarao Kambhampati},
  pages     = {3600--3607},
  year      = {2016},
  month     = {7},
  url       = {https://ijcai.org/proceedings/2016/507},
}

TY  - CPAPER
TI  - Adaptive Budget Allocation for Maximizing Influence of Advertisements
AU  - Hatano, Daisuke
AU  - Fukunaga, Takuro
AU  - Kawarabayashi, Ken-ichi
T2  - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2016
SP  - 3600
EP  - 3607
UR  - https://ijcai.org/proceedings/2016/507
ER  -