Consider the following sponsored search auction instance I: 2 slots. The top slot has a...

 

Transcribed Image Text:

Consider the following sponsored search auction instance I: • 2 slots. The top slot has a known click-through rate (CTR) ctri = 1 and the bottom slot has a known click-through rate ctr3 = 0.5. . 2 advertisers. Advertiser 1 has a private value-per-click v₁ = 1 and advertiser 2 has a private value-per-click v2 = 0.5. • The payoff of the advertiser (let's call them i, i = 1,2) who is assigned to the top slot is (v₂ - p), where p is the price charged per-click in the top slot. The payoff of i in the bottom slot is 0.5. vi (price 0 is charged per-click in the bottom slot). Under the Generalized Second-Price (GSP) auction rule: - Advertisers are asked to declare their value per click (this doesn't mean that their declarations are truthful!). Advertisers are then ranked according to their declarations and the advertiser with the highest declaration is assigned to the slot with the highest CTR (top slot), the advertiser with the second highest declaration is assigned to the slot with the lowest CTR (bottom slot). In case of a tie, advertiser 1 is allocated to the top slot. The per-click payment p at the top slot j, is set to be equal to the declaration of the advertiser assigned to the bottom slot. a. [7%] Compute the optimal/highest social welfare (sum of individual values) in I. b. [23% ] Assume the following strategy sets (the allowed strategies/reports each player can make) S₁ = {0,0.5, 1} and S2 = {0,0.5). Write MATLAB code that computes all Nash equilibria in I, and outputs the social welfare achieved in each of them. You can (or not) follow a brute-force approach, i.e. consider all possible combinations of declarations and for each of them check if it is an equilibrium. Copy and paste your MATLAB code in your report, and explicitly mention where in your MATLAB code you guarantee that the equilibrium conditions are satisfied (even if your code doesn't run or doesn't compute an equilibrium). If your code successfully computes one or more equilibria, present them in the report alongside their social welfare. Marks will be awarded for partially-correct approaches. Consider the following sponsored search auction instance I: • 2 slots. The top slot has a known click-through rate (CTR) ctri = 1 and the bottom slot has a known click-through rate ctr3 = 0.5. . 2 advertisers. Advertiser 1 has a private value-per-click v₁ = 1 and advertiser 2 has a private value-per-click v2 = 0.5. • The payoff of the advertiser (let's call them i, i = 1,2) who is assigned to the top slot is (v₂ - p), where p is the price charged per-click in the top slot. The payoff of i in the bottom slot is 0.5. vi (price 0 is charged per-click in the bottom slot). Under the Generalized Second-Price (GSP) auction rule: - Advertisers are asked to declare their value per click (this doesn't mean that their declarations are truthful!). Advertisers are then ranked according to their declarations and the advertiser with the highest declaration is assigned to the slot with the highest CTR (top slot), the advertiser with the second highest declaration is assigned to the slot with the lowest CTR (bottom slot). In case of a tie, advertiser 1 is allocated to the top slot. The per-click payment p at the top slot j, is set to be equal to the declaration of the advertiser assigned to the bottom slot. a. [7%] Compute the optimal/highest social welfare (sum of individual values) in I. b. [23% ] Assume the following strategy sets (the allowed strategies/reports each player can make) S₁ = {0,0.5, 1} and S2 = {0,0.5). Write MATLAB code that computes all Nash equilibria in I, and outputs the social welfare achieved in each of them. You can (or not) follow a brute-force approach, i.e. consider all possible combinations of declarations and for each of them check if it is an equilibrium. Copy and paste your MATLAB code in your report, and explicitly mention where in your MATLAB code you guarantee that the equilibrium conditions are satisfied (even if your code doesn't run or doesn't compute an equilibrium). If your code successfully computes one or more equilibria, present them in the report alongside their social welfare. Marks will be awarded for partially-correct approaches.