%北太天元(https://www.baltamatica.com/) 求解 廣義二價(jià)拍賣問(wèn)題

% 廣義二價(jià)拍賣（Generalized second-price auction, GSP）

% 假設(shè)有廣告位1、2、... 按點(diǎn)擊率(ctr)遞減順序排列。

% 每個(gè)廣告客戶j出價(jià)b_j，并假設(shè)廣告商按其出價(jià)的遞減順序進(jìn)行排序。每個(gè)廣告客戶被分配

% 與她的排名順序相關(guān)聯(lián)的廣告位。排位在第i高的廣告客戶只在收到點(diǎn)擊時(shí)付款，她只支付b_(i+1)。

% soc_welfare: social welfare, 所有玩家的收益和

% bid: bid for pay-per-click, 每次點(diǎn)擊投標(biāo)多少錢

% matrix of payoffs: 支付矩陣

% 占優(yōu)策略激勵(lì)相容（dominant-strategy incentive-compatibility，簡(jiǎn)寫(xiě)為DSIC）。這種情況下，說(shuō)真話是一種弱占優(yōu)策略，即無(wú)論別人采取什么策略，選擇說(shuō)真話這個(gè)策略的回報(bào)都大于等于其他策略的回報(bào)。由于在DSIC下，策略考慮者無(wú)法幫助任何其他人獲得比說(shuō)真話更多的回報(bào)，因此這個(gè)機(jī)制也被稱作策略一致或真實(shí)的。

%ctr: (click-through rate) 點(diǎn)擊率

% 假設(shè)廣告客戶 j 在接到一次點(diǎn)擊時(shí)會(huì)帶來(lái)v_j的價(jià)值的回饋，而且她的出價(jià)排名是第i高，

% 那么我們可以把她的效用(utility)寫(xiě)成 % 它獲得的價(jià)值回饋減去她支付的競(jìng)標(biāo)價(jià) b_{i+1} ,

% 然后把這個(gè)差再乘以點(diǎn)擊率:

% u_j = (v_j - b_{i+1}) ctr_i;

%

%每一次點(diǎn)擊給第j個(gè)廣告客戶帶來(lái)的價(jià)值

valuations = [1000000, 555710, 470400];

%點(diǎn)擊率

ctr = [1, 0.55071, 0.4704];

%支付矩陣

payoffs = rand(6, 3);

for i = 1:3

???for j = 1:3

???????if i ~= j %avoid comparing a player with themself

???????????switch i %looking at player i

???????????????case 1 %first player

???????????????????bid = valuations(2)-1;

???????????????????%calculate everyone's utility, populate the first row

???????????????????payoffs(1, :) = calc_utility(bid,i,valuations,ctr);

???????????????????bid = valuations(3)-1;

???????????????????%calculate everyone's utility, populate the second row

???????????????????payoffs(2, :) = calc_utility(bid,i, valuations, ctr);

???????????????case 2 %second player

???????????????????bid = valuations(3)-1;

???????????????????%calculate everyone's utility, populate the third row

???????????????????payoffs(3, :) = calc_utility(bid,i, valuations, ctr);

???????????????case 3 %third player

???????????????????%calculate everyone's utility, populate the fourth row

???????????????????payoffs(4, :) = calc_utility(bid,i, valuations, ctr);

???????????end

???????end

???end

end

%Utility for p1, p2, p3

soc_opt_utility = [-1,-1,-1];

soc_opt_utility(1) = ctr(1) * (valuations(1) - valuations(2));

soc_opt_utility(2) = ctr(2) * (valuations(2) - valuations(3));

soc_opt_utility(3) = ctr(3) * valuations(3);

%populating the fifth row

payoffs(5, :) = soc_opt_utility;

p3_p2_p1_utility = [-1, -1, -1];

p3_p2_p1_utility(1) = ctr(1) * (valuations(3) - (valuations(3)-1));

p3_p2_p1_utility(1) = ctr(3) * (valuations(3) - (valuations(3)-2));

p3_p2_p1_utility(1) = ctr(1) * valuations(3);

%populate the sixth row

payoffs(6, :) = soc_opt_utility;

%determine which utility is best

player_max_utility = max(payoffs);

for n = 1:3

???[max_row max_col] = find(payoffs==player_max_utility(n),1);

???switch max_row

???????case 1

???????????disp('Allocation: P2 -- Slot 1, P1 -- Slot 2, P3 -- Slot 3');

???????????soc_welfare = ctr(1) * valuations(2) + ctr(2) * valuations(1) + ctr(3) * valuations(3);

???????case 2

???????????disp('Allocation: P2 -- Slot 1, P3 -- Slot 2, P1 -- Slot 3');

???????????soc_welfare = ctr(1) * valuations(2) + ctr(2) * valuations(3) + ctr(3) * valuations(1);

???????case 3

???????????disp('Allocation: P1 -- Slot 1, P3 -- Slot 2, P2 -- Slot 3');

???????????soc_welfare = (ctr(1) * valuations(1)) + (ctr(2) * valuations(3)) + (ctr(3) * valuations(2));

???????case 4

???????????disp('Allocation: P3 -- Slot 1, P1 -- Slot 2, P2 -- Slot 3');

???????????soc_welfare = ctr(1) * valuations(3) + ctr(2) * valuations(1) + ctr(3) * valuations(2);

???????%case 5

???????????%disp('Allocation: P1 -- Slot 1, P2 -- Slot 2, P3 -- Slot 3');

???????????%soc_welfare = ctr(1) * valuations(1) + ctr(2) * valuations(2) + ctr(3) * valuations(3);

???????case 6

???????????disp('Allocation: P3 -- Slot 1, P2 -- Slot 2, P1 -- Slot 3');

???????????soc_welfare = ctr(1) * valuations(3) + ctr(2) * valuations(2) + ctr(3) * valuations(1);

???end

end

price_of_anarchy = round(soc_welfare / 1527311.214,5);

disp(price_of_anarchy);

%Calculates the utility of each slot allocation

function utilities = calc_utility(bid,player, valuations, ctr)?

???utilities = [-1 -1 -1];

???final_bid = valuations;

???final_bid(player) = bid;

???%calculate each utility, put it in the vector

???????if player ~=3

???????????if final_bid(1) > final_bid(2) && final_bid(2) > final_bid(3) %p1, p2, p3

??????????????u1 = round(ctr(1) * (valuations(1) - final_bid(2)),0); %utility of the first player

??????????????u2 = round(ctr(2) * (valuations(2) - final_bid(3)),0);

??????????????u3 = round(ctr(3) * valuations(3),0);

???????????elseif final_bid(1) > final_bid(2) && final_bid(3) > final_bid(2) %p1, p3, p2

???????????????u1 = round(ctr(1) * (valuations(1) - final_bid(3)),0);

???????????????u3 = round(ctr(2) * (valuations(3) - final_bid(2)),0);

???????????????u2 = round(ctr(3) * valuations(2),0);

???????????elseif final_bid(2) > final_bid(1) && final_bid(1) > final_bid(3) %p2, p1, p3

???????????????u2 = round(ctr(1) * (valuations(2) - final_bid(1)),0);

???????????????u1 = round(ctr(2) * (valuations(1) - final_bid(3)),0);

???????????????u3 = round(ctr(3) * valuations(3),0);

???????????elseif final_bid(2) > final_bid(1) && final_bid(3) > final_bid(1) %p2, p3, p1

???????????????u2 = round(ctr(1) * (valuations(2) - final_bid(3)),0);

???????????????u3 = round(ctr(2) * (valuations(3) - final_bid(1)),0);

???????????????u1 = round(ctr(3) * valuations(1),0);

???????????%else %p3, p2, p1

????????????%??u3 = ctr(1) * (valuation(3) - final_bid(2));

?????????????%?u2 = ctr(2) * (valuation(2) - final_bid(1));

??????????????% u1 = ctr(3) * valuation(1);

???????????end

???????end

???????????%p3, p1, p2

???if player == 3????

???????final_bid(1) = valuations(3)-1;

???????final_bid(2) = valuations(3)-2;

???????u3 = round(ctr(1) * (valuations(3) - final_bid(1)),0);

???????u1 = round(ctr(2) * (valuations(1) - final_bid(2)),0);

???????u2 = round(ctr(3) * valuations(2),0);

???end

???????utilities(1) = u1;

???????utilities(2) = u2;

???????utilities(3) = u3;

end