Auction mechanisms for preference driven ad exchanges

Abstract

In this paper we concentrate on ad exchange mechanisms that take into consideration the publishers’ preferences concerning the attributes of ads published in their ad space, in addition to their desire to earn money from the ads. We suggest allocation (ad placement) and pricing protocols which take into account preferences of both the publishers and the advertisers. The most promising protocol, the Weighted Bipartite Hungarian VCG protocol, collects the preferences of the auction’s participants and uses the Hungarian algorithm to maximize a weighted function of their preferences. Simulations show that this advantageous protocol can maintain a balanced budget over time while preserving most of the desired economic properties (e.g., individual rational, and truth telling), and reaches near optimal solutions.

Keywords

Agent-based marketplaces auction markets ad exchanges

1. Introduction

Most of the information on the World Wide Web, from its emergence till the present, is available at no charge. However, there are operational and managing costs behind these free information provider websites. Allowing advertisements on websites can be a great alternative to cover such costs and can even be beneficial for website owners also in terms of profit. However, we tend to forget that behind the websites there are self-interest entities, institutions, organizations or businesses, who naturally have their own preferences and interests concerning ads placed and shown on their site, beyond the immediate payment they receive for displaying them.

This question is interesting in the scope of a single website that has to decide which ads to show. Nonetheless it becomes even more challenging in the scenario of Ad Exchanges, in which multiple website owners (publishers) willing to dedicate space to ads, and multiple entities (i.e., advertisers) willing to publicize their advertisements, are brought to a common, automatic marketplace [28]. We call this problem the preference driven ad exchange, since the preferences of the participants are considered and respected by the auctioneer when calculating the auction outcome.

This research problem is applicable in various important domains and situations. Consider an illustrative scenario of a bakery Website. The bakery may have a positive incentive to show ads of complementary products, such as spreads; it might be neutral toward ads about bakery accessories, but it will certainly be opposed to ads of another bakery appearing on its website. The keyword bread, however, may appear in these three types of ads. Nevertheless, the keyword bakery may appear in the two latter types of advertisements (the neutral and contradicting ads). Consequently, an algorithm for matching ads to Websites based on specified keywords may disregard the preferences of the Website owners (whom we term publishers). Hence, a solution is required for ad exchange markets where website owners (sellers of ad slots) are given the ability to specify their detailed preferences concerning the ads shown on their websites.

Even a non-profit organization, may be easily convinced to put ads or links to related sites that do not clash with its purposes and goals, on its Website. For example, a site for home education (homeschooling) would not be interested in placing ads of formal or private schools on its site, even though there might be a similarity based keyword matching homeschooling with formal schools. Likewise, a political party’s website would be dissatisfied with having ads of other political parties shown on its site even though they might share similar or even identical aims and keywords.

In spite of the importance of this issue, as described in Section 2, most of the real world applications for ad exchange markets, as well as most of the current research, the choice of ads displayed on a certain private Website is made without, or relatively little consideration of the publisher’s preferences of the ads shown on his Website.

In this paper, we consider the ad-exchange problem with multiple advertisers and multiple publishers, where each publisher is interested in selling multiple ad slots, and we consider both sides’ preferences concerning the ad allocation. Our goal is to increase the satisfaction of all the participants in the auction, by using an efficient, fair and truthful protocol for the decision about the ad allocation and pricing.

The desirable protocol we suggest for this purpose, namely the Weighted Bipartite Hungarian VCG protocol termed the Weighted Bipartite HVCG, is based on the Affine Maximizer Auction and the Virtual Valuations Combinatorial auction mechanisms [24]. In particular, the Weighted Bipartite HVCG is a promising mechanism, reaching truthful bids, a balanced auctioneer’s budget in the long run, and near optimal results. This protocol is based on the Hungarian algorithm for the assignment problem combined with the Vickery-Clarks-Grove Protocol, and it assumes the existence of a centralized auctioneer. According to our developed Weighted Bipartite HVCG protocol, both, publishers and advertisers send the auctioneer their private preferences, and the auctioneer computes the optimal assignment using the Hungarian mapping algorithm, and then determines the payment required by each advertiser and the credit allotted to each publisher by applying the Vickery-Clarks-Grove payment rule.

Nonetheless, according to the Weighted Bipartite HVCG protocol, the utilities of the publishers that are considered in the utility function, which is maximized, are multiplied by a positive parameter ( $1+w$ ) in order to balance the auctioneer’s budget, and reach a positive expected revenue for the auctioneer.

We compared the properties and results of the Weighted Bipartite HVCG to the following protocols: (a) Classical Hungarian $+$ Vickery-Clarks-Grove protocol [4], which is used only for comparison since it does not maintain a balanced budget for the auctioneer and is therefore not applicable in real world applications. (b) Distributed Reallocation Protocol (DRP), which we developed for the ad exchange scenarios, takes into account the publishers’ preferences, whereby the mapping of ads to publishers is randomly initialized, and then iteratively, pairs of publishers are randomly chosen to exchange ads (if possible) in a way that is beneficial for both. The advantage of the Distributed Reallocation Protocol is the fact it is distributed and it is incentive compatible. However, the weighted HVCG achieves more efficient results.

We compared the Weighted Bipartite HVCG to the other protocols with respect to: (1) time complexity, (2) efficiency of the derived allocation, (3) budget balanced, (4) individually rational, and (5) being truthful. We found that with the Weighted Bipartite HVCG, the auctioneer has the ability to control the balance in the long term (i.e., in the short term, the auctioneer’s balance might be negative), at a minor expense of 1%–2% of loss of its optimality. Namely, the protocol achieves 98%–99% of the optimal allocation (when considering the sum of utilities of both publishers and advertisers), and these results were much better than the results reached by the other protocols considered. Moreover, the Weighted Bipartite HVCG still maintains the truthful property of the classical Vickery-Clarks-Grove protocol, as well as the individually rational property, in the sense that no participant loses by participating. Its sole drawback is that it is a centralized mechanism.

We proceed by describing several related existing protocols. We discuss how to adapt each of them for the ad exchange mechanisms, where the publishers’ preferences are taken into account, and we analyze their economic properties. Specifically we consider the following protocols: (a) the Simultaneous English Auction, (b) the advertisers initiated Gale and Shapley protocol, (c) the publishers initiated Gale and Shapley protocol, (d) the Generalized Second Price protocol, and the (e) advertisers’ aimed Hungarian Vickery-Clarks-Grove, where the assignment algorithm maximizes the advertisers’ preferences, while keeping the bid requirements of the minimum bid of the publishers.

The paper is structured as follows. In Section 2 we review the current state of the art and provide description of the auction protocols taken from the literature. In Section 3 we describe the publishers’ and advertisers’ market model and discuss the different auction mechanisms developed or adapted for preference driven ad exchange, and in particular, in Section 3.2.2 we describe the Weighted Bipartite HVCG details and properties. In Section 4 we compare the different algorithms’ properties, and we proceed by describing simulation results of the different protocols. Finally, in Section 5 we discuss our conclusions and propose directions for future work.

2. Literature review

The purpose of the current section is to describe relevant research and to position our research problem within the context of the current state of the art.

In this paper, we consider the ad-exchange problem, where both publishers and advertisers have preferences concerning ad allocations. Our goal is to increase the satisfaction of all the participants in the auction, by using an efficient, fair and truthful protocol for the ad assignment and for ad pricing.

There are multiple real world examples of Ad Exchanges, in which multiple websites (publishers) willing to dedicate space to ads, and multiple entities (i.e., advertisers) willing to publicize their advertisements, are brought to a common, automatic marketplace [28]. Such ad exchange markets include RightMedia [33], adBrite [2], openX [32] and Google’s DoubleClick [19, 20]. However, in most real applications for ad exchange markets, the choice of advertisements displayed on a certain private Website is made without taking into consideration the ranking preferences regarding the ads shown on the Website. Though Google DoubleClick uses a protocol that considers the publishers’ preferences it does so in a limited way, as described in Section 2.1.6.

Furthermore, the research that considers self-interested Website publishers with preferences about their ad-assignments in the online ad market, does so in a very limited way by assuming: (i) a single publisher [7, 12], (ii) a single type of item for sale [3, 4], or (iii) expressive bidding language for the bidders [6]. Beyond the abovementioned limitations, none of the previous work has dealt with the issue of taking into account the preferences of the publisher who sells the ad slots on his private site. This is despite the fact that it may be crucial that an ad’s content suits the website owner’s preferences.

Most of the other existing research [14, 37, 23] on Web advertising auctions focuses on sponsored search auctions and does not directly consider the self-interested Website advertising market. The difference lies in the fact that in sponsored search research the underlying goal is to maximize the interests of the searcher which in turn maximizes the probability of a click on the ad, and such a goal may often contradict the website owner’s motivation, when considering advertisements of similar but competitive companies and organizations.

The situation we consider is also different from double auctions with regular buyers and sellers [12, 15], for the following reasons: (a) In our domain, each publisher “sells” unique items (slots located on his Website) while in a regular market, the same item may have multiple identical copies and may be sold by different sellers. (b) As explained above, in our domain each publisher cares about the ads that will appear on his website, while in a regular market, the seller cares only about the price he will obtain and not about the buyer of the item.

2.1 Related auction mechanisms and protocols

We proceed by describing some related work on auction mechanisms and protocols, which were adapted, or can be adapted, for our ad exchange scenarios where the publishers’ preferences are considered for the ad assignment task.

2.1.1 The Vickery-Clarks-Grove and its variations

The Vickery-Clarks-Grove mechanism [21, 31] is the most common mechanism that promises truthful reporting of preferences of the players. It is known to be efficient, individually rational (IR) and truthful. However, it is not budget balanced. Namely, the sum of incomes is not necessarily equal to the payments. This makes this mechanism inapplicable since no self-interested rational auctioneer would be interested in a deficit in the market. Myerson and Satterthwaite [29] proved that no budget-balanced mechanism that is also Pareto-efficient and incentive compatible exists for the general social choice problem. Thus, previous attempts to modify the Vickery-Clarks-Grove mechanism in a way that would make it budget balanced and truthful, include solutions that achieve either sub-optimal solutions, such as those suggested by [8] or [15], or finding solutions for sub-problems where a redistribution scheme may be used, such as [9, 22, 30].

The Affine Maximizer Auction [34] is another variation of Vickery-Clarks-Grove mechanism, which makes linear transformations from the participants’ valuations, resulting in a dominant strategy incentive compatible mechanism for the combinatorial auction domain. A subset of Affine Maximizer Auction, called the Virtual Valuation combinatorial auction, was used by Likhodedov and Sandholm [25] for the combinatorial auction. In the Virtual Valuations Combinatorial auction, each bidder’s valuation is multiplied by a predefined weight. The resulting mechanism is a type of Affine Maximizer Auction, thus it is incentive compatible, and the weights’ values can be chosen to maximize the expected revenue of the seller in the combinatorial auction.

In our research, we developed the Weighted Bipartite HVCG, which is, in fact, a variation of the Virtual Valuations Combinatorial auction, which is not budget, balanced. We show that the Weighted Bipartite HVCG mechanism ensures the auctioneer’s budget is balanced over time, while keeping the truthful property and keeping near optimal allocation results. The details of the Weighted Bipartite HVCG are provided in Section 3.2.2 and a theoretical and simulation comparison with other auction protocols is provided in Section 4.

2.1.2 The laddered auction and its use in the distributed reallocation protocol

Aggarwal et al. [3] developed a new incentive-compatible auction, named the Laddered auction, assuming a situation in which one publisher exists. According to the Laddered auction, the mechanism calculates the price and the number of clicks each advertiser could have attracted in each of the possible lower places (with regard to the winning place). Once the winning place of an advertiser is determined, the mechanism summarizes the prices of the bids, weighed by the relative Click Through Rate achieved by each slot, from the bottom of the available slots’ list to its winning slot, and charges the advertiser the lowest price for the number of clicks he could have attracted in the lowest place and then the next higher price for the next bids, etc.

Two variations of the laddered auction were proposed in [12] in order to solve the problem of ad allocation and pricing for the case of a single publisher who is also the auctioneer. However, the solutions proposed in [12, 7] are not appropriate for the case of multiple and possibly manipulative publishers (Website owners). This is due to the fact that the Laddered and Greedy-Laddered schemes used in [12, 7] are inadequate when there are manipulations on the part of the publisher’s side. For example, the publishers themselves may deviate from their true scoring/ranking function in order to achieve higher gains.

