COOPETITIVE AD AUCTION SYSTEM AND METHOD

A single advertisement may provide benefits to multiple parties. The results discussed herein show that an ad auctioneer may improve both his own revenue and consumers' welfare by implementing an ad auction that allows cooperation among advertisers in a single ad while maintaining competition between ads. This may be called a “coopetitive” ad auction. An auction system may be configured to implement a coopetitive approach in which bids express complex preferences over ads. In particular, multiple bidders may be allowed to value a single ad, and a single bidder may be allowed to value multiple ads. Accordingly, an advertiser can derive value from clicks on multiple ads.

DETAILED DESCRIPTION

Example methods and systems are directed to auctions, such as auctions of advertisements (e.g., auctions of advertising space, time, or both) and, in particular example embodiments, coopetitive ad auctions. Ad auctions (e.g., search ad auctions) are discussed herein has illustrative examples of auctions that may implement any one or more of the methods and systems discussed herein. Examples merely typify possible variations. Unless explicitly stated otherwise, components and functions are optional and may be combined or subdivided, and operations may vary in sequence or be combined or subdivided. In the following description, for purposes of explanation, numerous specific details are set forth to provide a thorough understanding of example embodiments. It will be evident to one skilled in the art, however, that the present subject matter may be practiced without these specific details.

A single advertisement may provide benefits to multiple parties. For example, an ad for a Samsung laptop computer may benefit Microsoft, who sells the operating system for the laptop computer. This phenomenon may be studied with respect to auctions of search ads (e.g., auctions of advertisements shown to users of the search engine or “search advertising auctions”), and standard solutions may perform poorly. Such standard solutions include ignorance of mutual benefit and a benefit-aware Vickery-Clarke-Groves mechanism. In contrast, an appropriate first-price auction may exhibit nice equilibria in a single-slot ad auction. Such equilibria that satisfy a natural cooperative envy-freeness condition may select the welfare-maximizing ad and satisfy an intuitive lower-bound on revenue.

There may be several beneficiaries from the advertising of items and their subsequent sale. Imagine as an example that TigerDirect is selling a computer at a selling platform (e.g., eBay or Google). Suppose the computer is manufactured by Samsung, contains the latest Intel chip (e.g., processor), and has installed the Microsoft Office product and the Microsoft Windows operating system (OS). Imagine that the selling platform is configured to facilitate an advertisement auction in which the top listing on a web page is the one in which the selling platform makes the most money, the next highest listing on the web page is the one in which the selling platform makes the next highest amount of money, and so on. This type of auction might only take into account the additional profit which TigerDirect would make by selling this computer. Thus, only TigerDirect would be offering a bid to the selling platform. However, other stakeholders (e.g., Samsung, Intel, and Microsoft) in selling this computer may stand to profit if the computer is sold. According to example embodiments of the systems and methods discussed herein, the stakeholders may be provided with one or more direct ways in which to participate in the sale of the computer. An auction protocol is discussed herein, along with a mathematical analysis regarding the dynamics of how the bidding works in this auction protocol.

In 1991, Intel launched its “Intel Inside” advertising campaign and forever changed the way people buy computers. Previously, buyers only considered hardware insofar as it affected the software that would run on their new machine. The “Intel Inside” campaign aimed to change that behavior. Intel coordinated with PC vendors to advertise not only the processor's capabilities, but the Intel brand as well. Twenty years later, the “Intel Inside” mark has become one of the most recognized in the tech industry. Their signature five-note chime is known worldwide. Thus, today's buyers also think about the brand of processor inside their computer.

The benefit obtained from the “Intel Inside” campaign is an example of a general phenomenon. Intel has a vested interest in the sale of computers containing its products and, at least in an amortized sense, derives a specific benefit from every sale. Accordingly, a single advertisement may benefit many different companies. Companies may recognize this benefit and team up with partners in so-called cooperative advertising agreements (e.g., similar to the “Intel Inside” campaign). In 2000, an estimated $15 billion was spent on cooperative advertising in the United States alone. This phenomenon is also recognized in the operations research and marketing fields where it has been modeled using a variety of Stackelberg and dynamic games. In practical and theoretical realms, the question may be posed: how can companies who sell advertising space exploit the broad benefit of a single ad? This particular question is discussed herein in the context of online ad auctions. However, the methods and systems discussed herein may also be applied outside this context.

The results discussed herein indicate that an ad auctioneer (e.g., a facilitator or administrator of ad auctions) may improve both his own revenue and consumers' welfare by implementing an ad auction that allows cooperation among advertisers in a single ad on maintaining competition between ads. This may be termed a “coopetitive” ad auction. Coopetition may be used as a business term describing an environment where the same parties are simultaneously cooperating in some areas while competing in others. Also, as discussed below, external cooperative advertising contracts and the Vickery-Clarke-Groves (VCG) mechanism may perform poorly in a coopetitive ad auction (e.g., in comparison to a first-price auction).

FIG. 1is a screen capture illustrating ads (e.g., search ads) displayed on a web page100of search results returned by a search engine, according to some example embodiments.FIG. 1shows a real query110in which a search engine's ad auction produces an outcome that fails to provide coopetitive benefits. In contrast and as discussed below, equilibria of a first-price auction which satisfy a cooperative envy-freeness condition may have a natural performance guarantee similar to that of a second-price auction.

