If you recommend a product to me and I buy it, how much should you be paid by the seller? And if your sole interest is to maximize the amount paid to you by the seller for a sequence of recommendations, how should you recommend optimally if I become more inclined to ignore you with each irrelevant recommendation you make? Finding an answer to these questions is a key challenge in all forms of marketing that rely on and explore social ties; ranging from personal recommendations to viral marketing. In the first part of this paper, we show that there can be no pricing mechanism that is “truthful” with respect to the seller, and we use solution concepts from coalitional game theory, namely the Core, the Shapley Value, and the Nash Bargaining Solution, to derive provably “fair” prices for settings with one or multiple recommenders. We then investigate pricing mechanisms for the setting where recommenders have different “purchase arguments”. Here we show that it might be beneficial for the recommenders to withhold some of their arguments, unless anonymity-proof solution concepts, such as the anonymity-proof Shapley value, are used. In the second part of this paper, we analyze the setting where the recommendee loses trust in the recommender for each irrelevant recommendation. Here we prove that even if the recommendee regains her initial trust on each successful recommendation, the expected total profit the recommender can make over an infinite period is bounded. This can only be overcome when the recommendee also incrementally regains trust during periods without any recommendation. Here, we see an interesting connection to “banner blindness”, suggesting that showing fewer ads can lead to a higher long-term profit.
In typical literature on sponsored search auctions @cite_1 @cite_16 it is assumed that the web search engine is optimizing its expected profit and that its expected profit for showing a particular ad is the ad's click-through-rate (CTR) multiplied by the price the advertiser will be charged when her ad gets clicked. Usually, only a single round is considered or, when there are budget constraints @cite_6 @cite_3 , the CTRs are assumed to be during the duration of the game. If, however, it is assumed that CTRs drop for ads for each unsuccessful advertisement shown then, in the long run, this puts more emphasis on showing ads with high CTR, regardless of how much their advertisers can be charged for a single click. Although different objective functions for the search engine have been considered @cite_6 , the setting of profit maximization with trust decay has not been studied and we deem this an interesting area for future work.
@cite_3 @cite_16 @cite_1 @cite_6
2119914577 2088532256 1735712825 2086561196
Internet search companies sell advertisement slots based on users' search queries via an auction. While there has been previous work onthe auction process and its game-theoretic aspects, most of it focuses on the Internet company. In this work, we focus on the advertisers, who must solve a complex optimization problem to decide how to place bids on keywords to maximize their return (the number of user clicks on their ads) for a given budget. We model the entire process and study this budget optimization problem. While most variants are NP-hard, we show, perhaps surprisingly, that simply randomizing between two uniform strategies that bid equally on all the keywordsworks well. More precisely, this strategy gets at least a 1-1 e fraction of the maximum clicks possible. As our preliminary experiments show, such uniform strategies are likely to be practical. We also present inapproximability results, and optimal algorithms for variants of the budget optimization problem. Billions of dollars are spent each year on sponsored search, a form of advertising where merchants pay for placement alongside web search results. Slots for ad listings are allocated via an auction-style mechanism where the higher a merchant bids, the more likely his ad is to appear above other ads on the page. In this paper we analyze the incentive, efficiency, and revenue properties of two slot auction designs: "rank by bid" (RBB) and "rank by revenue" (RBR), which correspond to stylized versions of the mechanisms currently used by Yahoo! and Google, respectively. We also consider first- and second-price payment rules together with each of these allocation rules, as both have been used historically. We consider both the "short-run" incomplete information setting and the "long-run" complete information setting. With incomplete information, neither RBB nor RBR are truthful with either first or second pricing. We find that the informational requirements of RBB are much weaker than those of RBR, but that RBR is efficient whereas RBB is not. We also show that no revenue ranking of RBB and RBR is possible given an arbitrary distribution over bidder values and relevance. With complete information, we find that no equilibrium exists with first pricing using either RBB or RBR. We show that there typically exists a multitude of equilibria with second pricing, and we bound the divergence of (economic) value in such equilibria from the value obtained assuming all merchants bid truthfully. We discuss an auction framework in which sponsored search advertisements are delivered in response to queries. In practice, the presence of bidder budgets can have a significant impact on the ad delivery process. We propose an approach based on linear programming which takes bidder budgets into account, and uses them in conjunction with forecasting of query frequencies, and pricing and ranking schemes, to optimize ad delivery. Simulations show significant improvements in revenue and efficiency.