Analytics Strategist

March 21, 2013

An Unusually Blunt Dialogue on Attribution – Part 2

Q: Continue on our yesterday’s conversation … I am still confused about the difference between conversion model and attribution model and attribution modeling.  Can you demonstrate using a simple example?

A: Sure.  Let’s look at a campaign with one vendor/channel on the media plan …

Q: Wait a minute, that will not be an attribution problem.  If there is only one channel/vendor,  does it matter what attribution model you use?

A: It does. Do we give the vendor 100% of the credit? A fraction less than 100% of the credit?

Q: Why not 100%?  I think all commonly used attribution models will use 100% …

A: You may want to think twice, because some users may convert on their own.  Let’s assume the vendor reach 10,000 users and 100 of them converted. Let’s also assume that, through analysis and modeling works (such as using a control group), you conclude that 80 out of the 100 converters will convert on their own.  How many converters does the vendor actually (incrementally) impacted?

Q: 20.

A: If you assign 100% credit to the vendor, the vendor will get all 100 converters’ credits.  Since the actual impacted conversion is 20, a fraction of credit should be used; in this case it is 20% instead 100%.  That’s attribution modeling, in its simplest form.

Q: Really? Can you recap the process and highlight the attribution modeling part of it?

A:  Sure. In this simplest example, the conversion model provides us two numbers(scores):

1)      The probability of conversion given the converter exposed to the campaign, call it P(c|camp) – in this case it is 100/10000 = 1% , and

2)      The probability of conversion given the converter not exposure to the campaign, call it P(c|no-camp) – in this case it is 80/10000 = 0.8%

The attribution modeling says that, only a fraction of the credit, (P(c|camp)-P(c|no-camp))/P(c|camp) == 0.2 or 20%, should be credited out.

Notice that this fraction for attribution is not 100%. It is not P(c|camp) which is 1%; and it is not P(c|camp) – P(c|no-camp) which is 0.2%.

Q: This is an interesting formula.  I do not recall seeing it anywhere before.  Does this formula come from the conversion model?

A: Not really.  The conversion model only providing the best possible estimate for P(c|camp) and P(c|no-camp), that’s all.  It will not provide the attribution fraction formula.

Q: Where does this formula come from then?

A: It comes from the following reasoning:  vendor(s) should get paid for what they actually (incrementally) impacted, not all the conversions they touched.

Q: So the principle of this “attribution modeling” is not data-driven but pure reason.  How much should I trust this reasoning?  Can this be the ground to build industry consensus?

A: What else can we build consensus on?

Q: Ok, I see how it works in this simple case, and I see the principle of it.  Can we generalize this “incremental impact” principle to multi-channel cases?

A: What do you have in mind?

Q: Let me try to work out the formula myself.  Suppose we have two channels, call them A, and B.  We start with conversion model(s), as usual.  From the conversion model(s), we find out our best estimates for P(c|A,B), P(c|nA,nB), P(c|nA,B), P(c|A,nB).  Now I understand why it does not matter if we use logistic regression, or probit model or neural network to build our conversion model – all that matter is to make sure we get the best estimates for the above scores J

A: Agree.  By the way, I think I understand the symbols you used, such as c, A, nA, nB etc. – let me know if you think I may guess it wrong 🙂

Q: This is interesting, I think I can get the formula now.  Take channel A first, and let’s call the fractional credit A should get as C_a;  we can calculate it with this formula:  C_a= (P(c|A,B)–P(c|nA,B)) / P(c|A,B), right?

A: If you do that, C_a + C_b maybe over 100%

Q: What’s wrong, then?

A: We need to first figure out what fraction of attribution available to be credited out to A and B, just as in the simplest case discussed before. It should be (P(c|A,B) – P(c|nA,nB)) / P(c|A,B).

Q: I see.  How should we divide the credit to A and B next?

A: That is a question we have not discussed yet.  In the simplest case, with one vendor, this is a trivial question. With more than one vendor(s)/channel(s), we need some new principle?