As shown inFIG. 1, a search engine's web page100of search results for the query110for “samsung intel laptop” illustrates what may happen when the mutual benefits of an ad are ignored. A top-slotted ad120for “Intel Laptops” is competing against an ad130that appears below it for “Samsung Series 9 w/ Intel.” In reality, Intel would benefit if a user clicks on the Samsung ad130(and possibly even a Newegg ad140below both), and thus Intel should be unwilling to pay the premium costs of winning the top ad slot for the “Intel Laptops” ad120.

Hence, web page advertisements may directly or indirectly benefit multiple parties (e.g., mutually and cooperatively). For example, an iPhone ad benefits cell phone providers; a Samsung ad for a Windows laptop benefits Microsoft; and an ad for the Boston Red Sox benefits a bar across the street from Fenway Park. Moreover, these secondary benefits may be significant. For example, when Best Buy sells a Samsung laptop running Windows, Microsoft may generate more money than either Best Buy or Samsung from the laptop's sale. As a result, companies may have stronger incentives to share advertising costs, particularly when competing against a more integrated adversary, such as when Microsoft and Samsung compete together against Apple.

One technique for pooling advertising dollars is an ad-hoc system of external contracts (e.g., external cooperative advertising contracts). In such external contracts, one company agrees to pay a portion of another's advertising costs when its own branding is included in the ads. In the Intel example, Intel agrees to pay a percentage of the advertising costs when Samsung or Dell include the “Intel Inside” branding in their ad.

In the research community, cooperative advertising may be studied in marketing and operations research. The setting may be modeled as a Stackelberg game in which an upstream manufacturer makes an offer to downstream manufacturers or retailers, sometimes incorporating dynamic components. In some example embodiments, the upstream manufacturer is not the first mover (e.g., in proposing an external contract), and the external contracts may be based on alternative bargaining solutions.

Search advertising may be sold through a pay-per-click (PPC, also called “price-per-click”) ad auction. In certain example embodiments, each bidder comes to the auction with its own ad and places a bid in terms of its willingness to pay for each click. The ad auctioneer may subsequently assign ads to ad slots on the web page. Thus, bidders may compete for slots. In some example embodiments, the ad auctioneer might only charge a bidder when the bidder's ad is selected (e.g., clicked).

In some example embodiments of a PPC ad auction, the only way for advertisers to share costs is through external contracts. Unfortunately, this approach may create undesirable results in an auction format. For example, an advertiser (e.g., a manufacturer) may compete with itself. As depicted inFIG. 1, the search engine query110for “samsung intel laptop” may return a web page (e.g., web page100of search results) in which the ad120from Intel is shown above the Samsung ad130that explicitly advertises Intel-based laptops. In general, Intel should be happy if the buyer visits Samsung's web site with an intent to buy an Intel-based laptop. Thus, even if Intel would prefer that the user click on its own ad120instead of Samsung's ad130, Intel should be unhappy paying a premium cost to beat Samsung in the ad auction for the top slot on the web page (e.g., web page100).

Another downside to external cooperative advertising agreements is that downstream producers may face a moral hazard. In some situations, the downstream producer may be incentivized to overspend on advertising and, thus, waste the upstream manufacturer's money. In the worst case scenario, the upstream manufacturer refuses to participate and cooperation collapses entirely. Examples of both phenomena are provided below.

The example methods and systems described herein (e.g., in the context of theories of mechanism design) implement another approach in which bids express complex preferences over ads. In particular, such example methods and systems allow multiple bidders to value a single ad and may allow a single bidder to value multiple ads. Performance of such example methods and systems may depend on the mechanism (e.g., auction algorithm) implemented. For example, a Vickery-Clarke-Groves (VCG) auction may generate little or no revenue. The implicit cooperation among advertisers, which may be desired, may mimic the kind of strategic collusion that reduces revenue in VCG mechanisms.

In contrast to external contracts and VCG mechanisms, first-price auctions which consider bidders' complex preferences may generally have nice equilibria in single slot settings. In the discussion below, the intuition of a second-price auction is generalized to give a lower-bound on the revenue that the auctioneer should expect. Also, the discussion below shows that equilibria (e.g., all equilibria) satisfying a natural cooperative envy-freeness condition will maximize welfare while satisfying this revenue lower-bound. It will be further shown that the cooperatively envy-free (CEF) equilibria dominate VCG auctions in terms of revenue. Each individual bidder pays more in the first-price auction than in the VCG mechanism.

Moreover, the below discussion shows how such cooperative envy-free equilibria can be found. The envy-freeness constraints define a polytope of which the equilibria form the Pareto frontier, and the below discussion introduces a family of convex programs for computing equilibria. Furthermore, the egalitarian equilibrium is specifically identified, and an efficient algorithm for computing it is provided herein.

According to various example embodiments, first-price auctions may be preferable to VCG and generalized second-price (GSP) auctions. For example, first-price auctions tend to be more transparent. Since prices precisely correspond to bids, bidders do not face uncertainty in their payments, and there is no opportunity for the auctioneer to manipulate the auction, particularly by learning in a repeated setting.

