3e:null 3f:["$","title",null,{"children":"Proposed Bid Shading Strategy for DSP | Nicolas Grislain | Observable"}] 45:T571,md` # Proposed Bid Shading Strategy for *DSP* ## Summary and suggested next steps The main conclusions of this work is that optimal, *profit* maximizing, shading can be performed by applying a discount factor ${tex`s \in [0,1]`} to the bid who would have been chosen by the current system designed for SPA and that ${tex`s`} can be found by local optimisation of the *surplus* of each auction. A first model optimizing advertiser expected profit (${tex`\textit{advertiser value} - \textit{spend}`}) on a _per user_ basis has been developped and tested on simulated data. The plan to develop this approach is the following: 1. Train our bid shading model on production logs. 2. And test deploy on *DSP* to evaluate the impact on advertiser's *profit*. ${tex`1.`} is already started and should be finished quickly. ${tex`2.`} should be the main goal for the quarter. ## Introduction In this document, we will describe a simple but quite general model of *first price auction* (FPA) and show how to derive an optimal bidding strategy under budget constraint. We also show how our strategy can be expressed in terms of the standard *second price auction* (SPA) model. From this theoretical work we will describe how our strategy could be implemented within *DSP*, our current buying system, which assumes SPA. We show, in particular, how it would play with the pacing mechanism in place. `46:T4e1,md`## Definitions The **impression value** is the reward that an advertiser gets from a won auction. In a *CPC* campaign it will be the ${tex`CPC`}. The **expected impression value** also called **value** ${tex`=v_t`} will then be the expected reward that an advertiser gets from an auction ${tex`t`}. In a *CPC* campaign it will be ${tex`v_t = CPC\cdot pCTR_t`} In a budget constrained campaign, the **paced value** is the *value* discounted by the *pacing factor*. It can be seen as the *value* minus the opportunity cost of winning (winning now removes an opportunity of winning later in a budget constrained world). This notion is dependent on a *pacing factor* (see below). The **profit** is the sum of **impression value** minus **spend**. In this document a bidding strategy is always *optimal* in the sense it maximizes the *expected profit* of the advertiser. **Profit** will also be the way to measure the performance of a strategy. **Surplus** is the difference between what an advertiser is ready to bid and what he actually pays if he wins. In the budget constrained case, the surplus depends on the *pacing factor*. Note that the **surplus** may be ${tex`0`} while the profit is still positive in a budget constrained FPA world. `47:T712,md` ### In a Second Price Auction (SPA) Let's say there are ${tex`T`} opportunities over the period, we are trying to maximise: ${tex.block`\Pi_{SPA} = \sum_{t=0}^T\int_0^{a_t} \left(v_t-b\right)\cdot B_t(b)db`} with ${tex.block`\sum_{t=0}^T\int_0^{a_t} b\cdot B_t(b)db \leq K`} Where: - ${tex`\Pi_{SPA}`} is advertiser's *expected profit* over the campaign - ${tex`a_t`} is the bid chosen by the advertiser at auction ${tex`t`} - ${tex`B_t`} is the CDF of the highest other bid at auction ${tex`t`}, so ${tex`b_t\sim B(x_t)`}. It can be stated as the maximization of a _Lagrangian expression_: ${tex.block`\max_a \mathcal{L}_{SPA} = \max_a \sum_{t=0}^T\int_0^{a_t} \left(v_t-b\right)\cdot B_t(b)db - \lambda \left(\sum_{t=0}^T\int_0^{a_t} b\cdot B_t(b)db - K\right)`} The solution ${tex`a_{SPA}`} verifies: ${tex.block`\left(v_t-a_{t,SPA}\right)\cdot B_t(a_{t,SPA}) - \lambda a_{t,SPA}\cdot B_t(a_{t,SPA})=0`} with ${tex`\lambda \geq 0`}. When ${tex`B`} is sufficiently regular, the condition writes: ${tex.block`a_{t,SPA} = \frac{v_t}{1+\lambda} = a\cdot v_t`} The optimal bidding strategy is to bid proportionaly to ${tex`v_t`} with a _pacing factor_ ${tex`a \in [0,1]`}. In practice determining such a *pacing factor* requires a good forecast of what will happen over the course of the campaign (or budget constrained period). In *DSP* the pacing factor is set by a module named _controller_ using a simple forecast and is adjusted continuously using a feedback loop (note that we developped a RNN based approach described in our KDD paper [Recurrent Neural Networks for Stochastic Control in Real-Time Bidding](https://www.kdd.org/kdd2019/accepted-papers)). In this work we will assume the existence of a controller able to find such a _pacing factor_ and focus on _bid-shading_ as defined bellow. `48:T8ce,md` ### In a First Price Auction (FPA) We are trying to maximise: ${tex.block`\Pi_{FPA} = \sum_{t=0}^T\int_0^{a_t} \left(v_t-a_t\right)\cdot B_t(b)db`} with ${tex.block`\sum_{t=0}^T\int_0^{a_t} a_t\cdot B_t(b)db \leq K`} Where: - ${tex`\Pi_{FPA}`} is advertiser's profit over the campaign in the FPA case - ${tex`a_t`} is the bid chosen by the advertiser at auction ${tex`t`} - ${tex`B_t`} is the CDF of the highest other bid at auction ${tex`t`}, so ${tex`b_t\sim B(x_t)`}. It can be stated as the maximization of a _Lagrangian expression_: ${tex.block`\max_a \mathcal{L}_{FPA} = \max_a \sum_{t=0}^T\int_0^{a_t} \left(v_t-a_t\right)\cdot B_t(b)db - \lambda \left(\sum_{t=0}^T\int_0^{a_t} a_t\cdot B_t(b)db - K\right)`} The solution ${tex`a_{FPA}`} verifies: ${tex.block`\left(v_t-a_{t,FPA}\right)\cdot B_t(a_{t,FPA}) - \int_0^{a_{t,FPA}} B_t(b)db - \lambda a_{t,FPA}\cdot B_t(a_{t,FPA}) - \lambda \int_0^{a_{t,FPA}} B_t(b)db=0`} ${tex.block`a_{t,FPA} + \frac{\mathcal{B}_t(a_{t,FPA})}{B_t(a_{t,FPA})} = \frac{v_t}{1+\lambda} = a\cdot v_t`} We assume there is a function ${tex`S`} such that: ${tex.block`a_{t,FPA} = S\left(a\cdot v_t\right) \leq a\cdot v_t`} #### Non-budget constrained equivalence The FPA problem can be stated as: ${tex.block`\max_a \mathcal{L}_{FPA} = \max_a \sum_{t=0}^T\int_0^{a_t} \left(v_t-a_t\right)\cdot B_t(b)db - \lambda \left(\sum_{t=0}^T\int_0^{a_t} a_t\cdot B_t(b)db - K\right)`} Which can be rewritten: ${tex.block`\max_a \mathcal{L}_{FPA} = \max_a \sum_{t=0}^T\int_0^{a_t} \left(v_t-\left(1+\lambda\right)a_t\right)\cdot B_t(b)db + \lambda\cdot K`} And is equivalent to: ${tex.block`\max_a \mathcal{L}_{FPA} \Leftrightarrow \max_a \sum_{t=0}^T\int_0^{a_t} \left(\frac{v_t}{1+\lambda}-a_t\right)\cdot B_t(b)db`} ${tex.block` \Leftrightarrow \max_a \sum_{t=0}^T\int_0^{a_t} \left(a\cdot v_t-a_t\right)\cdot B_t(b)db`} This equivalence suggests the following theorem: #### Theorem of optimality of local surplus optimization Optimal (*profit* maximizing) bid shading can be achieved by optimizing *surplus* (${tex`\textit{paced value} - \textit{spend}`}) locally (i.e. auction by auction), the profit of the advertiser given an estimated value ${tex`v_t`} discounted by some *pacing factor* ${tex`a \in [0,1]`}. `49:Ta63,FPAChart = { let [X, m, r, s, av] = [FPAChartParameters.x, FPAChartParameters.m, FPAChartParameters.r, FPAChartParameters.s, FPAChartParameters.av]; let [mu, sigma] = [Math.log(m)+r*X, s]; let aBbX = aBb(mu, sigma) let shadingX = shading(mu, sigma) //let approxShadingX = approxShading(mu, sigma) let maxBid = settings.maxBid; let shadedBid = d3.range(0,maxBid,0.05).map(a => ({ x: aBbX(a), y: a })); //let approxShadedBid = d3.range(0,maxBid,0.5).map(a => ({ // x: a, // y: approxShadingX(a) //})); // Main parameters let epsilon = settings.epsilon; let height = settings.height; let margin = settings.margin; let x = d3.scaleLinear() .domain(d3.extent(shadedBid, d => d.y)).nice() .range([margin.left, width - margin.right]); let y = d3.scaleLinear() .domain(d3.extent(shadedBid, d => 0.8*d.y)).nice() .range([height - margin.bottom, margin.top]); // Build the graph let xAxis = g => g .attr("transform", `translate(0,${height - margin.bottom})`) .call(d3.axisBottom(x).tickSizeOuter(0)) .call(g => g.select(".tick:last-of-type text").clone() .attr("y", -12) .attr("text-anchor", "end") .text("Bid")); let yAxis = g => g .attr("transform", `translate(${margin.left},0)`) .call(d3.axisLeft(y)) .call(g => g.select(".tick:last-of-type text").clone() .attr("x", 8) .attr("text-anchor", "start") .text("Shaded bid")); let svg = d3.select(DOM.svg(width, height)); svg.append("g") .call(xAxis); svg.append("g") .call(yAxis); svg.append("path") .datum(shadedBid) .attr("fill", "none") .attr("stroke", settings.bidColor) .attr("stroke-width", 2) .attr("d", d3.line().x(d => x(d.x)).y(d => y(d.y))); /*svg.append("path") .datum(approxShadedBid) .attr("fill", "none") .attr("stroke", settings.colors[2]) .attr("stroke-width", 2) .attr("d", line);*/ svg.append("path") .datum(shadedBid) .attr("fill", "none") .attr("stroke", settings.bidColor) .attr("stroke-width", 1) .attr("stroke-dasharray", [5,5]) .attr("d", d3.line().x(d => x(d.y)).y(d => y(d.y))); svg.append("path") .datum([{x:av, y:0}, {x:av, y:maxBid}]) .attr("fill", "none") .attr("stroke", settings.valueColor) .attr("stroke-width", 2) .attr("d", d3.line().x(d => x(d.x)).y(d => y(d.y))); svg.append("circle") .datum({x:av, y:shadingX(av)}) .attr("fill", settings.valueColor) .attr('cx', d => x(d.x) ) .attr('cy', d => y(d.y) ) .attr('r', 8); return svg.node(); }4a:T777,simulationChart = { // Main parameters let height = settings.height; let margin = settings.margin; let x = d3.scaleLinear() .domain([0,auctions.length]).nice() .range([margin.left, width - margin.right]); let y = d3.scaleLinear() .domain([0, d3.max(auctions.map(a => a.v))]).nice() .range([height - margin.bottom, margin.top]); // Build the graph let xAxis = g => g .attr("transform", `translate(0,${height - margin.bottom})`) .call(d3.axisBottom(x).tickSizeOuter(0)) let yAxis = g => g .attr("transform", `translate(${margin.left},0)`) .call(d3.axisLeft(y)) let svg = d3.select(DOM.svg(width, height)); svg.append("g") .attr("fill", settings.valueColor) .selectAll("rect") .data(auctions) .join("rect") .attr("x", (d,i) => x(i)) .attr("width", 1) .attr("y", d => y(d.v)) .attr("height", d => y(0) - y(d.v)); svg.append("g") .attr("fill", settings.bidColor) .selectAll("rect") .data(auctions) .join("rect") .attr("x", (d,i) => x(i)) .attr("width", 1) .attr("y", d => y(d.b)) .attr("height", d => y(0) - y(d.b)); svg.append("g") .attr("fill", settings.shadedBidColor) .selectAll("circle") .data(shadedBids) .join("circle") .attr('cx', (d,i) => x(i)+0.5) .attr('cy', d => y(d)) .attr('r', 2); svg.append("g") .attr("fill", settings.uniformlyShadedBidColor) .selectAll("circle") .data(uniformlyShadedBids) .join("circle") .attr('cx', (d,i) => x(i)+0.5) .attr('cy', d => y(d)) .attr('r', 2); svg.append("g") .attr("fill", settings.valueColor) .selectAll("circle") .data(bids) .join("circle") .attr('cx', (d,i) => x(i)+0.5) .attr('cy', d => y(d)) .attr('r', 2); svg.append("g").call(xAxis); svg.append("g").call(yAxis); return svg.node(); }4b:T41c,viewof auctionsParameters = { let parameters = html``; parameters.oninput = () => { parameters.value = { mu: parameters.mu.valueAsNumber, sigma: parameters.sigma.valueAsNumber, m: parameters.m.valueAsNumber, r: parameters.r.valueAsNumber, s: parameters.s.valueAsNumber, n: parameters.n.valueAsNumber, budget: parameters.budget.valueAsNumber }; }; parameters.oninput(); return parameters; }4c:T6d3,md` ### Average profit and spend per auction in **$CPM**. Dotted lines are spend and bold lines profit. For: - Unshaded ${d3.select(DOM.svg(100, 10)) .call(svg => svg.append("line") .attr("x1",10).attr("y1", 5) .attr("x2",40).attr("y2", 5) .attr("fill", "none") .attr("stroke", settings.valueColor) .attr("stroke-width", 2)) .call(svg => svg.append("line") .attr("x1",60).attr("y1", 5) .attr("x2",100).attr("y2", 5) .attr("fill", "none") .attr("stroke", settings.valueColor) .attr("stroke-width", 1) .attr("stroke-dasharray", [5,5])) .node()} - Uniformely shaded ${d3.select(DOM.svg(100, 10)) .call(svg => svg.append("line") .attr("x1",10).attr("y1", 5) .attr("x2",40).attr("y2", 5) .attr("fill", "none") .attr("stroke", settings.uniformlyShadedBidColor) .attr("stroke-width", 2)) .call(svg => svg.append("line") .attr("x1",60).attr("y1", 5) .attr("x2",100).attr("y2", 5) .attr("fill", "none") .attr("stroke", settings.uniformlyShadedBidColor) .attr("stroke-width", 1) .attr("stroke-dasharray", [5,5])) .node()} - Shaded per auction ${d3.select(DOM.svg(100, 10)) .call(svg => svg.append("line") .attr("x1",10).attr("y1", 5) .attr("x2",40).attr("y2", 5) .attr("fill", "none") .attr("stroke", settings.shadedBidColor) .attr("stroke-width", 2)) .call(svg => svg.append("line") .attr("x1",60).attr("y1", 5) .attr("x2",100).attr("y2", 5) .attr("fill", "none") .attr("stroke", settings.shadedBidColor) .attr("stroke-width", 1) .attr("stroke-dasharray", [5,5])) .node()} `4d:T9e9,profitChart = { // Main parameters let height = settings.height; let margin = settings.margin; let x = d3.scaleLinear() .domain([0,auctions.length]).nice() .range([margin.left, width - margin.right]); let y = d3.scaleLinear() .domain([0, 1.2*1000*Math.max(shadedCampaign.profit[shadedCampaign.profit.length-1]/shadedCampaign.profit.length, campaign.spend[campaign.spend.length-1]/campaign.spend.length)]).nice() .range([height - margin.bottom, margin.top]); // Build the graph let xAxis = g => g .attr("transform", `translate(0,${height - margin.bottom})`) .call(d3.axisBottom(x).tickSizeOuter(0)) let yAxis = g => g .attr("transform", `translate(${margin.left},0)`) .call(d3.axisLeft(y)) let svg = d3.select(DOM.svg(width, height)); svg.append("path") .datum(campaign.spend) .attr("fill", "none") .attr("stroke", settings.valueColor) .attr("stroke-width", 1) .attr("stroke-dasharray", [5,5]) .attr("d", d3.line().x((d,i) => x(i)).y((d,i) => y(1000*d/(settings.epsilon+i)))); svg.append("path") .datum(uniformlyShadedCampaign.spend) .attr("fill", "none") .attr("stroke", settings.uniformlyShadedBidColor) .attr("stroke-width", 1) .attr("stroke-dasharray", [5,5]) .attr("d", d3.line().x((d,i) => x(i)).y((d,i) => y(1000*d/(settings.epsilon+i)))); svg.append("path") .datum(shadedCampaign.spend) .attr("fill", "none") .attr("stroke", settings.shadedBidColor) .attr("stroke-width", 1) .attr("stroke-dasharray", [5,5]) .attr("d", d3.line().x((d,i) => x(i)).y((d,i) => y(1000*d/(settings.epsilon+i)))); svg.append("path") .datum(campaign.profit) .attr("fill", "none") .attr("stroke", settings.valueColor) .attr("stroke-width", 2) .attr("d", d3.line().x((d,i) => x(i)).y((d,i) => y(1000*d/(settings.epsilon+i)))); svg.append("path") .datum(uniformlyShadedCampaign.profit) .attr("fill", "none") .attr("stroke", settings.uniformlyShadedBidColor) .attr("stroke-width", 2) .attr("d", d3.line().x((d,i) => x(i)).y((d,i) => y(1000*d/(settings.epsilon+i)))); svg.append("path") .datum(shadedCampaign.profit) .attr("fill", "none") .attr("stroke", settings.shadedBidColor) .attr("stroke-width", 2) .attr("d", d3.line().x((d,i) => x(i)).y((d,i) => y(1000*d/(settings.epsilon+i)))); svg.append("g").call(xAxis); svg.append("g").call(yAxis); return svg.node(); }4e:T6fe,bidsChart = { // Main parameters let height = settings.height; let margin = settings.margin; let x = d3.scaleLinear() .domain([0,100]).nice() .range([margin.left, width - margin.right]); // Build bins let valueBins = d3.histogram() .domain(x.domain()) .thresholds(x.ticks(50)) (auctions.map(a => a.v)); let bidBins = d3.histogram() .domain(x.domain()) .thresholds(x.ticks(50)) (auctions.map(a => a.b)); let y = d3.scaleLinear() .domain([0, d3.max(valueBins, d => d.length)]).nice() .range([height - margin.bottom, margin.top]); // Build the graph let xAxis = g => g .attr("transform", `translate(0,${height - margin.bottom})`) .call(d3.axisBottom(x).tickSizeOuter(0)) .call(g => g.append("text") .attr("x", width - margin.right).text(valueBins.x)); let yAxis = g => g .attr("transform", `translate(${margin.left},0)`) .call(d3.axisLeft(y)) .call(g => g.append("text") .text(valueBins.y)); let svg = d3.select(DOM.svg(width, height)); let valueBar = svg.append("g") .attr("fill", settings.valueColor) .selectAll("rect") .data(valueBins) .join("rect") .attr("x", d => x(d.x0) + (x(d.x1) - x(d.x0))/2 + 1) .attr("width", d => Math.max(0, (x(d.x1) - x(d.x0))/2 - 1)) .attr("y", d => y(d.length)) .attr("height", d => y(0) - y(d.length)); let bidBar = svg.append("g") .attr("fill", settings.bidColor) .selectAll("rect") .data(bidBins) .join("rect") .attr("x", d => x(d.x0) + 1) .attr("width", d => Math.max(0, (x(d.x1) - x(d.x0))/2 - 1)) .attr("y", d => y(d.length)) .attr("height", d => y(0) - y(d.length)); svg.append("g").call(xAxis); svg.append("g").call(yAxis); return svg.node(); }4f:[] 43:{"id":"9d739b2bc5b22bd8","slug":"proposed-bid-shading-strategy-for-dsp","title":"Proposed Bid Shading Strategy for DSP","thumbnail":"6b475392047d6eafeace2a689e75dd1e8f4489d1b858ac5b21bde86fee20c2fc","access_level":"public","create_time":"$D2019-06-20T18:16:28.427Z","update_time":"$D2019-07-08T16:12:35.591Z","view_time":null,"first_public_time":"$D2019-12-18T08:22:04.403Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"abf6c0508f02b218","login":"ngrislain","name":"Nicolas Grislain","avatar_url":"https://avatars-next.observableusercontent.com/d9d690de51e271b26a32af3f96c642029a5a0636a610083e0ffe1049ef087a89","tier":"starter_2024","bio":""},"version":1586,"publish_version":1586,"role":null,"authored":false,"authors":[{"type":"individual","id":"e67862f7a487e446","login":"ngrislain","name":"Nicolas Grislain","avatar_url":"https://avatars-next.observableusercontent.com/d9d690de51e271b26a32af3f96c642029a5a0636a610083e0ffe1049ef087a89","tier":null,"bio":""}],"members":[{"type":"individual","id":"e67862f7a487e446","login":"ngrislain","name":"Nicolas Grislain","avatar_url":"https://avatars-next.observableusercontent.com/d9d690de51e271b26a32af3f96c642029a5a0636a610083e0ffe1049ef087a89","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Proposed Bid Shading Strategy for DSP","cells":[{"id":631,"value":"$45","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1291,"value":"$46","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"md`\n## Auction model\n\nWe are a bidder (DSP) trying to deliver a CPC campaign optimally.\nWe receive a bid request and gather some *feature variables* ${tex`x`} before each auction.\n${tex`x`} is all we know about the market.\n\nGiven ${tex`x`}, we can anticipate the expected value of the current impression:\n\n${tex.block`v(x) = CPC\\cdot pCTR`}\n\nWe can also know some conditional distribution of the highest other bid:\n\n${tex.block`b \\sim B(x)`}\n\nWe will denote ${tex`B(b|x)`} and ${tex`\\mathcal{B}(b|x)`} or (${tex`B(b)`} and ${tex`\\mathcal{B}(b)`}, when not ambiguous) the *PDF* and *CDF* of ${tex`b`}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":656,"value":"md`\n## Campaign model\nWe are trying to maximize advertiser's profit for a CPC campaign over some period of time and given a budget ${tex`K`}.\n\nLet's first derive optimiality conditions in the standard SPA case.\nThen it'll be interesting to express similar optimality conditions in the desired FPA case.\n\nWe'll then define what *bid shading* means and how it can be implemented in a system designed for an SPA world. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":192,"value":"$47","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":425,"value":"$48","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":826,"value":"md`\n## Simulations\n\n### Data generation\n\nFor the simulations supporting this document, we will make the following simple assumptions regarding data generation.\n\nThe private value of a given impression ${tex`v = CPC\\cdot pCTR`} is:\n${tex.block`v = \\mu \\cdot e^{\\sigma\\cdot \\epsilon}`}\nwith: ${tex`\\epsilon \\sim \\mathcal{N}\\left(0, 1\\right)`}\n\nThe highest other bid will be:\n${tex.block`b = m \\cdot e^{r\\cdot x + s\\cdot e}`}\nwith ${tex`x \\sim \\mathcal{N}\\left(0, 1\\right)`}\nobserved market factor and ${tex`e \\sim \\mathcal{N}\\left(0, 1\\right)`}.\n\nNote that, for the sake of simplicity, ${tex`x`} is not affecting ${tex`v`}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":526,"value":"md`\n### Simulation of the bid shading function in the log-normal case\n\nIf ${tex`b \\sim B(x)`} is such that:\n${tex.block`b = m \\cdot e^{r\\cdot x + s\\cdot e}`}\n${tex.block`b \\sim LogNormal\\left(\\ln m+r\\cdot x, s\\right)`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":475,"value":"viewof FPAChartParameters = {\n let parameters = html``;\n parameters.oninput = () => {\n parameters.value = {\n x: parameters.x.valueAsNumber,\n m: parameters.m.valueAsNumber,\n r: parameters.r.valueAsNumber,\n s: parameters.s.valueAsNumber,\n av: parameters.av.valueAsNumber\n };\n };\n parameters.oninput();\n return parameters;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1564,"value":"tex`x=${FPAChartParameters.x}, m=${FPAChartParameters.m}, r=${FPAChartParameters.r}, s=${FPAChartParameters.s}, a\\cdot v=${FPAChartParameters.av}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":446,"value":"$49","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":880,"value":"md`\n#### Approximation by a family of shading functions\n\nIn our practical implementation we assume (as in the current *DSP* bid shading mechanism) that the shading function ${tex`S`} is of the form:\n${tex.block`S\\left(v\\right)=\\begin{cases}\n\\alpha \\cdot v & \\text{if }\\beta = 0 \\\\\n\\frac {\\left(1+\\alpha \\beta v\\right)^{1-\\rho}-1}{\\beta \\left(1-\\rho\\right)} & \\text{if }\\beta>0\\text{ and }\\rho \\neq 1 \\\\\n\\frac{1}{\\beta}\\ln(1+\\alpha \\beta v)&\\beta>0\\text{ and }\\rho =1\n\\end{cases}`}\nwhere ${tex`\\alpha \\in [0,1]`}, ${tex`\\beta \\geq 0`} and ${tex`\\rho > 0`}.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":552,"value":"aBb = (mu, sigma) => a => a + jstat.lognormal.cdf(a, mu, sigma)/(settings.epsilon + jstat.lognormal.pdf(a, mu, sigma));","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":520,"value":"shading = (mu, sigma) => {\n let aBbX = aBb(mu, sigma);\n return av => {\n let m = 0;\n let M = av;\n // Find by dichotomy\n while (M-m>0.01) {\n if (aBbX((M+m)/2)>av) {\n M = (M+m)/2;\n } else {\n m = (M+m)/2;\n }\n }\n return M;// Bidding higher is okay\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":832,"value":"md`\n## Simulation of campaigns over ${auctionsParameters.n} auctions for a budget of $${auctionsParameters.budget} and the following parameters\n\n${tex`\\left(\\mu, \\sigma\\right)`} = (${auctionsParameters.mu}, ${auctionsParameters.sigma})\n\n${tex`\\left(m, r, s\\right)`} = (${auctionsParameters.m}, ${auctionsParameters.r}, ${auctionsParameters.s})\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1401,"value":"md`\n### Auctions\nBlue bars represent the impression value and orange bars the highest other bid in **$CPM** as a function of **number of auctions run**.\n- Blue dots are the optimal SPA bids (pacing done from actual FPA).\n- Red dots are the shaded bids regardless of ${tex`x`} (*uniform shading*).\n- Green dots, the shaded bids using auction-level information ${tex`x`} (*auction based shading*).\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":787,"value":"$4a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"$4b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1569,"value":"tex`\\mu=${auctionsParameters.mu}, \\sigma=${auctionsParameters.sigma}, m=${auctionsParameters.m}, r=${auctionsParameters.r}, s=${auctionsParameters.s}, n=${auctionsParameters.n}, budget=${auctionsParameters.budget}, `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1411,"value":"$4c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1219,"value":"$4d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1480,"value":"md`\n## Conclusion\n\nIn general *Shaded per auction* > *Uniformely shaded* > *Unshaded* in terms of advertiser profit.\n\nBy varying the budget one can observe that:\n- In a *non budget-constrained environment* the unshaded bids yield *extremely poor performance* (zero profit).\n- In a *budget-constrained environment* unshaded and uniformly shaded bids can yield similar performance.\n - If *value* variability is small (${tex`\\sigma \\sim 0`}) both strategies yield the same results because uniform shading is fulfilled by the pacing factor.\n - If the *value* varies, the pacing factor cannot approximate the non-linear bid-shading function and both strategies diverge\n\nBy varying the predictible share of uncertainty: ${tex`r`} one can observe that:\n- The higher ${tex`r`}, the largest the difference between *shaded per auction* and *uniformely shaded*\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1467,"value":"md`\n### Distribution of values and bids\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":97,"value":"$4e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":856,"value":"pacing = (spend, budget) => {\n if (spend(1)>auctionsParameters.budget) {\n let m = 0;\n let M = 1;\n // find by dichotomy\n while (M-m > 0.01) {\n if (spend((M+m)/2)>auctionsParameters.budget) {\n M = (M+m)/2;\n } else {\n m = (M+m)/2;\n }\n }\n return m;// Negative errors are acceptable\n } else {\n return 1;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":808,"value":"bids = {\n let bid = (p,a) => p*a.v;\n let spend = p => auctions.reduce((s,a) => s + (bid(p, a) > a.b ? bid(p, a)/1000 : 0), 0);\n let p = pacing(spend, auctionsParameters.budget);\n return auctions.map(a => bid(p, a));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":810,"value":"uniformlyShadedBids = {\n let {m, r, s} = auctionsParameters;\n let bid = (p,a) => shading(Math.log(m), Math.sqrt(r*r + s*s))(p*a.v);\n let spend = p => auctions.reduce((s,a) => s + (bid(p, a) > a.b ? bid(p, a)/1000 : 0), 0);\n let p = pacing(spend, auctionsParameters.budget);\n return auctions.map(a => bid(p, a));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":811,"value":"shadedBids = {\n let bid = (p,a) => shading(a.mu, a.sigma)(p*a.v);\n let spend = p => auctions.reduce((s,a) => s + (bid(p, a) > a.b ? bid(p, a)/1000 : 0), 0);\n let p = pacing(spend, auctionsParameters.budget);\n return auctions.map(a => bid(p, a));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1164,"value":"campaign = {\n let spend = [];\n let value = [];\n let profit = [];\n let sumSpend = 0;\n let sumValue = 0;\n for (let i=0; iauctions[i].b) {\n sumSpend += bids[i]/1000;\n sumValue += auctions[i].v/1000;\n }\n spend.push(sumSpend);\n value.push(sumValue);\n profit.push(sumValue-sumSpend);\n }\n return {spend:spend, value:value, profit:profit};\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1175,"value":"uniformlyShadedCampaign = {\n let spend = [];\n let value = [];\n let profit = [];\n let sumSpend = 0;\n let sumValue = 0;\n for (let i=0; iauctions[i].b) {\n sumSpend += uniformlyShadedBids[i]/1000;\n sumValue += auctions[i].v/1000;\n }\n spend.push(sumSpend);\n value.push(sumValue);\n profit.push(sumValue-sumSpend);\n }\n return {spend:spend, value:value, profit:profit};\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1178,"value":"shadedCampaign = {\n let spend = [];\n let value = [];\n let profit = [];\n let sumSpend = 0;\n let sumValue = 0;\n for (let i=0; iauctions[i].b) {\n sumSpend += shadedBids[i]/1000;\n sumValue += auctions[i].v/1000;\n }\n spend.push(sumSpend);\n value.push(sumValue);\n profit.push(sumValue-sumSpend);\n }\n return {spend:spend, value:value, profit:profit};\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":"auctions = d3.range(auctionsParameters.n).map(() => {\n let x = jstat.normal.sample(0,1);\n let {mu, sigma, m, r, s} = auctionsParameters;\n let v = mu*Math.exp(sigma*jstat.normal.sample(0,1));\n let b = m*Math.exp(r*x + s*jstat.normal.sample(0,1));\n return {\n x: x,\n v: v,\n b: b,\n mu: Math.log(m) + r*x,\n sigma: s\n }\n});","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":320,"value":"md`\n## Settings\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":383,"value":"settings","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":322,"value":"viewof settings = {\n let colors = d3.schemeCategory10;\n let input = html``;\n input.oninput = () => {\n input.value = {\n colors: colors,\n valueColor: input.valueColor.value,\n bidColor: input.bidColor.value,\n shadedBidColor: input.shadedBidColor.value,\n uniformlyShadedBidColor: input.uniformlyShadedBidColor.value,\n margin: {top: 20, right: 20, bottom: 30, left: 40},\n height: 400,\n epsilon: 1e-3,\n maxBid: 50\n };\n };\n input.oninput();\n return input;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"md`\n## Importing libraries\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"d3 = require(\"d3\");","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":297,"value":"jstat = require(\"jstat\");","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4f","stdlib":"1"}} 44:"$43:body"