IEICE TRANSACTIONS on Information
Sponsored Search Auction Considering Combinational Bids with Externalities
Summary :
Sponsored search is a mechanism that shows the appropriate advertisements (ads) according to search queries. The orders and payments of ads are determined by the auction. However, the externalities which give effects to CTR and haven't been considered in some existing works because the mechanism with externalities has high computational cost. In addition, some algorithms which can calculate the approximated solution considering the externalities within the polynomial-time are proposed, however, it assumed that one bidder can propose only a single ad. In this paper, we propose the approximation allocation algorithm that one bidder can offer many ads considering externalities. The proposed algorithm employs the concept of the combinatorial auction in order to consider the combinational bids. In addition, the proposed algorithm can find the approximated allocation by the dynamic programming. Moreover, we prove the computational complexity and the monotonicity of the proposed mechanism, and demonstrate computational costs and efficiency ratios by changing the number of ads, slots and maximum bids. The experimental results show that the proposed algorithm can calculate 0.7-approximation solution even though the full search can't find solutions in the limited times.
- Publication
- IEICE TRANSACTIONS on Information Vol.E100-D No.12 pp.2906-2914
- Publication Date
- 2017/12/01
- Publicized
- 2017/09/15
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2016AGP0009
- Type of Manuscript
- Special Section PAPER (Special Section on Frontiers in Agent-based Technology)
- Category
- Information Network
Authors
Ryusuke IMADA
Tokyo University of Agriculture and Technology
Katsuhide FUJITA
Tokyo University of Agriculture and Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ryusuke IMADA, Katsuhide FUJITA, "Sponsored Search Auction Considering Combinational Bids with Externalities" in IEICE TRANSACTIONS on Information,
vol. E100-D, no. 12, pp. 2906-2914, December 2017, doi: 10.1587/transinf.2016AGP0009.
Abstract: Sponsored search is a mechanism that shows the appropriate advertisements (ads) according to search queries. The orders and payments of ads are determined by the auction. However, the externalities which give effects to CTR and haven't been considered in some existing works because the mechanism with externalities has high computational cost. In addition, some algorithms which can calculate the approximated solution considering the externalities within the polynomial-time are proposed, however, it assumed that one bidder can propose only a single ad. In this paper, we propose the approximation allocation algorithm that one bidder can offer many ads considering externalities. The proposed algorithm employs the concept of the combinatorial auction in order to consider the combinational bids. In addition, the proposed algorithm can find the approximated allocation by the dynamic programming. Moreover, we prove the computational complexity and the monotonicity of the proposed mechanism, and demonstrate computational costs and efficiency ratios by changing the number of ads, slots and maximum bids. The experimental results show that the proposed algorithm can calculate 0.7-approximation solution even though the full search can't find solutions in the limited times.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2016AGP0009/_p
Copy
@ARTICLE{e100-d_12_2906,
author={Ryusuke IMADA, Katsuhide FUJITA, },
journal={IEICE TRANSACTIONS on Information},
title={Sponsored Search Auction Considering Combinational Bids with Externalities},
year={2017},
volume={E100-D},
number={12},
pages={2906-2914},
abstract={Sponsored search is a mechanism that shows the appropriate advertisements (ads) according to search queries. The orders and payments of ads are determined by the auction. However, the externalities which give effects to CTR and haven't been considered in some existing works because the mechanism with externalities has high computational cost. In addition, some algorithms which can calculate the approximated solution considering the externalities within the polynomial-time are proposed, however, it assumed that one bidder can propose only a single ad. In this paper, we propose the approximation allocation algorithm that one bidder can offer many ads considering externalities. The proposed algorithm employs the concept of the combinatorial auction in order to consider the combinational bids. In addition, the proposed algorithm can find the approximated allocation by the dynamic programming. Moreover, we prove the computational complexity and the monotonicity of the proposed mechanism, and demonstrate computational costs and efficiency ratios by changing the number of ads, slots and maximum bids. The experimental results show that the proposed algorithm can calculate 0.7-approximation solution even though the full search can't find solutions in the limited times.},
keywords={},
doi={10.1587/transinf.2016AGP0009},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - Sponsored Search Auction Considering Combinational Bids with Externalities
T2 - IEICE TRANSACTIONS on Information
SP - 2906
EP - 2914
AU - Ryusuke IMADA
AU - Katsuhide FUJITA
PY - 2017
DO - 10.1587/transinf.2016AGP0009
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2017
AB - Sponsored search is a mechanism that shows the appropriate advertisements (ads) according to search queries. The orders and payments of ads are determined by the auction. However, the externalities which give effects to CTR and haven't been considered in some existing works because the mechanism with externalities has high computational cost. In addition, some algorithms which can calculate the approximated solution considering the externalities within the polynomial-time are proposed, however, it assumed that one bidder can propose only a single ad. In this paper, we propose the approximation allocation algorithm that one bidder can offer many ads considering externalities. The proposed algorithm employs the concept of the combinatorial auction in order to consider the combinational bids. In addition, the proposed algorithm can find the approximated allocation by the dynamic programming. Moreover, we prove the computational complexity and the monotonicity of the proposed mechanism, and demonstrate computational costs and efficiency ratios by changing the number of ads, slots and maximum bids. The experimental results show that the proposed algorithm can calculate 0.7-approximation solution even though the full search can't find solutions in the limited times.
ER -
English