The systems and methods discussed herein may be applied to auctions with externalities. Whereas simple auction models may assume players (e.g., bidders) are indifferent to the bundle received by another player (e.g., a bidder), in reality there may be externalities. For example, players may care about the bundles received by other agents (e.g., bidders). Incorporation of externalities (e.g., accounting for one or more externalities) may produce an auction mechanism in which bidders can express a different value for every possible outcome. The methods and systems discussed herein might not always have nice interpretations in terms of externalities. However, like mechanisms that account for externalities, such methods and systems might not be easily expressed in a standard bidding language and, in extreme situations, may degenerate into a mechanism which involves bidders expressing a value for every possible outcome.

A coopetitive advertising model may be or include a generalized form of a PPC advertising auction. As in a PPC auction, the auctioneer in a coopetitive ad auction chooses which of m competing ads to show in s slots. Each advertiser derives a value of v from a click on one of its ads and has a utility that is quasi-linear in money, e.g., u(p)=v−p when the advertiser gets a click and pays p. The likelihood that a user clicks on ad j in slot k, called the click-through-rate (CTR), is given by cj,k. Hence, the expected utility of a bidder whose ad is shown in slot with CTR c is E[ui(pi)]=c(v−p). The discussion herein focuses on a special case with only one slot (s=1) where CTRs are independent of the ad. In this case, the CTR can be taken to be 1 without loss of generality, so CTRs may be disregarded for the purposes of the discussion herein.

A new feature of the coopetitive model is that an advertiser can derive value from clicks on multiple ads. In general, the advertiser i's value for a click vi,jdepends on the particular ad j. However, for the sake of clarity, a simpler model is presently discussed.

An advertisement j∈{1, . . . , m} is defined by a publicly-known set of advertisers Sj⊂[n] who all derive value from a click on the advertisement j. Advertiser i derives the same value vifrom a click on any ad j where i∈Sj(and advertiser does not benefit if i∉Sj). Let T denote the ad set of bidders in the ad with the maximum total value such that T=argmaxSjΣi∈Sjvi(in case of a tie, T denotes the particular winning ad chosen by the auction). The results discussed herein are generalized to the more complicated vi,jsetting by considering equilibria where a bidder bids for the same surplus vi,j−bi,jin each ad.

In the discussion below, shorthand may be used for certain examples. This notation is itself best described by an example:

This example denotes an auction with three advertisers A, B, and C whose values are 2, 1, and 3 respectively. Everyone derives value when the first ad (A2;B1;C3) is shown; only advertisers A and B benefit from the second ad; and only advertiser C benefits from the third.

External contracts provide a way in which advertisers may cooperate. Each ad may be “owned” (e.g., purchased or won) by a single bidder, and any party wishing to increase the bid on an ad may negotiate an external contract with the ad's owner.

This may be modeled as a standard VCG PPC ad auction in which advertiser i can commit to pay an αifraction of the cost each time one of its ads is clicked, up to a maximum βi. This payment goes directly to the owner o(j) of the clicked ad j. Thus, the utility of advertiser i would be

ui=vi−min(αipo(i),βi), while the utility of the ads owner o(j) would be uo(j)=vo(j)−po(j)+min(αipo(j),βi).

In the setting discussed herein, with a single slot, a VCG mechanism chooses the ad j that maximizes Σi∈Sjviand charges the bidder i the minimum value he needed to have to secure the winning ad. Bidders submit their true values vi, because VCG auctions are incentive compatible.

In a first-price auction, however, each advertiser submits a bid bi. The auctioneer displays the ad j that maximizes Σi∈Sjbi, and the auctioneer charges each bidder in the winning ad pi=biwhen the ad is clicked.

Many standard mechanisms may behave poorly with respect to advertisers coopetitive valuations. For example,FIG. 1shows how one ad auction system caused Intel to compete against itself.

A few pitfalls specifically arise with the use of external contracts. First, if an external contract is made with insufficient granularity, an advertiser might easily compete with itself:

Consider the following two single-slot ad auctions:

In the first ad auction, M will happily contribute advertising funds to help beat A; however, in the second auction M wins regardless. The only effect of M's dollars in the second auction is to fund a useless bidding war between the SM and DM ads.

In reality, the granularity of cooperative advertising contracts may be somewhat limited, so this may be a legitimate concern in spite of the fact that it is clearly not an equilibrium for M to offer a cooperative advertising contract in the second auction.

Additionally, the advertiser receiving the external contract may face a moral hazard; he may be incentivized to overspend the money of his advertising partner. In equilibrium, a potential result is that cooperation collapses:

Consider the following three ads with four interested parties:

Suppose there are three ad slots with CTRs of 0.1, 0.08, and 0.05 respectively. If a bidder appears in multiple ads, their likelihood of a click is the sum of the likelihoods for those ads.

In the external contracts model described above, M will not offer a cooperative advertising contract in equilibrium. As a result, not only will revenue be hurt, but the auction will be inefficient, because the (A11) ad wins the auction.