Q: I have an idea:  we can re-adjust the fractions on top of what we did before, like this:  C’_a = C_a / (C_a + C_b) and C’_b = C_b/(C_a + C_b);  and finally, we use C’_a and C’_b to partition the above fraction of credit.  Will that work?

(note: the following example has error in it, as pointed out by Vadim in his comment below)

A: Unfortunately, no.  Take the following example:

suppose A add no incremental value, except when B is present:  P(c|A,nB) == P(c|nA,nB) and P(c|A,B) > P(c|nA,B)

also, B does not add anything when A is present:  P(c|A,B) = P(c|A,nB)

The calculation will lead to:  C_b == 0 and C_a > 0.  Therefore, A get all the available credit and B get nothing.

Do you see a problem?

Q: Yes.  B will feel unfair, because without B, A will contribute nothing.  However, A get all the credit and B get nothing.

A: This is just a case with two channels and two players.  Imaging if we get 10 channels/players, what a complicated bargaining game this is going to be!

Q: Compare with this, the conversion model part is actually easy; well, not easy but more like a non-issue.  We can build conversion models to generate all these conditional probability scores.  However, we still stuck here and can’t figuring out a fair division of credit.
A: This is attribution modeling:  the process or formula that will translate the output of conversion models into attribution model (or fractional credits). We need to figure this thing out.

Q: What is it, really?

A: We are essentially looking for a rule or a formula to divide the total credit that we can all agree as fair.  Is that right?

Q: Right, but we have to be specific about what do we mean by “fair”.

A:  That’s right.  So, let’s discuss a minimal set of “fair” principles that we can all agree upon.  There are three of them, as I see it:

Efficiency: we are distributing all available credit, not leaving any on the table

Symmetry: if two channels are functionally identical, they should get the same credit

Dummy Channel: if a channel contribute nothing in all cases, it should get no credit

What do you think?

Q: I think we can agree with these principles.  How can they help?

A: Well, someone has proved that there is one and only one formula that satisfy this minimal set of principles. I think this is our attribution formula!

Q: Really? I do not believe this.  Who proved this?  Where can I read more of it?

A: In 1953, Lloyd Shapley published the proof in his PhD dissertation and the resulting formula became Shapley Value. The field of knowledge is called Cooperative Game Theory.  You can Google it and you will find tons of good references. Of course, Shapley did not call it “attribution problem” and he talked about players instead of channels. The collection of principles are more than three.  However, Transferable Utility and Additive principle are automatically satisfied when applied to credit partitioning problem.

Q: Now, how do you apply this attribution rule differently for different converters?

A: You do not.  The difference among converters are reflected in the scores generated from the conversion models, not in the above attribution formula – or Shapley Value.

Q: Ok, if that is the case, everyone in the industry will be using the same Attribution Formula, or Shapley Value.  How do we then creatively differentiate from each other?  How should different type of campaigns be treated uniquely?  How do the effect of channels on different types of conversion be reflected in attributed credits?

A: Well, all these will be reflected in how the conversion models are built and how the parameters of the conversion models are estimated, and finally the scores that come out of the conversion models.  You will innovate on statistical model development techniques. Attribution formula is, fortunately, not where you are going to innovate.

Q: This is quite shocking to me. I can’t imagine how the industry will react …

A: How did industry deal with Marketing Mix Modeling?  We accept the fact that those are simply regression models in essence, and start selling expertise on being able to do it thoroughly and do it right.  We do not have to create our own attribution model to be able to compete with each other.

Advertisements

November 21, 2011

Ad exchange as matchmaker

Filed under: misc — Tags: , , , , — Huayin Wang @ 9:52 pm

Looking at ad exchange from the matching game perspective can be interesting.  My early post tried to draw some insights from game theory into ad exchange design and practice.

Ad exchange is a platform of matching advertiser’s ads to publisher’s slots for each audience-impressions.  The massive scale of its operation, the technological challenge and sophistication are unprecedented; and yet the basic matching mechanism is under-designed in comparison to traditional matchmaking. There are so many things that publisher care about which ad will be shown on their sites, not just what’s is the highest bid price; yet, the within current ad exchange design, there is no opportunity for publishers to express their preferences fully.