Thus, for the multiple publishers’ case, we developed a more complex protocol, called the Distributed Reallocation Protocol, that is incentive compatible for the publishers as well (which overcomes the drawback of the laddered auction’s variations). According to this protocol, initial allocation of ads to publisher is randomly determined by the auctioneer, and then, pairs of publishers are randomly chosen to negotiate about possible ad replacement in a way that is beneficial for both. The pricing mechanism used by the Distributed Reallocation Protocol is the original laddered pricing protocol, which ensures truthful bids of the advertisers. Other details of the Distributed Reallocation Protocol, including the Distributed Reallocation Protocol properties, are described in Section 3.2.3.

2.1.3 The Simultaneous English Auction

The Simultaneous English Auction, in the literature termed the Simultaneous Ascending Auction [10], is an auction for similar multiple items, in which at each round, bidders simultaneously make sealed bids for the items in which they are interested. After each round, results are posted, and for each item, the minimum price is set according to the highest bid of the last round, plus a predefined increment. The simultaneous ascending auction was introduced in 1994 to sell licenses to use radio spectrum bands in the USA [26]. The simultaneous ascending auction was also suggested for the combinatorial auction [11], in which the bidder bids for a bundle of items the buyer wants to buy together.

When applying the Simultaneous English Auction to the preference driven ad exchange domain, each publisher has to announce a scoring function and then Simultaneous English Auctions are run by the different publishers, where each advertiser can decide in which auction to participate and what price to bid. Finally, the winning ad is determined by the ad that has the maximum sum of the bids plus scoring function. However, when we ask each publisher to describe its rule, the publisher may have incentives to manipulate its rule, thus, the protocol is not truthful from the publishers’ side. The details of the Simultaneous English auction, as well as its properties, are described in Section 3.2.4.

2.1.4 Gale and Shapley protocol

Gale and Shapley [18] considered the stable marriage problem, which is the problem of finding a stable match between two equally sized sets of elements given an ordering of preferences for each element. A match is stable when no match ( $A$ , $B$ ) exists whereby both $A$ and $B$ would be individually better off than they are with the element to which they are currently matched. The algorithm suggested by Gale and Shapley involves a number of iterations, and its complexity is $O(n^{2})$ where $n$ is the size of each set.

In order to adapt the Gale and Shapley algorithm to the preference driven ad exchange domain, we have to consider the following details:

How to extend the smaller set to be equal-size sets.

Which of the sets (set of advertisers or set of publishers) will be the side that proposes.

How to incorporate a pricing mechanism that does not include the original Gale and Shapley algorithm.

In Section 3.2.5 we describe all these issues, and suggest how the Gale and Shapley algorithm is applied to the preference driven ad exchange domain, and in Section 4 we compare its theoretical properties and its simulation outcome with respect to the other suggested protocols.

2.1.5 The Generalized Second Price auction

The Generalized Second Price auction is the most common auction used in the Web. The Generalized Second Price auction is similar to the second price auction, where the winner of each slot pays the price of the next bid for this slot. However, while the second price auction is known to be truthful, the Generalized Second Price is not [14, 13]. Namely, truth telling about the real value of a click with regard to a certain keyword is not optimal for an advertiser.

Athey and Ellison [6] analyzed a model of a Generalized Second Price auction for sponsored links in a search engine, where each advertiser has a privately known quality, and each consumer (a search engine user) tries to find the advertisers that match his need, where high quality firms are more likely to meet each consumer’s need. In contrast, in our work a third party is introduced into the allocation mechanism, which is the private publisher that hosts the ads. In other words, our mechanism is concerned with the preferences of both the publisher and the advertiser. Moreover, the value of an ad can be different for different publishers, and not directly dependent on a quality parameter known to the advertiser as in their model.

Abrams and Schwarz [1] considered sponsored keyword auctions where the user’s future propensity to click on ads is taken into account and it is directly influenced by his past experience with clicks. Namely, an ad with a disappointing quality of the landing page imposes a negative externality on the search engine due to the fact that the future stream of revenue from this user will be reduced. This externality is referred to as a hidden cost. Abrams and Schwarz suggest the hidden cost Generalized Second Price, which takes into account the hidden costs caused by the quality parameter of each ad. In particular, for the single slot case, they suggest a compensation scheme for advertisers based on the experience quality they provide a user. Our study also incorporates compensation to advertisers that contributes to the publishers where their ads are displayed. However, we use different auction mechanisms due to the existence of private information of both the advertisers and the publishers, which is not assumed in the work of Abrams and Schwarz. Moreover, we consider a multiple slots model, for which the Generalized Second Price protocol as well as the hidden cost Generalized Second Price protocol are not incentive compatible.

Yang et al. [37] considered two ways of combining reserve prices in the auction: the generalized second-price auction where the winner of the last ad position pays the larger value between the highest losing bid and the reserve price, and the Generalized Second Price with a posted reserve price (APR) where the winner of the last position pays the reserve price. They examined the effect of different environment parameters on the optimal reserve price that maximizes the Search engine’s expected revenue. Their work can be used by a publisher participating in a non-incentive compatible protocol in order to find which reserve price to publicize. Note, however, that if the auction protocol is incentive compatible, the publisher will publicize his real cost from storing the ad as his reserve price, and this will be his optimal strategy.

In Section 3.2.6 we analyzed the Generalized Second Price properties for the preference driven ad exchanges, and we found that it is not truthful for both sides. For comparison reasons we implemented it assuming that participants (publishers and advertisers) must report true values, and in Section 4 we found via simulations that the Generalized Second Price was outperformed by most of the other protocols compared, as shown in Tables 2, 3 and 5.

2.1.6 The advertisers’ aimed HVCG

In the Google DoubleClick Ad Exchange system [19, 20], the publisher can control his environment in the following ways: (a) Open Auction Pricing: the publisher is able to fix different CPMs (cost per impression) for different users or type of users, and in this way, he can restrict the appearances of the ads of his competitors. (b) Set blocking rules: the publisher can block particular URLs or particular sensitive categories (keywords) from appearing on his Website. (c) Opt-in: explicitly allow certain ad technologies and categories that are blocked by default. (d) Ad style and back up ads.

The way Google DoubleClick handles irrelevant or competitive ads is by setting a high minimum required bid in order to be able to participate in the auction. However, after fulfilling this limitation, the competitive ad can participate in the ad auction like any other ad. In contrast, in our research the competitive ad is kept in a lower position by remembering the negative utility of the Website from this ad. Thus, our mechanism is able to better match the Website preferences relative to the way Google DoubleClick does. In fact, the Advertisers’ Aimed HVCG, described in Section 3.2.7, is analogous to the protocol used by Google DobuleClick, and in Section 4 we show that it was found to be less efficient than most of the other auction protocols. Note, however, that Google does not publicize all the details concerning the way DoubleClick was implemented, and the exact details of the variation Google uses is not known to us.

2.2 Bidding strategies in non-incentive-compatible auctions

Recent work on bidding strategies includes the work by Xu et al. [36], who studied how an advertiser changes his bid prices in a sponsored search, by modeling his rationality. They considered different levels of rationality of advertisers, and they modeled advertisers’ behaviors using a parametric model, and applied machine learning techniques to learn the parameters in the model. Simulations using history data samples of a sponsored search log showed that the techniques used by Xu et al. lead to a very accurate bid prediction, with respect to other strategies suggested in the literature.

The bidding strategy they used can be applied in situations where the auction protocol does not promise truthful bids, such as the first price sealed bid or Generalized Second Price for the multi slot auction. Thus, they can be applied by some of the non-incentive compatible protocols, such as the English, the Gale and Shapley and the Generalized Second Price auctions, Note, however, that machine learning techniques can be used to reveal the advertiser’s expected utility from a clicked ad and to find the Publisher’s utility from the ad. We leave this direction of research for future work.

2.3 Summary of the literature review

To summarize, we described the literature that was the base of our developments. As can be shown, very little work was done when considering the situation of preference driven ad exchanges, in which the participants have preferences about the ad allocation properties. However, several related works concerning research about protocols and strategies for keyword auctions in search engines exist, and in our work, we adapt these protocols and strategies for the preference driven ad exchanges.

3. The preference driven ad exchange model and the proposed auction mechanisms

3.1 Description of the environment

We consider a model where $M$ publishers (sellers), each denoted by $\textit{Pub}_{j}^{*}$ , dedicate space on their websites to advertisements. In addition, $N$ Advertisers (buyers), denoted $A_{i}$ , compete for these spaces. For simplicity, we assume each publisher dedicates $K$ ad slots on his website.

Each participant in the ad exchange environment is characterized by multiple values. We start by characterizing an advertiser and then we continue to define a publisher.

3.1.1 The characteristics of the advertiser

Click Through Rate (CTR): $\textit{CTR}_{i}(k,j)$ indicates the click through rate $A_{i}$ will attract by being placed in slot $k$ of publisher $j$ . Specifically, the click through rate denotes the expected number of times the ad of advertiser $i$ will be clicked when placed in slot number $k$ , out of 100 times that the ad is shown in this particular slot location [3, 4]. Thus, 0 $\leqslant$ CTR ${}_{i}(k,j)\leqslant$ 100 for each advertiser $i$ , publisher $j$ and slot $k$ .

Private value: $V_{i}(j)$ defines the value per click advertiser $A_{i}$ is expecting to gain if the click is from Pub ${}_{j}^{*}$ ’s website. The value $V_{i}(j)$ is the expected utility of the advertiser from future deals and interactions performed by visitors of Website $j$ who clicked on the ad, and its calculation is based on the Website quality and on the keywords’ similarity to the Website’s content.

Bid: Each advertiser, $A_{i}$ , submits a positive bid $B_{i}(j)$ indicating the price it is willing to pay per click on its ad when it is shown on the Website of publisher $j$ . The bid is calculated by the advertiser according to its strategy, given the auction protocol used. Consequently, we will prefer auction protocols that ensure truthful bidding, i.e., protocols in which the bidders are motivated to bid their true private value.

Price: $P_{i}(k,j)$ denotes the price that should be paid by advertiser $A_{j}$ for an ad allocated to slot $k$ of website Pub ${}_{j}$ . This price is determined by the pricing protocol used by the auctioneer, and it depends on the bid of advertiser $A_{i}$ as well as on bids of other advertisers and the scoring function reported by the publishers.

Expected utility: The expected utility of advertiser from being displayed in slot $S_{k}$ of Pub ${}_{j}$ is:

$\textit{EU}_{A_{i}}({\textit{Pub}}_{j},S_{k})=(V_{i}(j)-P_{i}(k,j))\cdot% \textit{CTR}_{i}(k,j)$ (1)

3.1.2 The characteristics of the publisher

Utility per click of the publisher: $U_{j}(i)$ denotes the utility that is obtained by publisher Pub ${}_{j}$ from a click on ad $A_{i}$ . This utility function can actually reflect: (i) the “preferred/allowed” keywords list and the “forbidden/undesired” keywords list, (ii) the quality of the ad, (iii) the aim and type of the Websites the ad is linked to (i.e., competitive or friendly Websites), and (iv) other business and cultural factors.

Note that the value of $U_{j}(i)^{*}$ may be positive or negative. This in turn means that an advertisement that is beneficial to a certain publisher is expressed by a positive utility (for being a complementary product or service). On the other hand, an advertisement that may harm the publisher if it appears on its Website (e.g., a competitive product or service) will result in a negative utility $U_{j}(i)^{**}$ for the publisher. Namely, a negative value of $U_{j}(i)^{*}$ means that Pub ${}_{j}$ prefers not to show ad $A_{i}$ .

Reported utility (scoring function): $R_{j}(i)$ denotes the value that Pub ${}_{j}$ reports as its utility from a click on ad $A_{i}$ . Some of the auction protocols ensure a truthful bidding strategy of the publishers, i.e., $R_{j}(i)=U_{j}(i)$ for each publisher Pub ${}_{j}$ and for each ad $A_{i}$ . Again, as we explained above, we assume the publisher announces one general scoring function, and given the parameters of a particular ad (keywords, quality of the ad, the ad’s links, the type and aim of the ad) the scoring function produces a certain utility for the ad.

To this end, we can define the expected utility of the publishers and of the advertisers from a certain allocation of advertisements to slots on the websites of the publishers.

The existence of a regulator (auctioneer) is needed in order to execute some of the protocols (the centralized protocols), and it is needed in all the protocols, in order to ensure that all participants follow the protocol’s rules.

The expected utility of a publisher: The expected utility of publisher pub ${}_{j}$ , from showing the set of winning ads $\{A_{i_{1}},\ldots,A_{i_{k}}\}$ placed in slots $\{S_{1},\ldots,S_{k}\}$ , correspondingly is:

${\textit{EU}}_{\textit{Pub}_{j}}(A_{i_{1}}\ldots A_{i_{k}})=\sum\limits_{k=1}^% {K}{(p_{i_{k}}(k,j)+U_{i}(j))\cdot\textit{CTR}_{i_{k}}(k,j)}$ (2)