In contrast to an external contract, a VCG auction mechanism charges a player based on the externality the player imposes on other users (e.g., the welfare that others lose because of the player's presence). A potential downside of the VCG mechanism may be a failure to generate any revenue. Collusion may have a negative effect on revenue in the VCG mechanism. While such collusion can be illegal in other settings, it may be desirable for advertisers to cooperate on ads that are of mutual benefit in coopetitive ad auctions.

For example, two players can make their payments zero by simultaneously claiming sufficiently large values for the winning outcome o. If the players' bids are sufficiently large that o is still the welfare-maximizing outcome, even if one of the pair were removed, the externality that each player imposes is zero, and no player pays anything. This may happen in coopetitive ad auctions. For example:

In the following single slot ad auction {(A1,B1,C1,D1), (E3)}, the VCG mechanism shows the first ad in the slot, but nobody pays anything.

In this case, the ABCD ad remains the best ad, even if a single bidder is removed. As a result, no players pay. Such a scenario may occur when many players value the winning ad. For example, such a case can occur naturally if a single ad is valued by many small bidders.

The weak revenue of the VCG mechanism may not be limited to extremes like the above example. In general, payments may be lower than an auctioneer might hope. For example:

In the following single slot ad auction, {(A2,B2), (E3)}, the VCG mechanism shows the first ad in the slot, and players A and B each pay 1.

Intuition may suggest that the auctioneer should hope to make A and B pay a total of 3, since that is the total bid required to beat E. However, the total VCG payment for the first ad is only 2. In contrast, a coopetitive first-price auction would indeed generate a revenue of 3, as discussed below.

It may be useful to consider the behavior (e.g., equilibria) of first-price auctions in a coopetitive ad auction. Coopetitive ad auctions may differ from non-coopetitive ad auctions in that advertisers involved in the same ad are expected to cooperate on that ad, but remain competitors across other ads. For example, two sponsors (e.g., members) of a losing ad may jointly raise their bids so as to make their joint ad win.

Accordingly, the discussion presently focuses on first-price auction equilibria that are CEF. By this, it is meant that no cooperating advertisers in a losing ad can jointly raise their bids to beat out the presently winning ad. If a losing ad shares bidders with the winning ad, then it is only the advertisers not participating in either ad which affect this condition.

Definition 1: The bids (bi)i∈T for the winning ad T are CEF if and only if for all alternate ads Sj,

Furthermore, the agents bidding may be individually rational (IR), such that for each advertiser i, 0≦bi≦vi.

Combining IR and CEF yields efficiency. If the bids of agents in T\Sjare at least the values of agents in Sj\T, then so too are the values of the agents in T\Sj.

Lemma 4.1: If the bids (bi)i∈T or the winning ad T are IR and CEF, then T is the efficient winning ad.

These CEF and IR conditions form a polytope of possible payments associated with the correct winning ad. Not all of these are equilibria; those that are not equilibria will instead form the lower frontier of the polytope. On this frontier, there can still be many possible equilibria. Consider the following ad auction: {A100,B100), (C99)}. Every set of bids bA=x, bB=99−x for 0≦x≦99 constitutes an equilibrium.

Now, consider the equilibrium conditions. By CEF, no losing advertisers will be able to raise their bids and affect the outcome. Hence, it is sufficient to worry only about the winning bidders lowering their bids.

Lemma 4.2: The IR, CEF bids (bi) form an equilibrium for the winning ad T if and only if for each bidder k, bk=0 or there exists an ad Sjk such that

Proof First, consider the “if” direction. Assume such an Sjexists for every k. If k were to lower his bid, Sj would win, and k would no longer be in the winning set.

Consider the other direction. Assume a set of equilibrium bids are CEF and IR. For every winning advertiser k, they must not be able to lower their bids and still win. Otherwise, the winning advertiser k would lower his bid, and there will be no equilibrium. Thus, for any k such that bk>0, there is such a set Sj.

Next, consider the revenue behavior of equilibrium points in the polytope. First, it is noted that the revenue is not the same for all equilibrium points. This is not simply a matter of dividing up a fixed payment. As an example, consider the following setting with three ads and five interested parties: {(A1,B1,C1), (A1,D1), (B1,E1)}. The first ad should win, but what should the payments be?

The CEF and IR conditions result in the following polytope: bA+bC≧1, bB+bC≧1, 0≦bA, bB, bC≦1. The set of equilibrium points includes (1, 0, 1), (0, 1, 0) and every convex combination of the two. Thus, the revenue of the equilibrium points may range from 1 to 2.

How would other mechanisms fare? VCG would charge nothing, because no advertiser is integral to the ad being displayed. If A and B were to lie and say they are not affiliated with C or D, then any second-price or first-price mechanism would insist on a payment of 1 from the three of them. In this example, the revenues of the first price equilibria are lower bounded by VCG, and by simpler first-price and second-price auctions.

Lemma 4.3: For every point in the IR, CEF polytope, the bids of each advertiser are lower bounded by their VCG payments.
Proof: Consider advertiser i. Let T be the winning ad, and let Sjbe the winning ad without i. If Sj=T, then i's VCG payment is 0, and hence it is sufficient to only worry about the case that Sj≠T. By the CEF constraints,

The latter quantity is exactly i's VCG payment, and hence every advertiser's bid is at least their VCG payment.

One possible way of dealing with these situations, after determining which ad is the winning ad, is for all members of the winning ad to pretend to be uninterested in the losing ads. At this point, the members of the winning ad negotiate among themselves on how to split up a payment of the maximum bid throughout all other ads. The revenue of every point in the polytope will be at least the revenue of this mechanism.

Lemma 4.4: The revenue of any equilibria in the IR, CEF polytope is at least the maximum total value of non-winning advertisers in a non-winning ad.

This lemma follows directly from the CEF conditions. Note that this is the same as the revenue that a second-price auction would get if it treated advertisements as single agents and removed any interests of winning advertisers in losing ads.