If ad exchange were a matchmaker, what it would be like?  Imaging publisher as bride and advertisers as potential grooms – our ad-exchange-matchmaker goes to a bride and say,

M:  Let’s put it out there and see who will be the richest man coming here for you

B:  But I am scared of marrying one I do not know”

M:  Well, you can give me a black list and tell me what you do or do not like as filters

B:  Can I pick it myself?

M:  No, I will pick one for you –  based on wealth

Now you get the idea of the frustrations of our publisher/bride.  There need to be a process for publishers to perform data-driven ads evaluation based on their objective and value, not just bid price.  About publisher concerns of ad exchange and RTB,  Brian O’Kelley discussed here on ClickZ.  A better designed matching mechanism should handle publisher’s preference properly, which may ease some of the publishers’ concerns (channel conflict, data leak and brand safety) if not solving them.

November 16, 2011

Ad exchange, matching game and mechanism design

Over the years, I have learned some interesting things in this new ad:tech industry, particularly around the Ad Exchange and RTB ad auction market model.  I want to share some of my thoughts here and hope you find them interesting to read.

Ad Exchange is not like a financial exchange

The “exchange” in the name is suggestive of a financial stock exchange market, and interesting observations can be made based on this analogy.  However, there are some fundamental differences such as the lack of liquidity in ad impression and information asymmetry.  Jerry Neumann has blogged about this topic profusely;  it is still a topic of great interest today, as seen in a recent article by Edward Montes.

In fact, the differences are easy to understand. The harder part is, like Jerry asked,  If the ad exchange aren’t exchanges, what are they?  or I should add, what should they be like?

Publisher’s preference is the missing piece

The analogy with financial exchange (stock and future) is not a good analogy partly because of its inability to fully model advertiser preference. Not all impressions are of the same value to an advertiser and not all advertisers give the same value to an impression. The commodity auction model as embedded in ad exchange does better, because it allows advertisers to bid based on any form of evaluation – a chance for advertiser to fully express its preference over audience, contextual content and publishers’ brand.

Still, there is a problem for the current auction model: after collecting all the bids from advertisers, it takes the highest bidder to be the winner, as if price is the only thing publishers care about.  In reality, not all bids with the same price are of the same value to a publisher.  Publishers care about brand safety and contextual relevancy as well; in fact, the quality of user experience may mean more to publishers than advertisers!  In sum, publishers care about the quality of the ads above and beyond the bid price.  Unfortunately, the current ad exchanges lack the proper mechanism allowing publishers to articulate their full preferences.  This results in lost of market efficiency and lost of opportunities to remove transaction frictions.  This is a design flaw.

Display marketplace is still far from perfectly efficient and this design flaw does not help.  The recent developments of Private Marketplace are piecemeal attempts to overcome this design issue.  Some market movements in late merge and acquisition attempts can be understood from this angle.

Where can we look for design idea on how to handle this issue?  – paid search and game theory!

The quality score framework from paid search

In many ways, paid search is just like ad exchange, with Google plays one of a few “publisher” roles.   In both markets, advertisers are competing for ad-view through auction bidding;  if we equate audience in display to keywords in search, then the bidding processes is quite the same:  search advertisers do extensive keyword research, look at past performance along side of other planning parameters such as time of the day etc. to optimize their bids;  similarly display advertisers look at the audience attributes, the site and page contents, past performance and planning parameters as they perform bid optimization.

The bidding processes in both markets are similar;  the differences lie in the post-bidding ad evaluation.

After all bids are collected, ad exchange today simply select the highest bidder.  In case of paid search, bids are evaluated on price, ad relevancy and many other attributes.  Google has mastered the evaluation process with its Quality Score framework.  This difference in having a Quality Score framework vs not is not a small thing.  As anyone familiar with the history of paid search know, the quality score framework played a pivotal role in shaping the search industry when Google introduced it around the turn of the century.  The post-bidding ad evaluation for display may just be a critical piece of technology and have potentially significant impact on the efficiency and the health of the display market.