3.1.3 Desired properties of the auction mechanisms

Given this background, next we propose different auction mechanisms, where each includes the allocation rule and the payments rule to determine the prices. Our design goal is to satisfy the following desired economic properties that current state of the art auction mechanisms barely satisfy:

Incentive compatible (ensuring truthful bids).

Efficiency (preferring Pareto efficient allocation).

Computationally efficient (time and space used to compute the allocation and the pricing scheme).

Budget balanced.

Complying with the publisher’s and advertiser’s preferences.

Some of the above criteria may conflict one another as shown in [29]. In particular, the original Vickery-Clarks-Grove protocol is not budget balanced, and in our domain it causes losses over time for the auctioneer. Thus, we suggest the Weighted Bipartite HVCG protocol, described in Section 3.2.2, which is a variation of the Vickery-Clarks-Grove protocol but may reach a balanced budget, and we proceed by proposing other comparable protocols developed or adapted for the preference driven ad exchange environment.

3.2 Auction mechanisms for preference driven ad exchanges

In this section we present some auction mechanisms developed for preference driven ad exchanges. We start in Section 3.2.1 by describing the HVCG (Hungarian $+$ VCG) protocol which is the baseline for the Weighted Bipartite HVCG protocol. We proceed in Section 3.2.2 by describing the weighted bipartite HVCG protocol we developed, which is the most promising protocol for the preference driven ad exchanges. In Section 3.2.3 we describe the Distributed Reallocation Protocol, which is a distributed protocol that we developed for the preference driven ad exchange, and in the rest of this section we present other ad placement mechanisms used for ad exchanges, and we suggest how to adapt them for the preference driven ad exchanges. We consider the following protocols: the Simultaneous English Auction, the Gale and Shapley protocol, the Generalized Second Price, and the advertisers’ aimed HVCG. We describe each mechanism in detail, as well as its advantages and drawbacks. Then, in Section 4, we compare the properties of the different mechanisms, and provide the results of the comparison on a simulation platform.

Figure 1.

The interaction diagram for the HVCG, the Weighted Bipartite HVCG, the Generalized Second Price, and the advertisers’ aimed HVCG protocols.

3.2.1 The HVCG protocol

The Hungarian Vickery-Clarks-Grove protocol (HVCG) is based on the Hungarian algorithm [23, 27] that solves the assignment problem to find an optimal ad-placement combined with a payment scheme based on the Vickery-Clarks-Grove mechanism [21, 31]. When using the HVCG, an optimal solution is reached, and truthful bidding is achieved. We suggest in [12] to use this protocol for the preference driven auctions where one publisher exists, i.e., the auctioneer. However, in ad exchanges where multiple self-interested publishers exist, the HVCG does not maintain the budget balanced property, and thus it cannot by applied in real world situations. Consequently it is used solely for comparison purposes and to provide benchmarking results for the evaluation of other mechanisms’ performances. The HVCG operates as follows:

Algorithm 1: The Hungarian Vickery-Clarks-Grove protocol
1:	Each participant sends its preferences to the auctioneer.
2:	Each publisher Pub ${}_{j}$ , provides the auctioneer with $R_{j}(i)$ , which denotes its reported reward (utility) from a click on ad $i$ , for each ad.
3:	Each advertiser provides the auctioneer with its bid $B_{j}(i)$ .
4:	The auctioneer finds the optimal mapping of ads to publishers using the Hungarian algorithm.
5:	The auctioneer determines the payment of each ad and the income of each publisher by means of the Vickery-Clarks-Grove protocol, in order to ensure truth telling by both the publishers and the advertisers.

The structure of the interaction between the auction’s participants for the HVCG protocol, as well as for other protocols that use a centralized mechanism is specified in Fig. 1.

The advantage of the HVCG protocol is its stability and optimality of its allocation. The truthfulness of the HVCG is inherited from the truthfulness of the original Vickery-Clarks-Grove protocol [21]. The HVCG is individually rational and again it inherited this property from the VCG mechanism. Given that truthful reporting of preferences is promised, and given the fact that the Hungarian algorithm reached the optimal solution [23, 27], we can conclude that the HVCG finds the optimal ad allocation with respect to the entities’ preferences.

Properties of the HVCG Protocol

Truthfulness: Inherited from the Vickery-Clarks-Grove protocol [21].

Individual rationality: Inherited from the Vickery-Clarks-Grove protocol [21].

Time complexity: The time complexity of the HVCG protocol is $O((N+M)[\max\{N,\textit{MK}\}]^{3}$ ), as described below. The Hungarian protocol, that produces the optimal allocation, requires a time complexity equal to the maximum between the rows’ and columns’ numbers to the power of three. Here, the number of rows is $N$ (ads to be allocated) and the number of columns is MK (places where ads can be allocated). Thus, the time complexity of running the Hungarian algorithm is $O([\max\{N,\textit{MK}\}]^{3}$ ).

*According to the Vickery-Clarks-Grove payment calculations, for each participant, the optimal allocation is recalculated assuming it is not part of the allocation. Thus, the above cubic complexity should be multiplied by the number of participants which is $N+M$ , and added to the time of running the optimal solution where all participants are included. Hence the total time is $O(\max(N,$ $\textit{NK})^{3})+(N+M)\max(N,\textit{NK})^{3})=O((N+M)\max(N,\textit{NK})^{3})$ .

Is not budget balanced: The payments of the advertisers are not guaranteed to be equal to the publishers’ gains.

To summarize, the main disadvantage of the* HVCG is the fact that it is not budget balanced, and, in particular, it can yield a deficit for the auctioneer in the long run. Thus, in Section 3.2.2, we present the Weighted Bipartite HVCG, which is a variation of the HVCG protocol, that can guarantee an expected balanced budget of the auctioneer over time, and thus it can be implemented as a solution for the preference driven market domain.

3.2.2 The Weighted Bipartite HVCG

Inspired by mechanisms used in combinatorial auctions such as the Affine Maximizer Auction [34] and the Virtual Valuations Combinatorial auction [24], we developed a modified Vickery-Clarks-Grove protocol that satisfies the budget balanced property, in contrast to the original Vickery-Clarks-Grove mechanism. This property is achieved by trading the optimality of the achieved solution, and the resulting allocation is simply a suboptimal one (however, simulations show that it achieves more than 98% of the optimal solution). According to the Weighted Bipartite HVCG, a tuning parameter, $w$ , exists to control the balance of the market’s auctioneer as we will show in the simulation section (Section 4).

The following steps describe the process of the Weighted Bipartite HVCG:

Algorithm 2: Weighted Bipartite HVCG
1:	Each participant sends the auctioneer its private information.
2:	Each advertiser $A_{i}$ sends its true V ${}_{i}$ function.
3:	Each publisher Pub ${}_{j}$ sends its scoring function R ${}_{j}(i)$ which in this case is identical to the real utility function, $R_{j}(i)=U_{j}(i)$ , since the mechanism is proven to be truthful for all participants (publishers and advertisers).
4:	The auctioneer finds an allocation that achieves the maximum overall utility given that we afford the publishers a higher weight by multiplying their reported values by ( $1+w$ ). That is, the maximization problem in this case should optimize the following equation:

	$X^{}=\sum\limits_{{\textit{pub}}_{j}=1}^{M}(1+w)U_{{\textit{pub}}_{j}}+\sum% \limits_{A_{i}=1}^{N}V_{A_{i}}$ (3) Where $U_{\textit{pubj}}$ is the published utility of publisher pub ${}_{j}$* from the given allocation, and $V_{Ai}$ is the utility of advertiser $A_{i}$ from the allocation (Note that since the protocol is truthful, $U_{\textit{pubj}}=$ $R_{\textit{pubj}}$ and $V_{Ai}=B_{Ai}$ ).
5:	The payments of each advertiser, $A_{i}$ and the credits of each publisher, Pub ${}_{j}$ , are determined by the auctioneer. The payment of each advertiser, $A_{i}$ is: $p_{A_{i}}=\left(\sum\limits_{{\textit{{pub}}}_{i}=1}^{M}(1+w)U_{{\textit{pub}}% _{j}}^{x^{}}+\sum\limits_{A_{j}\neq A_{i}}V_{A_{j}}^{x^{}}\right)\mspace{-5.% 0mu }-\mspace{-5.0mu }\left(\sum\limits_{{\textit{pub}}_{i}=1}^{M}(1+w)U_{{% \textit{pub}}_{j}}^{x_{-A_{i}}^{}}+\sum\limits_{A_{j}\neq A_{i}}V_{A_{j}}^{x_% {-A_{i}}^{}}\right)\mspace{-10.0mu }$ (4) for the credit each publisher, Pub ${}_{j}$ , receives: $\begin{split}\displaystyle p_{{\textit{Pub}}_{j}}&\displaystyle=\left(\left(% \sum\limits_{{\textit{pub}}_{k}\neq{\textit{pub}}_{j}}{\left(1+w\right)U_{{% \textit{pub}}_{k}}^{x^{}}}+\sum\limits_{A_{i}=1}^{N}V_{A_{i}}^{x^{}}\right)% \right.-\\ &\displaystyle\quad\left.\left(\sum\limits_{{\textit{pub}}_{k}\neq{\textit{pub% }}_{j}}{\left(1+w\right)U_{{\textit{pub}}_{k}}^{x_{-{\textit{Pub}}_{j}}^{}}}+% \sum\limits_{A_{i}=1}^{N}{V_{A_{i}}^{x_{-{\textit{pub}}_{j}}^{}}}\right)% \right)\Bigg{/}(1+w)\end{split}$ (5) Where $x^{}$ denotes the optimal allocation found in step 1, and $x_{{-Pub}_{j}}^{}$ / $x_{{-A}_{i}}^{}$ denotes the optimal allocation if publisher Pubj*/advertiser $A_{i}$ is not involved. Note that the difference between the classical Vickery-Clarks-Grove mechanism and the Weighted Bipartite HVCG is in the factor ( $1+w$ ) that is involved both in the allocation optimization criteria and in the payments’ calculation of each participant.

$X^{*}=\sum\limits_{{\textit{pub}}_{j}=1}^{M}(1+w)U_{{\textit{pub}}_{j}}+\sum% \limits_{A_{i}=1}^{N}V_{A_{i}}$ (3)

Where

U_{\textit{pubj}}

is the published utility of publisher pub ${}_{j}$ from the given allocation, and

V_{Ai}

is the utility of advertiser

A_{i}