Thus, any first-price equilibria that satisfies CEF (e.g., no losing advertisers can collaborate to increase their bids and win) has good revenue that beats both the VCG approach and an analogue to a second-price auction.

An egalitarian solution is presently considered. As discussed above, there are many ways the winners can split up payments while still satisfying the aforementioned equilibria and cooperative envy-freeness constraints. In a first-price auction, an exact split that bidders may be expected to reach may depend on preferences and bidding dynamics of the advertisers.

The present discussion considers one such split in particular: the egalitarian bargaining solution. In the egalitarian bargaining solution, the utility of the worst-off player is maximized, and on up the line. This can be defined as the equilibrium with the lexicographically maximum surplus (e.g., an equilibrium with and a lexicographically maximum surplus):

Definition 2: The egalitarian solution in the coopetitive first-price auction is an equilibrium that displays the highest surplus ad and charges advertisers so that the surplus vector is lexicographically maximal when bidders are ordered in terms of increasing surplus.

In many normal settings, this will result in all players sharing the generated surplus equally.

The egalitarian equilibrium may be algorithmically computed (e.g., by a machine, which may form all or part of a network-based system, such as a network-based commerce system or a network-based auction system) by repeatedly lowering bids uniformly. An example embodiment of such an algorithm is described in Algorithm 1.

Algorithm 1: An algorithm is presently described for computing the egalitarian equilibrium in a single-slot first-price auction.
Input: a coopetitive ad auction problem
Output: the egalitarian equilibrium bids bi.1. Set the bids of all advertisers to their values. Call T the winning ad.2. Lower bids of advertisers in the winning ad T uniformly until some bidder i reaches bi=0 or a constraint Σi∈Tbi≧Σi∈Sjbiwould be violated for some ad Sj.3. Fix the bids of advertisers in T\Sjor fix the bid of i if bireached 0).4. Repeat (2) and (3), lowering only unfixed bids until all bidders in T are fixed.
Lemma 5.1: Algorithm 1 computes the egalitarian equilibrium point.
Proof: First, it will be shown that the resulting point is efficient and cooperatively envy-free. Then, it will be shown that the resulting equilibrium is an egalitarian one.
Begin with the following assertion:
Assertion 1: The total bid for the winning ad T never drops below the bids of non-winning ads.
At any point, the algorithm lowers only the bids of players in every ad tied for the highest value. As a result, every ad tied for the highest value is decreasing by the same amount. Thus, the winning ad at the beginning of the algorithm remains the winning ad at the end and hence the final winning ad is the ad with the most surplus.

At the end of the auction, as T remains the ad with the highest value and no non-winning advertisers see their surpluses decrease, the CEF constraints are satisfied for every alternate ad Sj.

By Lemma 4.2, the point will be in equilibrium if and only if there is a set for every agent tied with the winning set that he is not in. The algorithm will stop when, for every bidder, there is such a set, or they are bidding zero. Hence, such an equilibrium may be reached.

Thus, the final point is an efficient, CEF point. The present discussion considers whether or not this final point is in fact the egalitarian solution. This may be proven with induction. Assume that the algorithm gives the egalitarian bargaining solution for the first i−1 lowest surplus advertisers. Next, consider the algorithm after those advertisers are fixed. In particular, the next time an advertiser has their bid fixed, with a surplus of z. At this point, there will be a set Sjsuch that

First, note that the algorithm cannot reduce the bid of i further than the egalitarian solution. Otherwise, that would result in the egalitarian solution. Assume now that the algorithm results in a lower surplus for player i. Hence, i's bid is fixed before being lowered to his egalitarian surplus. According to the above mentioned assumptions,

By the CEF constraints in the egalitarian solution,

Then, Σi∈T\Sjmax(vi−z,b′i)<Σi∈T\Sjbiand hence Σi∈T\Sjb′i=Σi∈T\Sjbi, since all advertisers with surplus less than z have the egalitarian surplus, and all advertisers with more surplus are in Sj, b′i=bi

As discussed above, a wide variety of ads provide value to more than one party, for example, ads for computers, cell phones, and even baseball teams, to name a few. As evidenced by the “samsung intel laptop” query110shown inFIG. 1, ad auctions without support for coopetitive ads discussed herein may completely fail to account for such shared benefits. While a search engine may enjoy a little extra revenue at Intel's expense in the interim,FIG. 1does not represent a sustainable equilibrium. The theoretical results presented herein show that failure to account for the shared benefit of an advertisement can have a substantial negative effect on both welfare and revenue.

As a possible solution, it was shown above that a coopetitive first-price auction behaves well in equilibrium. In particular, all equilibria that satisfy cooperative envy-freeness may be efficient and may generate good revenue. Moreover, such equilibria may be efficiently computed. Finally, as noted above, these results may be generalized to a model where bidders have different values for different ads.

FIG. 2is a network diagram illustrating a network environment200suitable for a coopetitive auction, according to some example embodiments. The network environment200includes an ad auction machine210, a database215, and devices230,240,250,260, and270, all communicatively coupled to each other via a network290. The ad auction machine210, the database215, and the devices230,240,250,260, and270may each be implemented in a computer system, in whole or in part, as described below with respect toFIG. 6.