The need for a non-trivial post-bidding ad evaluation calls for an extra decision process (and algorithm) to be added, either at ad exchange or at publisher’s site, or both.  In this new model and with this extra component, ad exchange will send the full list of bidding to the publisher instead of picking a winner based on price alone.  It is then up to the publisher to decide which ad will be shown.  With millions of publishers, large and small, this seemingly small change may be a trigger for more inside this industry where technology is already orders of magnitude more complex than paid search.

The matching game analogy

With full preferences being taking into account for both advertisers and publishers, ad exchange looks less like a commodity marketplace and more like the matching game.  It will be interesting to look at market efficiency from the perspective of mechanism design in game theory, which is another way of saying operational market process.

Matching advertisers with publishers under a continuous series of Vickrey auctions is our setup for the discussion – the best model I can think of that mimic the matching game setup;  it shouldn’t be too surprising to anyone that matching game is an interesting analogy to ad exchange.  As a game theory abstraction of many practical cases, matching game includes college admission and marriage market.  Let’s take the marriage market as an example.

Using a simplistic description, a marriage market involves a set of Men and a set of Women.  Each man has a preference vector over the set of women (a ranking of women);  similarly each woman has a preference vector over the set of men (a ranking of men).  A matching is an assignment of men to women such that each man is assigned to at most one woman and vice versa.  A matching is unstable if there exist a man-woman pair not currently matched to each other but both prefer match to each other than their current match – the pair as such is called a blocking pair.  When there is no blocking pair exist, a match will be called a stable match.

Clearly, stability of a match is a good quality: a stable match is not vulnerable to any voluntary pairwise rematch (translating into ad exchange language, a stable match is one such that no pair of advertiser – publisher currently not matched to each other have incentive to switch and form a new match).  A matching is male-optimal if no two males have incentive to switch partners. Female-Optimal is defined similarly.  A stable matching that is both male-optimal and female optimal looks like an perfect efficient market; we hope to find a mechanism that lead to the unique stable matching as such – something we can then mimic to implement for a future ad exchange model.

Unfortunately, there is no unique stable matching for matching game in general (in this case, having too many good things may not be a good thing).  There is also no unique optimal matching that is optimal from both men and women’s perspective.  We learned that Male Proposals Deferred Acceptance Algorithm, sort of like the current auction process in ad exchange in which advertisers played the male roles, produce Male-Optimal stable matching.  If we switch the role of men and women, a similar algorithm exists that produces Female-Optimal matching.  The two algorithms/mechanisms lead to two distinctly different results.  You can read more about algorithmic game theorycomputational game theory, specifically on matching game and mechanism design if interested.

So, why are we looking into this and what we’ve learned from it?  Below is my translation, or transliteration to be more appropriate, from game theory speak to the ad:tech domain.

We all like to believe that there is an efficient market design for everything, including the exchange marketplace for ads. Our believe is justified for all commodity marketplace by the general equilibrium theory.  Unfortunately, there is no equivalence of a “general equilibrium” or universal optimal stable match for a marriage market, which implies that there is no universal optimal advertiser-publisher matching in ad exchange.  If this is the case, the search for an optimal market mechanism for ad exchange will be a mission impossible.

However, there exist one-sided optimal condition, advertiser-optimal and/or publisher-optimal matching.  It is also easy to find the corresponding mechanisms that lead to those one-sided optimal stable matching.  The auction market as currently implemented in ad exchanges, with the addition of post-bidding evaluation process, is similar to the mechanism leading to advertiser-optimal matching.

The future seems open for all kinds of good mechanism design.  Still, I believe that there is a “naturalness” in the current style auction market.  It is quite natural for the auction process to start from the publisher side, by putting the ad impression on auction, because it is all start with the audience requesting a webpage – a request send to a publisher. It is not easy to imagine how advertiser can set up a “reverse auction” starting from the demand side, within a RTB context. We can never rule out the possibility, and it may work potentially for trading the ad future.

Conclusion:

I am reluctant to draw any conclusions – these are all food for thought and discussion.  I’d love to hear your comments!

Create a free website or blog at WordPress.com.