from the allocation (Note that since the protocol is truthful,

U_{\textit{pubj}}=

R_{\textit{pubj}}

and

V_{Ai}=B_{Ai}

The payments of each advertiser,

A_{i}

and the credits of each publisher, Pub ${}_{j}$ , are determined by the auctioneer. The payment of each advertiser,

A_{i}

is:

$p_{A_{i}}=\left(\sum\limits_{{\textit{{pub}}}_{i}=1}^{M}(1+w)U_{{\textit{pub}}% _{j}}^{x^{*}}+\sum\limits_{A_{j}\neq A_{i}}V_{A_{j}}^{x^{*}}\right)\mspace{-5.% 0mu }-\mspace{-5.0mu }\left(\sum\limits_{{\textit{pub}}_{i}=1}^{M}(1+w)U_{{% \textit{pub}}_{j}}^{x_{-A_{i}}^{*}}+\sum\limits_{A_{j}\neq A_{i}}V_{A_{j}}^{x_% {-A_{i}}^{*}}\right)\mspace{-10.0mu }$ (4)

for the credit each publisher, Pub ${}_{j}$ , receives:

$\begin{split}\displaystyle p_{{\textit{Pub}}_{j}}&\displaystyle=\left(\left(% \sum\limits_{{\textit{pub}}_{k}\neq{\textit{pub}}_{j}}{\left(1+w\right)U_{{% \textit{pub}}_{k}}^{x^{*}}}+\sum\limits_{A_{i}=1}^{N}V_{A_{i}}^{x^{*}}\right)% \right.-\\ &\displaystyle\quad\left.\left(\sum\limits_{{\textit{pub}}_{k}\neq{\textit{pub% }}_{j}}{\left(1+w\right)U_{{\textit{pub}}_{k}}^{x_{-{\textit{Pub}}_{j}}^{*}}}+% \sum\limits_{A_{i}=1}^{N}{V_{A_{i}}^{x_{-{\textit{pub}}_{j}}^{*}}}\right)% \right)\Bigg{/}(1+w)\end{split}$ (5)

Where

x^{*}

denotes the optimal allocation found in step 1, and

x_{{-Pub}_{j}}^{*}

x_{{-A}_{i}}^{*}

denotes the optimal allocation if publisher Pubj/advertiser

A_{i}

is not involved. Note that the difference between the classical Vickery-Clarks-Grove mechanism and the Weighted Bipartite HVCG is in the factor (

1+w

) that is involved both in the allocation optimization criteria and in the payments’ calculation of each participant.

Following the above description of the Weighted Bipartite HVCG, we will now present the properties of this mechanism.

Properties of the Weighted Bipartite HVCG Protocol

(a) Truthfulness – the Weighted Bipartite HVCG is strategy proof, inherited from the Affine Maximizer Auction [34] and the Virtual Valuations Combinatorial auction [24] mechanisms used in the combinatorial auction. The proof for the particular protocol used for ad exchanges is provided in Lemma 1.

Lemma 1. The Weighted Bipartite HVCG is strategy proof.

Proof Use $X^{*}$ to denote the overall value of the optimal allocation when all participants tell the truth.

Similarly let $X^{\wedge}$ denote the optimal allocation value when a particular player deviates from its true value.

By definition $X^{*}\geqslant X^{\wedge}$ .

Consider the case where publisher1 deviates from the truth telling strategy:

Split the total allocation value to be the others’ portion and the publisher’s portion in both cases, when it tells the truth and when it deviates:

$X^{*}=X_{\textit{withoutPublisher}1}^{*}+\left(1+w\right)V_{\textit{true}1}% \geqslant X_{\textit{withoutPublisher}1}^{*}+\left(1+w\right)V_{\textit{false}% 1}=X^{\wedge}$

Now subtract the value of the optimal allocation from both sides when the given publisher is not considered for allocation,

$X_{\textit{withoutPublisher}1}^{*}-X_{-1}^{*}+\left(1+w\right)V_{\textit{true}% 1}\geqslant X_{withoutPublisher1}-X_{-1}^{*}+\left(1+w\right)V_{\textit{false}1}$

Divide both sides by ( $1+w$ ):

$\frac{X_{\textit{withoutPublisher}1}^{*}-X_{-1}^{*}}{1+w}+V_{\textit{true}1}% \geqslant\frac{X_{\textit{withoutPublisher}1}^{\wedge}-X_{-1}^{*}}{1+w}+V_{% \textit{false}1}\\$

The first argument of both sides equals the payment the publisher will receive in both cases according to the payment scheme of the Weighted Bipartite HVCG.

In total, each side of the inequality represents the utility of the publisher if he tells the truth and if he lies, correspondingly.

That is, we prove that by deviating, the publisher will obtain a lower utility and therefore is not incentivized to deviate (truth-telling is its best strategy).

Now for the case of advertiser1 who is attempting to deviate from the truth-telling strategy:

Split the total allocation value into two parts: (i) others’ portion and (ii) the advertiser’s portion, for both cases, when it tells the truth and when he deviates:

$X^{*}=X_{\textit{withoutAdvertiser}1}^{*}+V_{\textit{true}1}\geqslant X_{% \textit{withoutAdvertiser}1}^{*}+V_{\textit{false}1}=X^{\wedge}$

Now, from both sides subtract the value of the optimal allocation when the given advertiser is not considered for allocation,

$X^{*}=X_{\textit{withoutAdvertiser}1}^{*}-X_{-1}^{*}+V_{\textit{true}1}% \geqslant X_{\textit{withoutAdvertiser}1}^{*}-X_{-1}^{*}+V_{\textit{false}1}$

The first argument of both sides equals the payment the advertiser will receive in both cases according to the payment scheme of the Weighted Bipartite VCG.

In total, each side of the inequality represents the utility of the advertiser if it tells the truth and if it lies, correspondingly.

Again, for the advertiser we prove that by deviation it will obtain a lower utility and therefore he is not incentivized to deviate (truth-telling is his best strategy).

(b) Individual rationality: The Weighted Bipartite HVCG is individually rational. The proof is provided in Lemma 2.

Lemma 2. The Weighted Bipartite HVCG protocol is individually rational.

Proof First check that the advertisers are incentivized to participate (i.e., they will incur a non-negative utility). The total value of the optimal allocation given the valuation of a particular advertiser is:

$X^{*}=X_{{\textit{withoutAdvertiser}}_{1}}^{*}+V_{{\textit{{true}}}_{1}}$

Since the allocation rule by definition finds the optimal allocation, the allocation found where advertiser l is included is higher than that when it is not considered. Namely:

$X^{*}\geqslant X_{-1}^{*}$

By the above two formulas we obtain:

$\displaystyle X^{*}=X_{{\textit{withoutAdvertiser}}_{1}}^{*}+V_{{\textit{true}% }_{1}}\geqslant X_{-1}^{*}$ $\displaystyle X_{-1}^{*}-X_{{\textit{withoutAdvertiser}}_{1}}^{*}{\leqslant V}% _{{\textit{true}}_{1}}$

The left side of the inequality stands for the payment advertiser l needs to pay the mechanism. However, evidently in the above equation it is less than its utility, namely its utility is non-negative.

Now we will prove the individual rationality from the publishers’ perspective,

$\displaystyle X^{*}=X_{{\textit{{withoutPublishers}}}_{1}}^{*}{+\left(1+w% \right)U}_{{\textit{true}}_{1}}$ $\displaystyle X^{*}\geqslant X_{-{\textit{Publisher}}_{1}}^{*}$ $\displaystyle X^{*}=X_{{\textit{withoutPublisher}}_{1}}^{*}{+\left(1+w\right)U% }_{{\textit{true}}_{1}}\geqslant X_{-{\textit{Publisher}}_{1}}^{*}$ $\displaystyle{{X}_{-{\textit{Publisher}}_{1}}^{*}-X_{{\textit{withoutPublisher% }}_{1}}^{*}\leqslant\left(1+w\right)U}_{{\textit{true}}_{1}}$ $\displaystyle\frac{{X}_{-{\textit{Publisher}}_{1}}^{*}-X_{{\textit{% withoutPublisher}}_{1}}^{*}}{1+w}\leqslant U_{{\textit{true}}_{1}}$ $\displaystyle X^{*}=X_{{\textit{withoutAdvertiser}}_{1}}^{*}+V_{{\textit{true}% }_{1}}\geqslant X_{-1}^{*}$

In this case $V_{{\textit{true}}_{1}}$ stands for the negative utility, namely, ${-V}_{{\textit{true}}_{1}}$ is the publisher’s given cost (as a positive value).

Now we negate both sides of the inequality:

$\frac{X_{{\textit{withoutPublisher}}_{1}}^{*}-{X}_{-{\textit{Publisher}}_{1}}^% {*}}{1+w}+U_{{\textit{true}}_{1}}\geqslant 0$

This means that the cost is less than the payment the publisher will receive from the advertiser and therefore it will yield the advertiser a positive utility; in other words, it is individually rational.

(c) Time complexity: The time complexity of the Weighted Bipartite HVCG is the same as the time complexity of the HVCG protocol, which is $O((N+M)\max(N,\textit{NK})^{3})$ .

(d) Budget balanced – Existence of Balanced Weight: As we show in the next section the Weighted Bipartite mechanism is budget balanced for the long term and the auctioneer may tune the balance by tuning the parameter $w$ . Note, however, that the auctioneer cannot promise that a certain auction will be balanced, since it does not know the real properties of the participants. However, over time, the auctioneer can learn the weight that will cause its budget to be balanced.

After describing the properties of the weighted bilateral VCG, we continue by comparing it to other auction protocols that can be used for preference driven auctions. In particular, we proceed with the Distributed Reallocation Protocol which is a distributed protocol we developed for the preference driven auction.

3.2.3 Distributed Reallocation Protocol

The Distributed Reallocation Protocol is a distributed truthful protocol that we developed for the allocation and pricing tasks in the preference driven auction. According to the Distributed Reallocation Protocol, the mapping of ads to publishers is randomly initialized, then iteratively, pairs of publishers are chosen arbitrarily, and they may exchange ads between themselves in a way that is effective for both, if possible.

The Distributed Reallocation Protocol proceeds as follows:

Algorithm 3: The distributed reallocation protocol
1:	Each publisher announces its scoring values $R_{j}(i)$ to all advertisers.
2:	According to a random assignment, ads are allocated to publishers.
3:	Each publisher who was assigned ads that achieve a negative utility for it, may leave the mechanism without incurring a cost.
4:	Do:
5:	In a random and iterative manner, at each step, two publishers are chosen;
6:	These selected publishers first search for more preferred ads from the unallocated pool of ads.
7:	Afterwards, both publishers try to consider exchanges such that the utility of at least one of them will increase without reducing the utility of the other publisher. [A possible improvement is to perform this step simultaneously where all publishers are matched in pairs and the matching can be iterated (in the case of an odd number, at each step, one random publisher is left out).]
8:	Until the predefined hard deadline is reached or no significant improvement is possible (i.e., no changes occur after some predefined number of iterations).
9:	At closing time.
10:	The allocation is performed according to the final agreed allocation.
11:	The advertisement payments are determined according to the original laddered auction [2], where the price paid by advertiser $i$ who won slot $k$ of publisher $j$ is: $p_{i}(k,j)=\frac{\sum\limits_{w=k}^{K-1}{{{B}_{\textit{ad-allocated-slot}(w+1)% }(j)\cdot(\textit{CTR}}_{i}(w,j)-{\textit{CTR}}_{i}(w+1,j))}}{{\textit{CTR}}_{% i}(k,j)}$ (6)

Namely, the laddered payment, $p_{i}(k,j)$ , of advertiser $A_{i}$ for being located in slot $k$ with publisher $j$ , is based on the second best bid of the winners located in the slots below, $B_{\textit{ad-allocated-slot}(w+1)}$ where $w$ runs from the current slot downward to the lowest, $k$ (1 is the first position). The payment calculated for each potential click is according to the price of the second highest bid where the payment for each click is laddered. Thus the payment for the first clicks which advertiser $A_{i}$ could win had it been located in the last slot will be according to the price of the next advertiser that did not win and for the additional clicks which it could win had it been placed in the second to last slot the advertiser will pay according to the bid of the winner of the last slot and so forth up to the clicks that the advertiser gained in relation to the slot below it which are according to the price proposed by the winner of the next slot.

Properties of the Distributed Reallocation Protocol

Truthfulness: The Distributed Reallocation Protocol is strategy proof from the viewpoints of the publishers and the advertisers.

This property of being strategy proof from the advertiser’s perspective is due to the fact that the costs of displaying the ads are determined by the Laddered auction which is truthful and is basically a generalization of the second price sealed bid auction that is also strategy proof. From the publishers’ perspective, as (i) the initial allocation is independent of the utilities reported by the publisher, and (ii) the selection of pairs of publishers for a possible exchange is also determined randomly, any possible deviation from reporting the true utility function may cause the publisher to lose an ad it could have won.

Individual rationality: According to the Distributed Reallocation Protocol, no participant may lose by participation.

In the Distributed Reallocation Protocol, the initial random allocation may cause a negative utility for one or more of the publishers, and the consequent replacements and exchange steps do not always compensate for the initial loss. Therefore, as mentioned in step 2 of the Distributed Reallocation Protocol mechanism, such a publisher may leave the mechanism with no charges. Moreover no advertiser is charged more than it proposed according to the Laddered payment scheme. To conclude we can state that the Distributed Reallocation Protocol mechanism satisfies the individual rationality property according to which no participant may receive a negative utility by participation.

Time complexity: The time complexity of the Distributed Reallocation Protocol is:

$O(I*(N-\textit{MK}+\tbinom{2K}{K}K\log K))$

where $I$ indicates the maximum number of iterations permitted.

The first random assignment is assumed to be negligible. Next, for each iteration, two random publishers are chosen, each, first, checks whether one of the unallocated ads is more beneficial for him. The complexity of this stage is $(N-\textit{MK})$ , where $(N-\textit{MK})$ is the number of unallocated ads. In the second stage of each iteration both selected publishers try to search for the best $K$ ads from the $2K$ that are currently assigned to them. There are $\binom{2K}{K}$ such options. Moreover, once the best set of $K$ ads is determined, the optimal ordering of the $K$ ads to the $K$ slots is achieved by sorting them, which requires $O(K\log K)$ time steps.

Budget balanced: The Distributed Reallocation Protocol is budget balanced, namely the sum of payments made by the advertisers is equal to the sum of credits given to the publishers.

We proceed by describing the other ad placement mechanisms which are compared to the Weighted Bipartite HVCG: the Simultaneous English Auction, the Gale and Shapley protocol, the Generalized Second Price, and the advertisers’ aimed HVCG. We describe each mechanism in detail, as well as its advantages and drawbacks. We then provide the results of the comparison made by means of a simulation platform in the next Section (Section 4).

3.2.4 The Simultaneous English Auction

According to the Simultaneous English Auction, each publisher runs a separate auction on the slots it suggests for advertisements. As mentioned in Section 3.1, we assume the existence of a regulator responsible for the due process of the whole market.

Specifically, the Simultaneous English Auction, as adapted for the preference driven ad exchanges, proceeds as follows:

Algorithm 4: The Simultaneous English Auction
1:	Each publisher initiates an English auction, and announces its scoring rule (reported utility) $R_{j}(i)$ for each advertisement $A_{i}$ .
2:	Each advertiser (ad owner) sees the list of publishers, and needs to decide in which auction to place a bid and at what price.
3:	At each time unit $t=1\ldots T$ .
4:	Each advertiser can decide to do one of the following.
5:	Choose the auction in which to participate and the price to bid.
6:	Move from one auction to another.
7:	Increase its bid in its active auction.
8:	Each publisher determines the winners of each slot $k$ according to a decreasing order of

	$(B_{i}(j)+R_{j}(i))\textit{CTR}_{i}(k,j)$ .
9:	In a predefined closing time T, the auction is over.
10:	The winners of the available slots of each publisher are the highest ranked ads.
11:	The price each ad pays is equal to its bid.

The Simultaneous English Auction properties

(a) Bidding strategy in equilibrium

The optimal strategy for the advertiser in the Simultaneous English Auction protocol, is to choose, at each time step, the publisher and the bid that maximizes its expected utility from the auction. The principle of the proposed bid is similar to that of the classic English auction, where the advertiser is required at each step to overbid the current bid by the minimum required to make it the winner. Choosing a lower bid will cause the advertiser to lose its possible slot. Choosing a higher bid than the minimal required to win, will cause it to pay more than the minimal price required to win. Choosing an auction different than the auction that maximizes the advertiser’s expected utility will clearly decrease its expected utility.

Note, however, that the publisher is sometimes motivated to report a scoring rule, $R_{j}(i)$ , that is different than its real utility function, $U_{j}(i)$ .

(b) The Simultaneous English Auction: Publishers’ untruthful reported utility function

Given the Simultaneous English Auction, there are cases where a publisher may deviate from its real utility function $U_{j}$ , by announcing a different reported utility function $R_{j}$ used as its scoring function. We prove this in Lemma 3.

Lemma 3. Given the Simultaneous English Auction protocol, there are situations in which the publishers will be motivated to report a scoring function which is different than their real utility function.

Proof Suppose a single publisher, $\textit{Pub}_{1}$ , with a single slot exists and there are two advertisers, $A_{1}A_{2}$ , competing for this single slot. Both advertisers have $\textit{CTRi}(1,j)=1\text{ for }j=1\text{ and }i=1,2$ . Now, let us assume that the true utility gained by displaying these two ads is the same and equals $-$ 1, i.e., $U_{1}(1)=$ $U_{1}(2)=-1$ (the publisher in this case gains a negative utility by displaying these ads). From the advertisers’ perspective, the utility gained by $A_{1}$ , and $A_{2}$ from displaying their ads in the single slot available is $V_{1}(1)=1.5$ and $V_{2}(1)=2$ , correspondingly.

If the publisher reports its true utility, advertiser $A2$ will win at a price of $1.5+\varepsilon$ , since given this price, advertiser $A1$ will leave the competition. Thus, the publisher will obtain $B=1.5+\varepsilon$ , its utility will be $U=-1$ , and consequently its profit will be $B+U=1.5+(-1)=0.5+\varepsilon$ .

Now, in order to attain a profit higher than $0.5+\varepsilon$ , the publisher can bid a scoring rule $R_{1}(2)=-1.9$ for ad 2. Advertiser $A2$ will agree and pay 1.9 for the dedicated space, and the profit of the publisher will be $B+U=1.9+(-1)=0.9$ , which is higher than its profit when reporting its true utility function.

This example demonstrates that there are cases where the publishers may gain by reporting a deviation from their true utility with the Simultaneous English Auction.

In spite of the fact that a publisher may deviate from his real utility function by reporting a different one, in this paper we assume the publishers will announce a general non-changeable scoring function that will be used for all future auctions in a predefined time interval (and this will be a part of the protocol and will be enforced by a centralized regulator). Thus, in order to be able to manipulate the scoring function, the publisher will need to speculate about the possible advertisers in its possible future auctions, and attempt to calculate a scoring function that will benefit him more than his true utility function. Such a mission is assumed to be hard. Nonetheless, with the use of machine learning techniques, it might be practical. Such manipulation is not within the scope of this paper, though we intend to address this issue in future work.

At each round, at least one bid is incremented by the minimum required, m_increment, over the previous winning bid. The total number of possible increments in one auction is the maximum valuation of any advertiser for this auction (since no advertiser will bid more than its valuation) divided by the size of the minimum required bid increment. Given the number of rounds of each particular English auction among those that are run simultaneously, we define the maximum number of rounds of the Simultaneous English Auction to be the number of rounds of the longest English auction by:

$\textit{MaxNumRounds}={\max}_{i=1\ldots N,j=1\ldots M}\{V_{i}(j)\}/m\_\textit{% increment}.$ (7)

In each round, an advertiser has to scan the current winner of all available slots, MK, in order to decide what and where to bid. In particular, given the number of rounds in the worst case MaxNumRounds, the running time of each advertiser is:

$O(M\cdot K\cdot\textit{MaxNumRounds})=O(M\cdot K\cdot{\max}_{i=1..N,j=1..M}\{V% _{i}(j)\}/m{\_}\textit{increment})$ (8)

In each round, a publisher has to consider the winner of each of his $K$ slots, where the number of available bids for each slot can be at most $N$ . Thus, given the number of rounds in the worst case, MaxNumRounds, the total time complexity for each publisher is:

$O(N\cdot K\cdot\textit{MaxNumRounds})=O(N\cdot K\cdot{\max}_{i=1..N,j=1..M}\{V% _{i}(j)\}/m{\_}\textit{increment})$ (9)

Consequently, if the different participants act in parallel, the time required until all the participants will finish their calculation is:

$O(\max\left(N,M\right)\cdot K\cdot{\max}_{i=1..N,j=1..M}\left\{V_{i}\left(j% \right)\right\}/m\_\textit{increment}).$ (10)

The Simultaneous English Auction is individually rational: No advertiser will pay more than its private value, no publisher will obtain less than its reserved costs published (otherwise it will not display an ad).

The Simultaneous English Auction is budget balanced: The advertisers give their payments directly to the publishers. Thus, the sum of payments made by the advertisers is equal to the sum of credits given to the publishers.

3.2.5 Gale and Shapley matching protocol

According to the Gale and Shapley mechanism, the utility function of the publishers is expressed as an ordered list of advertisers, while the utility function of the advertisers is expressed as a decreasing list of the preferred slots indicated by pairs of publisher and slots, $({\textit{pub}}_{i_{j}},s_{i_{j}})$ . These ordered lists of preferences of the publishers and the advertisers are assumed to be the input of the Gale and Shapley mechanism for two-sided matching [18]. Note that if more ads exist than the available slots, fictive publishers can be added with no utility and zero Click Through Rates in order to find a perfect match.

Gale and Shapley allocation protocol

The proposed Gale and Shapley matching protocol can have two variations:

Advertisers-initiated protocol: The advertiser choses his preferred publisher and slot. The publisher has to agree or disagree.

Publisher-initiated protocol: The publisher choses his preferred ad for each slot. The advertisers have to agree or disagree.

The advertisers-initiated protocol is defined as follows:

Algorithm 5: The advertisers-initiated protocol
Notation: pub denotes the publisher, $s$ denotes the slot, MK is the number of possible pairs of
	$<$ $p u b, s$ $>$ .
1:	For each advertiser, $A_{i}$ , create an ordered list of places indicated by the pairs $\textit{PreferencesList}=$
	$\{(\textit{pub}_{i_{1}},s_{i_{1}}),\ldots,((pub_{i_{\textit{MK}}},s_{i_{% \textit{MK}}})\}$ ordered in a decreasing order of preferences. (The most
	preferred pair will be the first pair, $(\textit{pub}_{i_{1}},s_{i_{1}})$ ).
2:	While an unallocated ad, $X$ , exists do:
3:	Pick an unallocated ad $X$
4:	Find the most preferred $(\textit{pub}_{i_{1}},s_{i_{1}})$ in the current preference list of $X$ .
5:	Remove ${(pub}_{i_{1}}s_{i_{1}})$ from the list of $X$ .
6:	If (slot ${(pub}_{i_{1}},s_{i_{1}})$ is empty) and
	(the utility of publisher $\textit{pub}_{i_{1}}$ from allocating $X$ to it is positive) then
7:	Allocate $X$ to slot $s_{i_{1}}$ of publisher $\textit{pub}_{i_{1}}$ .
8:	Else if (slot $(\textit{pub}_{i_{1}}s_{i_{1}})$ is not empty) and
	(publisher $\textit{pub}_{i_{1}}$ prefers ad $X$ more than the currently allocated ad $Y$ ) then
9:	Set ad $Y$ to be unallocated
10:	Allocate $X$ to slot $(\textit{pub}_{i_{1}},s_{i_{1}})$ .

The publisher-initiated protocol is defined as follows:

Algorithm 6: The publisher-initiated protocol
Notation: pubj denotes the publisher, $A_{j_{k}}$ denotes the $i$ ’s advertisers according to the order of
	publisher pubj and $N$ is the number of available ads.
1:	For each publisher pubj, create an ordered list of ads $\textit{PreferencesList}=\{A_{j_{1}},\ldots,A_{j_{N}}\}$ ordered
	in a decreasing order of preferences. The most preferred pair will be $A_{i,1}$ .
2:	While an unallocated slot $(\textit{pub}_{j},\textit{slt})$ exists do:
3:	Pick an unallocated slot $(\textit{pub}_{j},\textit{slt})$
4:	Find the most preferred $A_{j_{k}}$ in the current preference list of publisher $\textit{pub}_{j}$ .
5:	Remove $A_{j_{k}}$ from the list of $\textit{pub}_{j}$ .
6:	If ( $A_{j_{k}}$ is not allocated yet) and
	(the utility of $A_{j_{k}}$ from being allocated by publisher $\textit{pub}_{j}$ is positive):
7:	Allocate $A_{j_{k}}$ to slot slt of publisher $\textit{pub}_{j}$
8:	Else if ( $A_{j_{k}}$ is already allocated) and
	(advertiser $A_{j_{k}}$ prefers to be allocated by publisher $\textit{pub}_{j}$ slot slt more than his current
	allocation) then
9:	Set the old location of $A_{j_{k}}$ to be unallocated
10:	Allocate ad $A_{j_{k}}$ to slot $(\textit{pub}_{j},\textit{slt})$

Gale and Shapley pricing protocol

In the original Gale and Shapley matching protocol, there was no currency involved. The existence of money and a pricing protocol, however, can influence the preferences of the participants and change the final solution. If we enable different prices for each pair of advertiser and publisher, we will find ourselves in a type of simultaneous auction protocol. In this study, for simplification reasons, we use a protocol that requires the publishers to predefine prices for each of their slots (each publisher can find the best set of prices by using a reinforcement learning protocol, however this is not within the scope of this paper). In particular, in our simulations, the price of winning the last slot of any publisher was determined to be equal by all publishers, and equal to the average expected bid, and the price of any higher slot will be 1% more than the price of the next slot.

Properties of the Gale and Shapley protocol

Time complexity: The time complexity of the Gale and Shapley protocol is $O(\textit{NMK})$ where $N$ is the number of advertisers, $M$ is the number of publishers, and $K$ is the number of slots each publisher dedicates to ads, since no ad gives an offer to any publisher/slot more than once.

Individual rationality: The algorithm is individually rational since no participant will offer or accept an offer that is not beneficial to it.

Stability: The protocol is stable, which means that no pair exists that prefers to be together (ad a in slot s) rather than in their current allocation.

Truthfulness: The protocol is truthful only from the proposing side, but not from the passive side. The explanation for this can be found in [35].

Nonetheless, using such a protocol without a dynamic price mechanism will cause the protocol to be very limited, since no compensation can be used by the participants. Note, however, that if a dynamic pricing is used, the protocol becomes a type of Simultaneous English auction.

3.2.6 The Generalized Second Price protocol

The next protocol we compared it to is a Generalized Second Price based mechanism, adapted for usage in the content of multiple-publishers and multiple-ads, with preferences of both sides.

The Generalized Second Price variation used for the preference driven auction is described as follows. Given the centralized ad exchange, and given a list of ads to be published and a list of available publishers:

Algorithm 7: The Generalized Second Price
Notation: there are $N$ advertisers and $M$ publishers.
1:	Each publisher submits $N$ values of minimal bids: for each advertiser, the publisher submits a
	minimal bid value needed for participation of the advertiser in the auction of the publisher.
2:	Each advertiser submits $M$ bids: one bid for each publisher.
3:	The auctioneer calculates the optimal allocation using the Hungarian algorithm.
4:	The function that will be maximized will be a sum of the utilAlloc function, which is defined
	as follows:
	For each ad Ai located by publisher Pubj:
	if $B_{i}(j)+R_{j}(i)<0$ (the bid of ad Ai does not cover the reported costs of publisher Pubj),
	then $\textit{utilAlloc}(\textit{Ai},\textit{Pubj})=-\infty$ .
	Otherwise, $\textit{utilAlloc}(\textit{Ai},\textit{Pubj})=B_{i}(j)$
5:	Given the allocation, the pricing policy will be determined as follows:
6:	If $(B_{\textit{winner}(\textit{Sk}+1)}(\textit{Pubj})+\textit{utilAlloc}(\textit{% Ai},\textit{Pubj})\geqslant 0)$ //ad Ai is located at slot $\textit{Sk}<K$ of publisher
	Pubj, and the bid of the next slot winner will cover the publishers’ expenses:
7:	then $\textit{price}(A_{i})=B_{\textit{winner}(Sk+1)}(\textit{Pubj})$
8:	//the price paid by Ai to Pubj will be equal to the next bid
9:	Otherwise: $\textit{price}(A_{i})=R_{j}(i)$

10:	//advertiser $A_{i}$ will pay the minimal value needed for participation in the auction of publisher
	Pubj.

The properties of the Generalized Second Price

We proceed by describing the properties of the Generalized Second Price protocol:

Not incentive compatible: The Generalized Second Price protocol is not incentive compatible, as proved by [2, 14]. Moreover, the publisher has incentive to reduce its published utility $R_{j}(i)$ in order to obtain higher prices in the auction.

Individually rational: The variation used in this paper is individually rational, since in any case the publisher will receive at least its reservation price for allocating an ad. In addition, each winning advertiser will pay the next bid, or the reserve price which is less or equal to its bid, and as a result, no advertiser will pay more than its own maximum value.

Complexity: The complexity of implementing the GSP in the variation used in this paper includes the complexity of the Hungarian algorithm: $O(\max(N,\textit{MK})^{3})$ and the complexity of evaluation of the Generalized Second Price: $O(N)$ . The total time is: $O(\max(N,\textit{MK})^{3})$ .

Budget balancing: The protocol is budget balanced (the determined payments are passed from the bidders to the publishers).

3.2.7 Advertisers’ aimed HVCG protocol

For the sake of comparison, we also added a protocol similar to the Hungarian $+$ Vickery Clarks Grove protocol, where the utility function is maximized by the advertiser’s bid, but if the bid of an advertiser is lower than the minimal required bid for that publisher, the bid is not considered. In other words, the utility function is determined in the same manner as in steps a, and b of the Generalized Second Price protocol:

Algorithm 8: The advertisers’ aimed HVCG protocol
Notation: There are $N$ advertisers and $M$ publishers.
1:	Each publisher $\textit{Pub}_{j}$ submits $N$ values of minimal bids for each of the $N$ advertisers.
2:	Each advertiser $A_{i}$ submits $M$ bids for each of the publishers.
3:	The auctioneer calculates the optimal allocation using the Hungarian algorithm.
4:	The function that will be maximized will be a sum of the utilAlloc function, as defined in
	Algorithm 8 (the Generalized Second Price protocol).
5:	The auctioneer calculates the prices paid and obtained by each participant using the
	Vickery-Clarks-Grove protocol.

Given the details of Advertisers’ aimed HVCG protocol, we proceed by specifying its properties.

The properties of the advertisers’ maximization protocol:

(a) Not individually rational: See Lemma 4.

Lemma 4. The Advertisers’ aimed HVCG protocol is not individually rational.

Proof Consider the following situation: 2 publishers exist, where each one suggests one slot, and 2 advertisers exist. The advertisers’ bids and the publishers’ minimal prices are as follows:

$\displaystyle B_{1}(1)=1,B_{1}(2)=2,B_{2}(1)=2.5,B_{2}(2)=2.5$ $\displaystyle R_{1}(1)=-2,R_{1}(2)=-2.4.$ $\displaystyle R_{2}(1)=R_{2}(2)=R_{2}(3)=-1$

The Click Through Rate values are $\textit{CTR}_{i}(k,j)=1$ .

The allocation according to the protocol will be:

Ad ${}_{1}$ to publisher ${}_{2}$ , Ad ${}_{2}$ to publisher ${}_{1,}$ and the advertisers total utility will be 4.5.

If publisher ${}_{1}$ does not exist: Ad ${}_{2}$ will be allocated to publisher ${}_{2}$ , and the advertisers’ total utility will be 2.5.

Thus, the gains of publisher ${}_{1}$ will be 2, while the minimal required amount it will ask for the participation of Ad ${}_{2}$ will be 2.4. Thus, the gains of publisher ${}_{1}$ will be negative.

(b) Not truthful: The protocol is truthful considering the advertisers, since payments are calculated by the Vickery-Clarks-Grove protocol. However, a publisher who may have losses due to participating in the auction (as represented above) may be motivated to publish higher minimal values (i.e., lower reported utilities) than the real ones, in order to avoid the losses.

(d) Budget balancing: The protocol is not budget balanced, because of the use of Vickery-Clarks-Grove protocol which in general is not budget balanced.

4. Algorithms comparison and simulation results

In this Section, we compare the theoretical properties of the different algorithms, as detailed in Section 3.2, and we proceed by describing simulation results relating to the comparison of the different algorithms, and, in particular, the comparison of the Weighted Bipartited HVCG with the other suggested algorithms for the preference driven ad exchanges.

4.1 Summary of the different protocols’ properties

We start by providing a summary of the main theoretical properties of the different algorithms described in Section 3.2: HVCG, the Weighted Bipartite HVCG, the Distributed Reallocation Protocol, the Simultaneous English Auction; the Gale-and-Shapley protocol, the Generalized Second Price protocol (GSP) and the Advertisers’ aimed Hungarian VCG. Table 1 summarizes the properties of the different protocols used for the ad exchange domain. Then we proceed by providing the results of a comparison we performed by means of simulations.

Table 1
The properties of the different protocols

Protocol	Centralized/	Truthful	Budget	Individual	Optimal
	Distributed		balanced	rational
HVCG: payment mechanism	Centralized	$+$	$-$	$+$	$+$
Weighted Bipartite VCG	Centralized	$+$	Can be reached	$+$	$-$
Distributed Reallocation Protocol	Distributed	$+$	$+$	$+$	$-$
Simultaneous English auction	Distributed	IC for the advertisers	$+$	$+$	$-$
Gale and Shapley matching protocol	Distributed	IC for the proposer side	$+$	$+$	$-$
Generalized Second Price protocol	Centralized	$-$	$+$	$+$	$-$
Advertisers’ aimed HVCG protocol	Centralized	Truthful for the advertisers	$-$	$-$	$-$

4.2 Simulation setting

In order to evaluate and compare the performance of the suggested protocols, we developed a simulated ad exchange market with publishers and advertisers. The simulation details are as follows.

Each simulation included $N$ advertisers, and $M$ publishers, each with $K$ available slots for ads. For each generated environment, all the proposed mechanisms for the ad exchange scenario were applied and the resulting matches between the $N$ advertisers and the existing KM slots of the publishers were compared.

Each randomized environment satisfied the following properties:

A random Click Through Rate table is generated for each advertiser $A_{i}$ and slot $k$ . The click through rate is a random number between (0.01…10) clicks from 100 presentations of the ad. The Click Through Rate values are uniformly distributed, unless otherwise specified. Note that for simplicity, we assume the same Click Through Rate for a given advertiser $A_{i}$ for slot number $k$ in any publisher. We use this generalization, in light of the fact that the set of publishers dynamically changes, and this makes the task of learning the Click Through Rate per publisher a very difficult one.

For each publisher, a utility function $U_{publisher}$ (ad) was randomly created: For each publisher and each ad, $U_{publisher}$ (ad) gives the utility of the publisher from one click on each type of ad. The publisher utility function, unless otherwise specified, was uniformly generated between ( $-$ 1.0…0.01). Typically, the scoring function of the publisher is negative in order to reflect the fact that in general the ads disturb the website and affect the Website user’s experience.

For each advertiser $A_{i}$ , the value $V_{i}(j)$ of the advertiser from a click on an ad presented by publisher Pub ${}_{j}$ is created. The value is randomly distributed between ( $0\ldots+1.0$ ), unless otherwise specified.

Other parameters related to the protocol that are used: unless otherwise specified, the minimum increment in the English auction is set to 0.2, and the balancing weight in the Weighted Bipartite HVCG protocol is set to 0.3.

Figure 2.

The main simulation entities.

Given these guidelines, we created different random generated environments that represent a typical ad exchange market. Each point presented in our result is the average of 100 runs of random generated environments, based on the above parameters.

The simulation system was set up for the research purpose, and was not implemented in a real ad auction (the real Click Through Rate values used in Section 4.8 were collected from a website where the ads were randomly mapped to slots). Figure 2 describes a schematic diagram (a partial class diagram) which describes the simulation entities and the relation between them.

Specifically, we compared the following protocols:

Weighted Bipartite HVCG.

Simultaneous English Auction.

Gale and Shapley: Matching protocol, where the advertisers offer, or where the publishers offer.

The Distributed Reallocation Protocol.

HVCG: Hungarian algorithm $+$ Vickery-Clarks-Grove protocol: For sake of comparison.

GSP: With advertisers utility function.

Advertisers’ aimed HVCG protocol.

Note however that despite its optimal results the HVCG was not appropriate as a solution due to the deficit it causes the auctioneer as demonstrated in our results. Thus, for the most part it was used as a baseline in the comparison.

The research questions which we addressed include:

How should the auctioneer tune the weighting parameter $w$ in the Weighted Bipartite HVCG?

How efficient are the different protocols? Which protocols were generally more efficient? How do changes in the size of the environments or in other environment parameters affect the protocols’ efficiency?

How is the total market utility shared between the publishers and advertisers in the different protocols?

Next we provide the simulation results and answers to the research questions.

4.3 Comparison of the performance of the different protocols

In the following section, we present our results concerning the comparison of the different suggested protocols, with regards to their efficiency, and the distribution of gains between publishers and advertisers. The results are presented in Table 2, for simulations with 100 advertisers, 10 publishers and 3 slots per publisher.

Table 2
The results of the different protocols

Protocol	Total utility	Ratio out of	Publishers’	Advertisers’	Comments
	(standard deviation)	optimal solution	utility share	utility share
HVCG	158.05 (6.34)	100%	95.7%	21.7%	Auctioneer loss:
					17.4%
Weighted Bipartite HVCG:	157.32 (6.37)	99.5%	70.4%	22.7%	Auctioneer share: 6.9%
$W=$ 0.3					of the total utility
Distributed Reallocation Protocol	132.8	84%	84.8%	15.2%
Simultaneous English auction	130.97 (11.13)	82.9%	74.9%	25.1%
Gale and Shapley protocol,	111.16 (10.07)	70.3%	69.9%	30.1%
advertisers as proposers
Gale and Shapley protocol,	146.12 (7.27)	92.5%	65.6%	34.4%
publishers as proposers
Generalized Second Price protocol	107.38	67.9%	17.2%	82.8%
Advertisers’ aimed VCG	107.38	67.9%	185.6%	27.5%	Auctioneer loss: 113.1%

There are several interesting results in Table 2 that warrant an explanation. First, it is clear that the Weighted Bipartite HVCG reached results that are near to the optimal results reached by the HVCG. Next, we can omit some of the protocols that are not applicable or that are not efficient as a whole: The HVCG protocol and the Advertisers’ aimed VCG cause a serious deficit for the auctioneer, and thus cannot be used in practice. The Gale and Shapley protocol was more efficient when the publishers were the proposers, while the Gale and Shapley protocol reached relatively weak results when the advertisers were proposers. Apparently the non-competitive results of the Gale and Shapley protocol when the bidders were the proposing side are due to the fact that the publishers could not be compensated for allocating ads that provide a utility lower than their price. Note, however, that as the number of slots increases, the advertiser’s Gale and Shapley protocol became more efficient with respect to the publisher’s Gale and Shapley protocol, as shown later in this section, in Fig. 13. Nonetheless, the Weighted Bipartite HVCG protocol is more efficient than both.

The results of the protocols that maximize the buyer’s side only (Generalized Second Price and Advertisers’ aimed Vickery-Clarks-Grove) were poor, due to the fact that they do not include the publishers’ preferences in the function to be maximized.

Table 3

The results of the different protocols with publishers’ positive scoring functions

Protocol	Total utility	Ratio out of	Publishers’	Advertisers’	Comments
	(standard deviation)	optimal solution	utility share	utility share
HVCG	263.32	100%	95.0%	17.1%	Auctioneer loss: 12.1%
Weighted Bipartite HVCG:	262.79 (9.59)	99.8%	80%	18.9%	Auctioneer share: 1.1%
$W=$ 0.3					of the total utility
Distributed Reallocation Protocol	224.01 (12.6)	85.1%	89.4%	10.6%
Simultaneous English auction	233.05 (18.06)	88.5%	80.9%	19.1%
Gale and Shapley,	182.04 (14.29)	69.1%	81.9%	18.1%
advertisers as proposers
Gale and Shapley,	251.69 (10.79)	95.6%	78.8%	21.2%
publishers as proposers
Generalized Second Price protocol	207.80	78.9%	31.6%	68.4%
Advertisers’ aimed VCG	207.80	78.9%	95.1%	13.7%	Auctioneer loss: 8.8%

Figure 3.

The balanced deficit ratio as a function of the number of advertisers with the HVCG protocol.

The Distributed Reallocation Protocol, Simultaneous English Auction and Gale and Shapley protocol with the publishers proposing offers, reached results closer to the optimal, but still less efficient than the results of the Weighted Bipartite HVCG. Furthermore in the previous section we showed that the Simultaneous English Auction and Gale and Shapley are not truthful or IC, thus they are open to manipulations.

In general, we consider situations where the publisher has expenses for each ad that is clicked. Thus, its utility from showing ads is negative. However, Table 3 considers the simulation results where the publishers’ utility for each ad is randomly in a range that also can be positive, and the utility of each publisher for a click on each ad is randomly drawn from the range between ( $-$ 0.5…0.5).

Note that with these values of publishers’ utilities, the losses of the auctioneer when applying the advertisers’ aimed VCG were only 8.8% (while the losses were 113.1% when considering negative publishers’ utilities). However, any type of losses on the part of the auctioneer cannot be applied in the long run, since the auctioneer will not be motivated to run these auctions at all. The Weighted Bipartite HVCG, however, is a good substitute, and its solution was near to optimal, as explained in the following subsection, in which we first examine the deficit of the auctioneer by applying the HVCG.

Figure 4.

The balanced deficit ratio as a function of the number of advertisers with the Weighted Bipartite HVCG protocol ( $w=$ 0.3).

4.4 The deficit obtained by the auctioneer with the HVCG and the Weighted Bipartite HVCG

We continue by observing the behavior of the auctioneer’s deficit when applying the HVCG and the Weighted Bipartite protocols. The deficit ratio in this case is defined as the total sum of payments to the publishers minus the total sum of payments obtained from the advertisers, divided by the total sum of the publishers’ and advertisers’ utilities from the given allocation.

We begin by analyzing the deficit when applying the HVCG. Figure 3 shows that the deficit level decreases as the number of advertisers increases. Moreover it remains almost stable for 100 bidders and more. The deficit becomes stable at around 10% of deficit for 100 bidders and more. Even though, it is only a 10% deficit, this property prevents the HVCG protocol from being applicable in real world situations because no auctioneer will run a market that incurs losses.

Next, we consider the Weighted Bipartite HVCG protocol, where the maximization function includes a weighting scheme that diverts more weight to the publishers, as described in Section 3.2.2. Using this protocol, the gains or deficit of the auctioneer can be controlled by simply tuning the value of $w$ in the allocation maximization formula, and accordingly in the payments formulas.

Figure 4 illustrates the balanced deficit of the Weighted Bipartite HVCG using $w=$ 0.3, for the same environments depicted in Fig. 3.

As illustrated, for a weight of $w=$ 0.3, again we can see that the auctioneer’s deficit decreases as the number of advertisers increases. However in this case, for 62 advertisers and more, the loss becomes negative, which means that the auctioneer starts to gain a positive revenue from managing the auction. Namely, using the Weighted Bipartite HVCG the auctioneer has the ability to control the deficit/revenue by tuning the weight $w$ . Obviously, if the auctioneer adopts a greedy attitude, then in the long run, his market will not be attractive nor competitive in the real open market.

Figure 5.

The total utility of the Weighted Bipartite HVCG relative to the total utility of the HVCG, as a function of weight $w$ .

Figure 6.

The auctioneer’s relative deficit (or profit) as a function of $w$ .

4.5 The implications of the tuning parameter

w

Now we will analyze the effect of the chosen weight $w$ on the relative utility. The trade-off is clear. As the weight $w$ increases, the allocation efficiency decreases (since the maximization function becomes greater than the average total utility) but the auctioneer’s revenue increases (as the payments to the publishers decrease). That is, the auctioneer trades the total market efficiency with its private revenue.

Figure 5 describes the total efficiency (total utility of participants including advertisers and publishers) as a function of the weight value ( $w$ ) with constant parameters of 100 advertisers,10 publishers and 3 slots in each run of the simulation, with a total of 100 runs.

The results demonstrate that even for the maximum weight value of 1, $w=$ 1 that the auctioneer may set in order to gain the maximum possible revenue, the loss in the efficiency is less than 1.2%. Namely, the mechanism achieves a near optimal allocation even in the worst case of a very greedy auctioneer. To conclude, the budget balance problem was overcome by a slight sacrifice in efficiency.

Figure 7.

Balanced $w$ as a function of the number of advertisers.

Figure 8.

The relative utility as a function of the number of advertisers when balancing $w$ .

This is a very interesting and surprising result which might increase the popularity of a VCG-like mechanism in real marketplaces.

Figure 6 demonstrates the relative deficit or profit of the auctioneer as a function of $w$ for the same set of simulations depicted in Fig. 5. Note that an exact balancing value of $w$ exists (for the examined simulations, the balancing weight value was $w=$ 0.15) for which the auctioneer’s deficit approaches zero. For higher values of w, the auctioneer begins to gain positive revenue at the expense of the participants (advertisers and publishers).

4.6 The value of the tuning parameter

w

The next interesting question that emerged is how to determine the optimal value of weight $w$ that will balance the auctioneer’s budget. In particular, for a given real world market, the auctioneer can tune this weight over time, until it reaches a weight that bestows her a positive but small profit. The auctioneer herself will not be motivated to increase her said profit due to the competition that exists in the marketplaces. If the auctioneer’s profit will be relatively larger, the profits of the publishers and advertisers will decrease, which will eventually cause them to leave the current ad exchange for other alternative markets. Thus, we propose that the auctioneer find the optimal weight that will result in profitability but will not drive the participants away.

To demonstrate this idea, Fig. 7 shows the value of that balances the market (deficit $=$ revenue $=$ 0) as a function of the number of advertisers (different values of $w$ were tested until the balanced $w$ was found). Figure 8 depicts the total efficiency for the balancing weights (as shown in Fig. 7) as a function of the number of advertisers.

Table 4
Results when the ratio of #advertisers/#publishers is kept constant

	#advertisers $=$ #publishers*100		#advertisers $=$ #publishers*10
#Publishers	Average relative utility	Average balanced weight	Average relative utility	Average balanced weight
3	0.999152	0.1495	0.989517	0.419
4	0.999404	0.136	0.993042	0.341
5	0.999625	0.1265	0.994819	0.325
6	0.999558	0.1175	0.994332	0.304
7	0.99965	0.1165	0.996379	0.2665
8	0.999697	0.1075	0.997326	0.2505
9	0.999758	0.104	0.997347	0.246
10	0.999697	0.102	0.997444	0.2265

Figure 9.

Balancing $w$ as a function of the number of publishers, 50 advertisers.

The interesting results show that as the number of advertisers increases the weight, $w$ , which balances the market, decreases. Namely the more the advertisers, the smaller the allocation deviation achieved and the more efficient the allocation is according to the results displayed in Fig. 8.

In the subsequent simulation we aimed to learn the direction of the loss incurred by balancing $w$ as a function of the number of advertisers (ranging from 20 to 100). The loss decreased as the number of advertisers increased, with the loss between 0.02%–4%. Namely, the more the advertisers (as the number of publishers remained 5, and the number of slots remained 2) in the market the lower the loss when applying the Weighted Bipartite HVCG protocol.

Furthermore, we checked the effect of changing the number of publishers; as depicted in Figs 9 and 10, as the number of publishers increased (while the number of advertisers remained 50), the balancing weight $w$ increased, and the relative utility when balancing $w$ slightly decreased.

Another interesting question that emerged is the influence of changes in number of publishers and advertisers when their ratio remains fixed. Table 4 shows the balanced $w$ and the relative utility when the ratio between the number of advertisers and the number of publishers remains constant (10). In fact, as the number of advertisers increases, if the ratio of advertisers/publishers remains constant, the average balanced weight as well, as the average utility, remain with the same values.

The conclusion from Figs 7–10 and from Table 4 is, that in general, as the relation between the number of publishers and the number of advertisers increases, the weight required to balance the auction is lower, and the average utility approaches the optimal utility.

To summarize, it is apparent that the use of the Weighted Bipartite HVCG protocol can help auctioneers handle a balanced budget over time, with only a slight effect on the total utility. In addition, when there are more advertisers, the balancing weight can be lower, but when there are more publishers, more payment is required resulting in an increase in the balanced weight needed to obtain a balanced protocol.

Figure 10.

The relative utility of the Weighted Bipartite HVCG when the budget is balanced as a function of the number of publishers, 50 advertisers.

Figure 11.

Total utility as a function of the number of advertisers.

4.7 Comparison of the various proposed protocols under different simulation settings

In the last set of simulations we compared only the more efficient and useful protocols proposed for the preference driven ad exchange. Based on the results provided in Tables 2 and 3, we graphically compared the (i) Weighted Bipartite HVCG, (ii) Simulated English Auction, (iii) Distributed Reallocation protocols, (iv) the Gale and Shapley protocol when the publisher is the offeror, and (v) the optimal HVCG protocol.

Figures 11–13 display the total utility of both the advertisers and the publishers, as a function of the number of advertisers (Fig. 11), as a function of the number of publishers (Fig. 12) and as a function of the number of slots (Fig. 13). The weight $w$ used in this set of comparisons was set to 0.3, and, unless specified otherwise, the number of advertisers was set to 100, the number of publishers was set to 10, the number of slots was set to 3, and each point in the figure represents the average results of 100 simulated runs.

Figure 11 demonstrates that the total utility increased as the number of advertisers increased for the different analyzed protocols. Moreover, the Weighted Bipartite HVCG protocol outperformed the other heuristic protocols, and achieved results that were very close to the optimal, but not applicable.

Figure 12 shows that the total utility increased linearly with the number of publishers, which can be explained by the fact that as the number of publishers is multiplied, the number of displayed ads is also multiplied by the same factor, and as a result, the total utility is multiplied.

Figure 13 demonstrates the behavior of the different protocols as a function of the number of slots (The number of advertisers was set to 50 and the number of publishers was set to 5). It is interesting to note that the results of the Simultaneous English Auction became less efficient as the number of slots increased. This phenomenon can be explained by the fact that in cases where more slots exist in each publisher’s website, there are more exchange possibilities to negotiate using the Distributed Reallocation Protocol and therefore better results are achieved which outperform the results of the Simultaneous English Auction. In addition, it is clear that as the number of slots increases, the Gale and Shapley algorithm becomes more efficient if the advertisers suggest the offers, while the Gale and Shaple protocol when publishers are the offerors becomes less efficient. The intuitive explanation is the fact that as the number of slots increases, the advertisers have more alternatives from which to choose of where to offer their bids, while the publishers have less alternatives for choosing ads to be allocated in all their slots. Thus, the results of the Gale and Shapley protocol when the advertisers choose their partners become more efficient as more slots exist in each publisher. Nevertheless, the advantage of the Weighted Bipartite HVCG is still clearly maintained for all the different parameters tested.

Figure 12.

Total utility as a function of the number of Web publishers.

Figure 13.

Total utility as a function of the number of slots.

4.8 Results of the simulation using real click through rate values

Lastly, we tested the behavior of the different protocols when using real click through rate data, collected from the Shabes.net website (http://shabes.net) during a period of two years (24-2-2014–24-2-2016). The collected data considered only seven types of ads. Thus, we randomly generated Click Through Rate values for the rest of the advertisers by applying a linear combination of Click Through Rate values based on a linear combination of the real values, where the Click Through Rate of each generated advertiser was a weighted average of Click Through Rate values of the other two advertisers, and the weights and the publishers’ and advertisers’ utility functions were generated randomly.

Table 5
Results based on real click through rate values

Protocol	Total utility	Ratio out of	Publishers’	Advertisers’	Balance
	(standard deviation)	optimal solution	utility share	utility share
HVCG	104.9262 (5.7447)	100.00%	96%	21.56%	$-$ 18.369%
Weighted-0.50	103.8725 (5.795)	99.00%	60%	22.24%	18.360%
DRP	87.3297 (5.999)	83.23%	86%	13.61%	0%
Simultaneous English Auction	81.7318 (9.1418)	77.89%	76%	24.36%	0%
Gale and Shapley, advertisers as offerors	71.3537 (6.073)	68.00%	64%	35.69%	0%
Gale and Shapley, publishers as offerors	92.6656 (6.243)	88.32%	61%	39.35%	0%

The results of the simulation, based on 100 runs, are similar to the simulation of random generated environments. The Weighted Bipartite HVCG was still near to optimal, achieving 99% of the optimal results, while keeping an 18% gain ratio for the auctioneer, and the Gale and Shapley protocol with publishers was the next best protocol, achieving 88.3% of the optimal results.

To conclude, in this section we compared different protocols for the ad allocation task in preference driven ad exchanges. We comprehensively compared different protocols and found that the distributed protocols, namely, the Distributed Reallocation Protocol, the Simultaneous English Auction and a variant of the Gale and Shapley protocols, reached approximately 80%–90% of the optimal solution, assuming a centralized manager with complete information. The HVCG protocol, which is based on the use of the VCG disclosure mechanism and then finds the optimal allocation, was found to be inapplicable since it causes a serious deficit for the auctioneer. However, a variation of the HVCG protocol, called the Weighted Bipartite HVCG protocol, reached near optimal (98%–99% of the optimal allocation) solutions while keeping the auctioneer’s budget balanced. Though the Weighted Bipartite HVCG protocol requires a centralized mechanism, it can be managed efficiently and reach near optimal solutions in real world situations, in light of the fact that an auctioneer manager exists in the real world ad exchange environment.

5. Conclusions

In this paper, we consider an ad exchange marketplace, where publishers, who are willing to dedicate space on their Website to ads, and advertisers, are brought to a common and automatic marketplace. In particular, we consider situations in which the publishers have preferences concerning the identity of the ads published in their ad space, in addition to their desire to earn money for the ads. Our goal is to increase the satisfaction of all the participants in the auction, by using an efficient, fair and truthful protocol for the decision about the ad allocation and pricing. In order to enable optimal allocation given the preferences of all sides, while maintaining a balanced auctioneer budget, we developed the Weighted Bipartite HVCG protocol, which is a variation of the classic VCG mechanism for the pricing task and the Hungarian algorithm for the ad allocation.

We compared the Weighted Bipartite HVCG to six other ad allocation mechanisms: (a) the Distributed Reallocation Protocol; (b) the Simultaneous English Auction; (c) the Gale and Shapley protocol; (d) the HVCG; (e) the Generalized Second Price protocol; (f) the advertisers’ aimed HVCG. We found that when considering the budget balanced protocols, the Weighted Bipartite HVCG reached the best solution, while being truthful and individually rational for both the advertisers’ and the publishers’ side.

We revealed that the Weighted Bipartite HVCG protocol was able to maintain the desired Vickery-Clarks-Grove properties, while achieving near optimal results (98% to 99% of the optimal total utility obtained by the classical HVCG protocol). The advantage of the Weighted Bipartite HVCG over the classical VCGH is in the fact that it is able to maintain a balanced budget for the auctioneer, and thus, it can be applied in real world situations.

The other heuristic protocols reach less efficient results. The Distributed Reallocation Protocol, the Simultaneous English Auction and the Generalized Second Price, achieve 80%–90% of the optimal allocation efficiency derived by the HVCG. The Gale and Shapley protocols achieve similar results, and when checking which variation of the Gale and Shapley protocols (when the publishers set the offers or when the advertisers set the offers) is more efficient, we found that it depends on the number of slots offered by each publisher. Note, however, that the Simultaneous English Auction and the Gale and Shapley protocols are not truthful with respect to the publisher’s side when the advertisers are the offerors and when the publishers are the offerors the Gale and Shapley protocol is not truthful with respect to the advertiser’s side. In conclusion, we found the Weighted Bipartite HVCG to be the most preferred protocol for the preference driven ad exchange: it is truthful, individually rational and budget balanced, and it reached results that were near the optimal results, and were more efficient with respect to the other proposed budget balanced protocols.

In future work we would like to find the optimal weight values for the auctioneer, given the fact that he competes with other auctioneers. In addition, we intend to consider dynamic environments where ad auctions are repeatedly performed and the click through rates vary over time. Finally, we intend to propose techniques for building the utility function of the publishers as a function of the ads’ attributes.

Footnotes

Authors’ Bios

Rina Azoulay received her BA degree in economics and computer science from Bar-Ilan University in 1995. She received her MSc (1997) and PhD (2001) degrees in Computer Science from Bar-Ilan University. She is a senior lecturer in the Computer Science Department the Jerusalem College of Technology, Israel.

Esther David (Ph.D. in computer science, Bar-Ilan University, 2004) is a Senior Lecturer in the Department of Computer Science at Ashkelon Academic College, Israel. She spent three years (2003–2006) as a post doc researcher at the Intelligence, Agents and Multimedia (IAM) group at Southampton University, UK under the supervision of Nicholas Jennings. She leaded the Agent-Based control of decentralized system project founded by the Data and Information Fusion. She has over 50 publications in leading AI conferences and Journals.

References

Abrams

and Schwarz

, Ad auction design and user experience, Applied Economics Research Bulletin, Special Issue 1 (Auctions) (March 2008), 98–105.

adBrite http://www.adbrite.com/.

Aggarwal

Goel

and Motwani

, Truthful auctions for pricing search keywords, in: ACM-EC 2006, Ann Arbor, MI, USA (11–15 June 2006), 1–7.

Aggarwal

Muthukrishnan

Pa’l

and Pa’l

, General auction mechanism for search advertising, in: WWW-2009, Madrid, Spain (20–24 Apr 2009), 241–250.

Ashkan

and Clarke

C.L.A.

, Impact of query intent and search context on click through behavior in sponsored search, Knowledge and Information Systems 34(2) (2013), 425–452.

Athey

and Ellison

, Position auctions with consumersearch, The Quarterly Journal of Economics 126(3) (2011), 1213–1270.

Azoulay

and David

, Truthful and efficient mechanisms for Website dependent advertising auctions, Multiagent and Grid Systems 10(2) (2014), 67–94.

Babioff

and Walsh

W.E.

, Incentive-compatible, budget-balanced, yet highly efficient auctions for supply chain formation, Decision Support Systems 39(1) (2005), 123–149.

Cavallo

, Optimal decision-making with minimal waste: Strategy proof redistribution of VCG payments, AAMAS-06, Hakodate, Japan (8–12 May 2006), 882–889.

10.

Cramton

, Ascending auctions, European Economic Review 42(3–5) (1998), 745–756.

11.

Cramton

Shoham

and Steinberg

(eds), Combinatorial Auctions, MIT Press, 2005.

12.

David

and Azoulay

, No more damaging ads on your own webpage – strategy proof mechanisms for ad placement, IAT-2012, Macau, China (4–7 December 2012), 140–145.

13.

Dütting

Roughgarden

and Talgam-Cohen

, Modularity and greed in double auctions, in: Proceedings of the 15th ACM Conference on Economics and Computation, Palo Alto, California, USA (2014), 241–258.

14.

Dütting

Henzinger

and Weber

, An expressive mechanism for auctions on the web, in: Proceedings of the 20th International Conference on World Wide Web, Hyderabad, India (28 March–1 April 2011), 127–136.

15.

Edelman

Ostrovsky

and Schwarz

, Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords, The American Economic Review 97(1) (2007), 242–259.

16.

Edelman

and Schwarz

, Optimal auction design and equilibrium selection in sponsored search auctions, The American Economic Review 100(2) (2010), 597–602.

17.

Faltings

, A budget-balanced, incentive-compatible scheme for social choice, in agent-mediated electronic commerce VI, theories for and engineering of distributed mechanisms and systems, Lecture Notes in Computer Science 3435 (2005), 30–43.

18.

Gale

and Shapley

L.S.

, College admissions and the stability of marriage, The American Mathematical Monthly 69(1) (1962), 9–15.

19.

Google Doubleclick www.google.com/adexchange/AdExchangeOverview.pdf, product information at http://www.doubleclick.com/products/advertisingexchange/index.aspx. In http://www.doubleclick.com.

20.

Google DobuleClick, Regulate your content through Ad Exchange rules, DoubleClick Ad Exchange Seller Help, in https://support.google.com/adxseller/answer/4584892?hl=en, visited 1.1.17.

21.

Groves

, Incentives in Teams, Econometrica 41(4) (1973), 617–631.

22.

Guo

and Conitzer

, Worst-case optimal redistribution of VCG payments, in: Proceedings of the 8th ACM Conference on Electronic Commerce, San Diego, California (11–15 June 2007), 30–39.

23.

Kuhn

H.W.

, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly 2(1–2) (1955), 83–97.

24.

Likhodedov

and Sandholm

T.W.

, Approximating revenue-maximizing combinatorial auctions, AAAI 2005, Pittsburgh, Pennsylvania (2005), 267–274.

25.

Likhodedov

and Sandholm

, Methods for boosting revenue in combinatorial auctions, Proceedings of the National Conference on Artificial Intelligence (AAAI), San Jose, California (25–29 July 2004), 232–237.

26.

Milgrom

, Putting auction theory to work: The simultaneous ascending auction, Journal of Political Economy 108(2) (2000), 245–272.

27.

Munkres

, Algorithms for the assignment and transportation problems, Journal of the Society for Industrial and Applied Mathematics 5(1) (1957), 32–38.

28.

Muthukrishnan

, Ad exchange: Research issues, Internet and Network Economics Lecture Notes in the Computer Science 5929 (2009), 1–12.

29.

Myerson

R.B.

and Satterthwaite

M.A.

, Efficient mechanisms for bilateral trading, Journal of Economic Theory 29(2) (1983), 265–281.

30.

Naroditskiy

Guo

Dufton

Polukarov

and Jennings

N.R.

, Redistribution of VCG payments in public project problems, in: Internet and Network Economics, Lecture Notes in Computer Science 7695 (2012), 323–336.

31.

Nisan

, Introduction to mechanism design (for computer scientists), in: Algorithmic Game Theory, chapter 9 Nisan

Roughgarden

Tardos

and Vazirani

editors, Cambridge University Press, 2007.

32.

OpenX http://www.openx.co/.

33.

RightMedia http://www.rightmedia.com/rightmedia.com/right-media-101/.

34.

Roberts

, The characterization of implementable social choice rules, in: Aggregation and Revelation of Preferences Laffont

J.J.

, eds, North-Holland Publishing Company, 1979, pp. 321–348.

35.

Shoham

and Leyton-Brown

, Multiagent Systems, Published by Cambridge University Press, 2010.

36.

Gao

Yang

and Liu

T.Y.

, Predicting advertiser bidding behaviors in sponsored search by rationality modeling, Proceedings of the 22nd International Conference on World Wide Web, Rio de Janeiro, Brazil (13–17 May 2013), 1433–1444.

37.

Yang

Feng

and Xiao

, Two pricing mechanisms in sponsored search advertising, Games 4 (2013), 125–143.

Auction mechanisms for preference driven ad exchanges

Abstract

Keywords

1. Introduction

2. Literature review

2.1 Related auction mechanisms and protocols

2.1.1 The Vickery-Clarks-Grove and its variations

2.1.2 The laddered auction and its use in the distributed reallocation protocol

2.1.3 The Simultaneous English Auction

2.1.4 Gale and Shapley protocol

2.1.5 The Generalized Second Price auction

2.1.6 The advertisers’ aimed HVCG

2.2 Bidding strategies in non-incentive-compatible auctions

2.3 Summary of the literature review

3. The preference driven ad exchange model and the proposed auction mechanisms

3.1 Description of the environment

3.1.1 The characteristics of the advertiser

3.2 Auction mechanisms for preference driven ad exchanges

3.2.2 The Weighted Bipartite HVCG

3.2.6 The Generalized Second Price protocol

3.2.7 Advertisers’ aimed HVCG protocol

4. Algorithms comparison and simulation results

4.1 Summary of the different protocols’ properties

Table 1 The properties of the different protocols

Table 2 The results of the different protocols

Table 4 Results when the ratio of #advertisers/#publishers is kept constant

Table 5 Results based on real click through rate values

Footnotes

Authors’ Bios

References

Table 1
The properties of the different protocols

Table 2
The results of the different protocols

Table 4
Results when the ratio of #advertisers/#publishers is kept constant

Table 5
Results based on real click through rate values