The ad auction machine210may be configured (e.g., by software, such as software modules) to implement a coopetitive ad auction, in whole or in part. The database215may store ads, web pages, bids, payments, or any suitable combination thereof, in support of one or more operations performed by the ad auction machine210. The ad auction machine210, with or without the database215, may form all or part of a network-based system205(e.g., a cloud-based server system) that provides one or more network-based auction services.

Also shown inFIG. 2are users232,242,252,262, and272. One or more of the users232,242,252,262, and272may be a human user (e.g., a human being), a machine user (e.g., a computer configured by a software program to interact with a device, such as the device230), or any suitable combination thereof (e.g., a human assisted by a machine or a machine supervised by a human). As shown inFIG. 2, the user232may be an advertiser (e.g., a first advertiser, who may be a seller of an item available for sale). The user242may be an advertiser (e.g., a second advertiser, who may be a manufacturer of a component of the item available for sale, or a manufacturer of software installed in the item available for sale). The user252may be a viewer of a web page (e.g., a search results web page, such as web page100) generated by the network-based system205(e.g., by the ad auction machine210). For example, the user252may be an online shopper, a potential buyer of the item available for sale, or both. The user262may be an advertiser (e.g., a third advertiser, who may be a seller of a different item available for sale), and the user272may be an advertiser (e.g., fourth advertiser, who may be a manufacturer of a component of the different item, or a manufacturer of software installed in the different item). As shown inFIG. 2, the users232and242may constitute a group of sponsors235of a coopetitive ad for an item (e.g., an item whose sale benefits both the users232and242). Likewise, the users262and272may form a similar group of advertisers or sponsors.

The user232is not part of the network environment200, but is associated with the device230and may be a user of the device230. For example, the device230may be a desktop computer, a vehicle computer, a tablet computer, a navigational device, a portable media device, or a smart phone belonging to the user232. Likewise, the user242is not part of the network environment200, but is associated with the device240. As an example, the device240may be a desktop computer, a vehicle computer, a tablet computer, a navigational device, a portable media device, or a smart phone belonging to the user242. Similar relationships may exist between the user252and the device250, between the user262and the device260, and the user272and the device270.

The network290may be any network that enables communication between or among machines, databases, and devices (e.g., the ad auction machine210and the device230). Accordingly, the network290may be a wired network, a wireless network (e.g., a mobile or cellular network), or any suitable combination thereof. The network290may include one or more portions that constitute a private network, a public network (e.g., the Internet), or any suitable combination thereof.

FIG. 3is a block diagram illustrating components of the ad auction machine210, according to some example embodiments. The ad auction machine210is shown as including an auctioneer module310, a bid module320, a results module330, a presentation module340, and a payment module350, all configured to communicate with each other (e.g., via a bus, shared memory, or a switch). Functions of the various modules shown inFIG. 3are discussed below with respect toFIGS. 4 and 5.

Any one or more of the modules described herein may be implemented using hardware (e.g., a processor of a machine) or a combination of hardware and software. For example, any module described herein may configure a processor to perform the operations described herein for that module. Moreover, any two or more of these modules may be combined into a single module, and the functions described herein for a single module may be subdivided among multiple modules. Furthermore, according to various example embodiments, modules described herein as being implemented within a single machine, database, or device may be distributed across multiple machines, databases, or devices.

FIGS. 4 and 5are flowcharts illustrating operations of the ad auction machine210in performing a method400of implementing a coopetitive ad auction, according to some example embodiments. Operations in the method400may be performed by the ad auction machine210, using modules described above with respect toFIG. 3. As shown inFIG. 4, the method400includes operations410,420,430, and440, and may include operation450.

In operation410, the auctioneer module310initiates an ad auction (e.g., a coopetitive auction of one or more search ad slots) to determine which of multiple ads (e.g., search ads) wins placement in an ad slot within a web page (e.g., web page100of search results). As discussed above, the multiple ads may include one or more coopetitive ads. In particular, a coopetitive ad among the multiple ads may advertise an item whose sale benefits multiple advertisers, such as a first advertiser (e.g., user232) and a second advertiser (e.g., user242). As an example, the item advertised by the coopetitive ad may be purchasable from the first advertiser and may include a component (e.g., a part) that is manufactured by the second advertiser. This situation is illustrated above with respect to a Samsung laptop with an Intel processor. As another example, the item advertised by the coopetitive ad may be purchasable from the first advertiser and includes software that is manufactured by the second advertiser. The situation is illustrated above with respect to a Samsung laptop having a Microsoft operating system. As described above, the first and second advertisers (e.g., users232and242) may both be sponsors (e.g., co-sponsors or members) of the coopetitive ad and may both be bidders to place the coopetitive ad in the ad slot within the web page (e.g., web page100of search results).

In operation420, the bid module320receives a first bid from the first advertiser (e.g., user232). This first bid may be an auction bid to win the ad slot for the coopetitive ad. By this submission, the first advertiser may become a bidder on the ad slot, a sponsor (e.g., co-sponsor) of the coopetitive ad, or both. In some example embodiments, the first bid is treated as a first partial bid (e.g., first fractional bid) to be combined with other partial bids into an aggregate bid submitted by multiple co-sponsors of the coopetitive ad. In some example embodiments, the first bid represents a first price-per-click that the first advertiser is willing to pay (e.g., in cooperation with the second advertiser) for placement of the coopetitive ad into the ad slot within the web page (e.g., web page100of search results).

In operation430, the bid module320receives a second bid from the second advertiser (e.g., user242), and the second bid may be an auction bid to win the ad slot for the coopetitive ad. By this submission, the second advertiser may also become a bidder on the ad slot, a sponsor (e.g., co-sponsor) of the coopetitive ad, or both. In some example embodiments, the second bid is treated as a second partial bid (e.g., second fractional bid) to be combined with other partial bids into an aggregate bid submitted by multiple co-sponsors of the coopetitive ad. In some example embodiments, the second bid represents a second price-per-click that the second advertiser is willing to pay (e.g., in cooperation with the first advertiser) for placement of the coopetitive ad into the ad slot within the web page (e.g., web page100).

In operation440, the results module330determines the winning ad based on bids received by the bid module320(e.g., in operations420and430). For example, the results module330may determine that the coopetitive ad (e.g., co-sponsored by the first and second advertisers) wins placement in the ad slot within the web page. This determination may be made based on a sum of the first and second bids to win the ad slot for the coopetitive ad. As an example, the sum of the first and second bids may exceed (e.g., be larger than) a sum of bids to win the ad slot for a competing ad (e.g., a different coopetitive ad co-sponsored by the users262and272) among the multiple ads. For example, supposing that the ad auction is a first-price auction, each advertiser may submit a bid bi. The results module330may determine the winner of the ad auction to be the ad j that maximizes Σi∈Sjbi.

In operation450, the presentation module340causes the web page (e.g., web page100of search results) to display the coopetitive ad (e.g., as the winner of the ad slot in the ad auction) in the ad slot. According to certain example embodiments, the presentation module340may be or include a web server, a web page generator (e.g., static or dynamic), or any suitable combination thereof. Operation450may be performed in response to the determining (e.g., the determination) that the coopetitive ad wins the ad slot in operation440.

As shown inFIG. 5, the method400may include one or more of operations522,542,544,546,548,552,554,556,560,570, and580, according to various example embodiments. For example, operation522may be performed before operation440(e.g., between operations420and430). In some example embodiments, the ad slot discussed above with respect to operation420is a top-ranked ad slot (e.g., a highest or most prominent ad location within the web page) among multiple ad slots that are available on the web page (e.g., web page100). In such situations, the ad auction may determine which ads will appear in multiple ad slots, such as a second-ranked ad slot (e.g., a next highest or next most prominent application within the web page). In operation522, the bid module320receives another bid (e.g., a third bid) from the first advertiser (e.g., user232), and this bid may be an auction bid to win a second-ranked ad slot for the coopetitive ad. Moreover, this bid may be different from the first bid discussed above with respect to operation420. That is, the first advertiser (e.g., user232) may submit different bids (e.g., bid different prices-per-click) for placing the coopetitive ad in the top-ranked ad slot and for placing the coopetitive ad in the second-ranked ad slot.

One or more of operations542,544,546, and548may be performed as part (e.g., a precursor task, a subroutine, or a portion) of operation440, in which the results module330determines the winning ad (e.g., the coopetitive ad) for the ad slot. In operation542, the results module330calculates the sum of the first bid and the second bid (e.g., the sum of the first and second bids, as received in operations420and430). As noted below with respect to operation546, operation440may be performed based on this calculated sum. For example, operation440may be performed based on this calculated sum being larger than a competing sum of bids to win the ad slot for a competing ad. That is, operation440may be performed based on this calculated sum maximizing Σi∈Sjbi.

In operation544, a similar calculation is performed for the competing sum of bids to win the ad slot for the competing ad. Specifically, the results module330calculates the sum of competing bids to win the same ad slot for the competing ad (e.g., a different coopetitive ad that advertises a further item whose sale benefits a third advertiser and a fourth advertiser, such as the users262and272). For example, the competing ad may be sponsored (e.g., co-sponsored) by multiple advertisers (e.g., users262and272) that each submitted a separate bid for placement of the competing ad into the ad slot. Such separate bids may be received during the ad auction by the bid module320prior to operation440. These separate bids may be summed to calculate the result of operation544. As noted below with respect to operation546, operation440may be based on this calculated sum. For example, operation440may be performed based on this calculated sum being smaller than the sum calculated in operation542.

In operation546, the results module330determines that the coopetitive ad discussed above with respect to operation440wins the top-ranked ad slot within the web page (e.g., web page100of search results). As noted above, this determination may be based on the result of operation542, the result of operation544, or both.

In operation548, a similar determination is made for a second-ranked ad slot within the web page (e.g., web page100of search results). For example, the results module330may determine that a competing ad (e.g., a different coopetitive ad co-sponsored by a third advertiser and a fourth advertiser, such as the users262and272) wins the second-ranked ad slot. This determination may be based on calculated sums of bids for placing one or more ads into the second-ranked ad slot (e.g., a sum that includes the third bid discussed above with respect to operation522).

One or more of operations552,554, and556may be performed as part (e.g., a precursor task, a subroutine, or a portion) of operation450, in which the presentation module340causes the web page (e.g., web page100) to display the winning ad (e.g., the coopetitive ad) in the ad slot within the web page. In operation552, the presentation module340causes the web page to display the coopetitive ad discussed above with respect to operation450in the top-ranked ad slot within the web page.

In example embodiments that include operation548, in which the results module330may determine that a competing ad wins the second-ranked ad slot, operation554may be performed as part of operation450. In operation554, the presentation module340causes the web page (e.g., web page100) to display the competing ad in the second-ranked ad slot.

In example embodiments where the ad auction is a search ad auction, operation556may be performed as part of operation450. In operation556, the presentation module340causes the web page (e.g., web page100) to display the coopetitive ad discussed above with respect to operation450with search results (e.g., returned by a search engine in response to a search query submitted by the user252).

According to various example embodiments, the ad auction machine210may detect a click on the coopetitive ad displayed in the web page (e.g., web page100) and respond by initiating or otherwise processing respective charges to the co-sponsors of the coopetitive ad (e.g., users232and242). Hence, one or more of operations560,570, and580may be performed after operation450, in which the presentation module340causes the web page to display the coopetitive ad in the ad slot.

In operation560, the presentation module340detects a click (e.g., performed by the user252via the device250) on the coopetitive ad displayed in the web page (e.g., web page100). In some example embodiments, a mouse over event may be used in place of a click.

In operation570, the payment module350charges the first advertiser (e.g., user232) a first amount that is equal to the first bid (e.g., placed by the first advertiser in operation420). According to some example embodiments, the payment module350initiates such a charge to the first advertiser or otherwise begins processing such a charge. Operation570may be performed in response to the click being detected in operation560.

In operation580, the payment module350charges the second advertiser (e.g., user242) a second amount that is equal to the second bid (e.g., placed by the second advertiser in operation430). According to certain example embodiments, the payment module350initiates this charge to the second advertiser or otherwise begins processing this charge. Operation580may be performed in response to the click being detected in operation560.

According to various example embodiments, one or more of the methodologies described herein may facilitate implementation, execution, and administration of a coopetitive auction, such as a coopetitive ad auction. Moreover, one or more of the methodologies described herein may facilitate an auction in which bids express complex preferences of bidders. Hence, one or more the methodologies described herein may allow multiple bidders to value a single object being auctioned (e.g., placement of the search ad within an ad slot), and a single bidder may be allowed to value multiple objects being auctioned (e.g., multiple ad slots on a web page).

When these effects are considered in aggregate, one or more of the methodologies described herein may obviate a need for certain efforts or resources that otherwise would be involved in facilitating coopetitive auctions. Efforts expended by administrators and bidders (e.g., advertisers) in implementing cooperative bidding relationships may be reduced by one or more of the methodologies described herein. Computing resources used by one or more machines, databases, or devices (e.g., within the network environment200) may similarly be reduced. Examples of such computing resources include processor cycles, network traffic, memory usage, data storage capacity, power consumption, and cooling capacity.

FIG. 6is a block diagram illustrating components of a machine600, according to some example embodiments, able to read instructions from a machine-readable medium (e.g., a machine-readable storage medium, a computer-readable storage medium, or any suitable combination thereof) and perform any one or more of the methodologies discussed herein, in whole or in part. Specifically,FIG. 6shows a diagrammatic representation of the machine600in the example form of a computer system and within which instructions624(e.g., software, a program, an application, an applet, an app, or other executable code) for causing the machine600to perform any one or more of the methodologies discussed herein may be executed, in whole or in part. In alternative embodiments, the machine600operates as a standalone device or may be connected (e.g., networked) to other machines. In a networked deployment, the machine600may operate in the capacity of a server machine or a client machine in a server-client network environment, or as a peer machine in a distributed (e.g., peer-to-peer) network environment. The machine600may be a server computer, a client computer, a personal computer (PC), a tablet computer, a laptop computer, a netbook, a set-top box (STB), a personal digital assistant (PDA), a cellular telephone, a smartphone, a web appliance, a network router, a network switch, a network bridge, or any machine capable of executing the instructions624, sequentially or otherwise, that specify actions to be taken by that machine. Further, while only a single machine is illustrated, the term “machine” shall also be taken to include a collection of machines that individually or jointly execute the instructions624to perform all or part of any one or more of the methodologies discussed herein.

The machine600includes a processor602(e.g., a central processing unit (CPU), a graphics processing unit (GPU), a digital signal processor (DSP), an application specific integrated circuit (ASIC), a radio-frequency integrated circuit (RFIC), or any suitable combination thereof), a main memory604, and a static memory606, which are configured to communicate with each other via a bus608. The machine600may further include a graphics display610(e.g., a plasma display panel (PDP), a light emitting diode (LED) display, a liquid crystal display (LCD), a projector, or a cathode ray tube (CRT)). The machine600may also include an alphanumeric input device612(e.g., a keyboard), a cursor control device614(e.g., a mouse, a touchpad, a trackball, a joystick, a motion sensor, or other pointing instrument), a storage unit616, a signal generation device618(e.g., a speaker), and a network interface device620.

The storage unit616includes a machine-readable medium622(e.g., a tangible and non-transitory machine-readable storage medium) on which are stored the instructions624embodying any one or more of the methodologies or functions described herein. The instructions624may also reside, completely or at least partially, within the main memory604, within the processor602(e.g., within the processor's cache memory), or both, during execution thereof by the machine600. Accordingly, the main memory604and the processor602may be considered as machine-readable media (e.g., tangible and non-transitory machine-readable media). The instructions624may be transmitted or received over a network626(e.g., network290) via the network interface device620.