楊 雪 董紅斌 滕旭陽(yáng)

(哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001) (yangxue@hrbeu.edu.cn)

一種視頻廣告的預(yù)算約束限制拍賣(mài)機(jī)制

楊 雪 董紅斌 滕旭陽(yáng)

(哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 哈爾濱 150001) (yangxue@hrbeu.edu.cn)

視頻廣告作為新興互聯(lián)網(wǎng)廣告的一個(gè)重要的分支，為廣告商帶來(lái)巨大的收益，目前對(duì)于視頻廣告的拍賣(mài)方式主要采用關(guān)鍵字拍賣(mài)中的廣義第二價(jià)格拍賣(mài)機(jī)制.但由于視頻廣告的時(shí)間可分性，使得視頻廣告與關(guān)鍵字拍賣(mài)內(nèi)在上成為2個(gè)不同的問(wèn)題.針對(duì)這些問(wèn)題，主要工作如下：1)定義在線視頻廣告的形式化模型.該模型是有公共預(yù)算限制和私有價(jià)格信息的異質(zhì)多物品拍賣(mài)模型，且該模型不限制競(jìng)價(jià)者的收益函數(shù)分布.2)前期工作已經(jīng)證明了不同時(shí)存在具有個(gè)體理性、激勵(lì)相容性和帕累托最優(yōu)性質(zhì)的預(yù)算約束拍賣(mài)的確定性機(jī)制.所以針對(duì)視頻廣告拍賣(mài)問(wèn)題，基于預(yù)算約束的嵌釘拍賣(mài)基礎(chǔ)，提出不限制競(jìng)拍者Agent的邊際效益形式且滿足激勵(lì)相容性、個(gè)體理性激勵(lì)相容的隨機(jī)機(jī)制.3)定性及定量分析了該機(jī)制的收益性質(zhì).通過(guò)定義分配因子和支配因子證明了該機(jī)制收益的下界，并通過(guò)針對(duì)不同分布的收益函數(shù)和預(yù)算約束的實(shí)驗(yàn)，在系統(tǒng)收益和社會(huì)效用2個(gè)指標(biāo)上驗(yàn)證了該機(jī)制的有效性.

多Agent系統(tǒng);拍賣(mài)機(jī)制設(shè)計(jì);在線視頻廣告;預(yù)算約束;非線性邊際價(jià)值

在線廣告系統(tǒng)作為IT產(chǎn)業(yè)中最重要的一個(gè)部分每年為出版商帶來(lái)巨大的利潤(rùn).作為一種高質(zhì)量的傳播媒體，視頻廣告將會(huì)成為增長(zhǎng)最快的廣告形式，而且在2018年年增長(zhǎng)率將會(huì)達(dá)到23.8%，領(lǐng)先于手機(jī)廣告21.5%[1-2].YouTube是全球最大的視頻服務(wù)商，每年從其廣告產(chǎn)品TrueView中贏取巨大收益.當(dāng)YouTube的用戶點(diǎn)擊觀看某一視頻時(shí)，網(wǎng)站會(huì)選擇一個(gè)廣告在視頻播放前進(jìn)行播放.用戶可以有2種選擇：觀看或者跳過(guò).用戶觀看廣告則會(huì)對(duì)廣告商產(chǎn)生收益，如直接購(gòu)買(mǎi)或者品牌價(jià)值提升等.出版商，即視頻網(wǎng)站，需要從眾多的廣告投放者中選擇廣告，通常是通過(guò)以最大化收益為目的拍賣(mài)的形式進(jìn)行選擇.眾多的視頻網(wǎng)站都選擇廣義第二價(jià)格拍賣(mài)(generalized second price auction, GSP)，因?yàn)檫@種拍賣(mài)形式在理論上會(huì)帶來(lái)較高收益且容易實(shí)現(xiàn)，其次作為關(guān)鍵詞廣告所采用的拍賣(mài)形式，其也被廣泛接受.

但是視頻廣告服務(wù)網(wǎng)站往往需要廣告商提供預(yù)算來(lái)控制其成本.在這種情況下，作為非激勵(lì)相容拍賣(mài)機(jī)制的廣義第二價(jià)格拍賣(mài)很容易被策略性的競(jìng)價(jià)來(lái)操縱.對(duì)于可以順序播放數(shù)個(gè)廣告的視頻廣告系統(tǒng)來(lái)說(shuō)，每一個(gè)廣告商對(duì)物品的需求也從單一的廣告位變?yōu)榧葘?duì)廣告順序的需求且同時(shí)對(duì)其所獲得的時(shí)間長(zhǎng)度2種需求的混合形式，這使得視頻廣告系統(tǒng)成為了比關(guān)鍵字廣告更加復(fù)雜的拍賣(mài)問(wèn)題.在這種情況下簡(jiǎn)單地使用廣義第二價(jià)格拍賣(mài)機(jī)制會(huì)對(duì)廣告商和發(fā)布商的收益產(chǎn)生影響.

因此本文提出一種新的視頻廣告市場(chǎng)模型，與YouTube現(xiàn)有模型不同，該模型允許可以播放多個(gè)預(yù)播廣告.每個(gè)廣告商都有多個(gè)任意長(zhǎng)度的廣告，播放這些廣告會(huì)為他們帶來(lái)一定的私有價(jià)值.此外，每一個(gè)競(jìng)價(jià)者對(duì)他支付的價(jià)格總額都有預(yù)算約束.拍賣(mài)的輸出是為每一個(gè)競(jìng)價(jià)者分配一個(gè)播放的時(shí)長(zhǎng)、確定播放的順序和對(duì)每一次播放需要支付的價(jià)格.因此，該問(wèn)題可以抽象為基于預(yù)算約束的異質(zhì)多物品拍賣(mài)問(wèn)題.

從之前的對(duì)于視頻廣告的研究中，針對(duì)基于預(yù)算約束的異質(zhì)多物品拍賣(mài)問(wèn)題，不存在能同時(shí)滿足個(gè)體理性、激勵(lì)相容和帕累托最優(yōu)等性質(zhì)的機(jī)制.此外，關(guān)于這個(gè)領(lǐng)域的大部分研究是基于邊際效益遞減假設(shè)，這嚴(yán)重限制了機(jī)制在實(shí)際中的應(yīng)用.基于上述原因，本文關(guān)注于設(shè)計(jì)基于多樣性的價(jià)值分布的激勵(lì)相容機(jī)制.首先在激勵(lì)相容的確定性機(jī)制基礎(chǔ)之上提出一種隨機(jī)機(jī)制，然后分析了本文提出的機(jī)制的收益性質(zhì)，并與最優(yōu)定價(jià)拍賣(mài)進(jìn)行了比較.對(duì)預(yù)算及用戶的價(jià)值函數(shù)對(duì)于拍賣(mài)商收益的影響進(jìn)行了討論.尤其是給出了線性邊際效益的條件下，有2個(gè)競(jìng)價(jià)者參與時(shí)的收益區(qū)間.隨后按照競(jìng)價(jià)者收益邊際效益不變、遞增和遞減幾種情況，將本文提出的機(jī)制在收益和社會(huì)福利2個(gè)指標(biāo)上與定價(jià)機(jī)制和維克利拍賣(mài)機(jī)制進(jìn)行了比較.

1 相關(guān)工作

與關(guān)鍵字拍賣(mài)類(lèi)似，在線視頻廣告也是一種異質(zhì)多物品拍賣(mài)，但其是一種更加復(fù)雜的異質(zhì)多物品拍賣(mài)的變體形式.GSP機(jī)制是目前應(yīng)用最廣泛的關(guān)鍵字拍賣(mài)機(jī)制，Varian[3]和Edelman等人[4]對(duì)原始的GSP拍賣(mài)機(jī)制的均衡性等問(wèn)題進(jìn)行了分析.而在加入預(yù)算約束的情況下，原始的GSP機(jī)制變得不再適用.Díaz等人[5]對(duì)GSP機(jī)制進(jìn)行了改進(jìn)，他們提出了幾個(gè)不同的考慮預(yù)算約束的GSP機(jī)制，并證明了在改進(jìn)的機(jī)制中納什均衡和局部無(wú)嫉妒均衡存在的穩(wěn)定性.而在考慮設(shè)計(jì)激勵(lì)相容的機(jī)制方面，Borgs等人[6]2005年在競(jìng)價(jià)者的價(jià)格和預(yù)算都是私有信息的條件下提出一種隨機(jī)機(jī)制，將所有參與者隨機(jī)分成2個(gè)集合，并互相使用另一集合的最優(yōu)價(jià)格作為其支付價(jià)格.Borgs等人證明了這個(gè)機(jī)制是收益最大化的激勵(lì)相容機(jī)制.同時(shí)該文章還指出在預(yù)算信息下，沒(méi)有任何的激勵(lì)相容機(jī)制可以滿足社會(huì)福利最大化的性質(zhì).

而在另一方面，嵌釘拍賣(mài)給研究人員提供了很好的思路.Ausubel[7]在2004年首次針對(duì)同質(zhì)物品分配提出了嵌釘拍賣(mài).該拍賣(mài)機(jī)制被證明與Vickrey 拍賣(mài)有相同的輸出，但是其具有更易懂和私有性更好等特點(diǎn)而易于推廣.而2012年Dobzinski等人[8]將預(yù)算約束加入到嵌釘拍賣(mài)中，并指出在有2個(gè)參與者存在的情況下，具有預(yù)算約束的嵌釘拍賣(mài)機(jī)制是唯一能同時(shí)滿足個(gè)體理性、激勵(lì)相容、和帕累托最優(yōu)條件的機(jī)制.他對(duì)基于預(yù)算約束的研究引導(dǎo)了很多不同方向的研究.但是這個(gè)工作是針對(duì)同質(zhì)物品進(jìn)行分配，并且假設(shè)所有的商品的邊際價(jià)值為恒定值.Colini-Baldeschi等人[9]基于嵌釘拍賣(mài)方法在關(guān)鍵字拍賣(mài)問(wèn)題上，加入了點(diǎn)擊率，分別對(duì)廣告位可分和不可分的情況提出了確定的和隨機(jī)的2種機(jī)制，并證明了他們都是滿足帕累托最優(yōu)性質(zhì)的.而Goel等人[10]提出了一種多角嵌釘拍賣(mài)，該機(jī)制保證了嵌釘拍賣(mài)的基本性質(zhì)，并且其更加易于擴(kuò)展.他們還進(jìn)一步對(duì)非硬約束的情況進(jìn)行了研究[11]，在嵌釘拍賣(mài)的框架下使用下降價(jià)格，保證了算法的激勵(lì)相容和帕累托最優(yōu)的性質(zhì).但是目前主要的研究都是基于擬線性收益或邊際價(jià)值遞減的假設(shè)的基礎(chǔ)之上，當(dāng)這個(gè)約束條件被放松后，有約束限制的異質(zhì)物品拍賣(mài)機(jī)制的性質(zhì)很難被保證.

此外，也有很多學(xué)者致力于研究在基于預(yù)算約束下的異質(zhì)多物品拍賣(mài)問(wèn)題中的不可能性結(jié)果[9-10,12].在預(yù)算約束為公共信息的條件下，對(duì)于單調(diào)的遞減邊際價(jià)值分布的情況，文獻(xiàn)[13]指出對(duì)于異質(zhì)可加物品拍賣(mài)沒(méi)有確定性機(jī)制能同時(shí)滿足個(gè)體理性、帕累托最優(yōu)和激勵(lì)相容的性質(zhì).但是對(duì)于一維拍賣(mài)問(wèn)題，存在不確定性機(jī)制同時(shí)滿足以上3個(gè)條件.此外對(duì)于可分物品拍賣(mài)也進(jìn)行了研究，綜合以上文獻(xiàn)對(duì)該問(wèn)題的研究結(jié)果如表1所示[12,14-17]：

Table 1 The Status of Divisible Items Auction Under Budget Limits

Fig. 1 Video ad agents system圖1 視頻廣告Agent系統(tǒng)

2 視頻廣告拍賣(mài)形式化模型

在視頻廣告投放市場(chǎng)中，有3種Agent：視頻網(wǎng)站用戶、廣告商和出版商.當(dāng)用戶播放某一特定的視頻時(shí)，將會(huì)被展示一些廣告.對(duì)于某特定視頻，在其之前播放的廣告集合、播放順序以及對(duì)該廣告需要支付的價(jià)格通過(guò)拍賣(mài)的程序決定.當(dāng)用戶觀看這些廣告時(shí)，可以選擇點(diǎn)擊或者在播放幾秒之后跳過(guò).如果某條廣告被觀看完成、被點(diǎn)擊或者觀看超過(guò)一定的時(shí)長(zhǎng)(如30 s或廣告長(zhǎng)度的50%)，則投放該廣告的廣告商需要向出版商支付一定的費(fèi)用.拍賣(mài)的過(guò)程結(jié)合了確定將會(huì)被展示的廣告集合和為每一個(gè)展示了廣告的視頻廣告商確定合理的支付價(jià)格2個(gè)過(guò)程.廣告商可能有不同時(shí)長(zhǎng)的廣告可以參與競(jìng)拍，并且其對(duì)于全部可支付的價(jià)格存在預(yù)算約束.圖1是對(duì)視頻廣告市場(chǎng)的簡(jiǎn)單概述.

假設(shè)市場(chǎng)中有3個(gè)廣告商，每個(gè)廣告商有3個(gè)不同市場(chǎng)的廣告可以播放，且其播放成本約束于其預(yù)算.如果用戶進(jìn)入到視頻播放頁(yè)面，出版商將會(huì)要求所有廣告商提交競(jìng)價(jià)、組織拍賣(mài)并最終確定需要播放的廣告的集合和廣告播放的順序以及需要支付的價(jià)格.用戶可以選擇觀看或者跳過(guò)某廣告，如果用戶觀看了該廣告，則出版商將會(huì)對(duì)這次廣告的展示收取費(fèi)用，但是這個(gè)費(fèi)用將會(huì)嚴(yán)格低于該廣告商的預(yù)算約束.下面對(duì)這個(gè)市場(chǎng)模型進(jìn)行形式化的描述.

2.1 市場(chǎng)定義

首先考慮一個(gè)簡(jiǎn)單的在線視頻廣告發(fā)布環(huán)境.在某視頻發(fā)布平臺(tái)上，播放某一特定視頻之前會(huì)有一些廣告首先播放.假設(shè)可以播放廣告的總時(shí)間為M，對(duì)該廣告位有興趣的競(jìng)拍者集合為N.每一個(gè)競(jìng)拍Agenti(i∈N)的廣告被視頻網(wǎng)站的用戶瀏覽之后都會(huì)獲得一定的私有價(jià)值，即用戶在觀看廣告后潛在地產(chǎn)生購(gòu)買(mǎi)行為等.進(jìn)一步假設(shè)每一個(gè)廣告商都有不同長(zhǎng)度的廣告可以被播放，而且不同長(zhǎng)度的廣告會(huì)帶來(lái)不同的價(jià)值.因此，每一個(gè)廣告商Agenti的價(jià)值定義為函數(shù)vi,其輸入為廣告的長(zhǎng)度(單位s)，輸出是其相對(duì)應(yīng)的收益價(jià)值.

(1)

從收益的定義中可知，Agent的收益函數(shù)是非擬線性的.

2.2 重要性質(zhì)

在給定了市場(chǎng)模型的形式化描述之后，下面將會(huì)定義一些本文機(jī)制需要滿足的性質(zhì).

給定一個(gè)分配，所有交易者的效用總和稱為社會(huì)福利，則機(jī)制的有效性可以定義如下.

換句話說(shuō)，當(dāng)廣告商對(duì)于其要播放的廣告所付出的價(jià)格不會(huì)高于其真實(shí)估價(jià)，且他的支付不會(huì)超過(guò)其預(yù)算時(shí)，該機(jī)制符合個(gè)體理性性質(zhì).

在具有激勵(lì)相容性的機(jī)制中，參與競(jìng)價(jià)者上報(bào)自己真實(shí)報(bào)價(jià)能獲得不低于其他競(jìng)價(jià)策略的效用.該性質(zhì)使得系統(tǒng)在分配時(shí)能同時(shí)兼顧最大化社會(huì)總效用與最大化競(jìng)價(jià)者效用.

3 機(jī)制設(shè)計(jì)

第2節(jié)形式化地定義了對(duì)于公共預(yù)算情況下的拍賣(mài)機(jī)制.針對(duì)該模型，本文基于Dobzinski等人[8]的工作，在嵌釘拍賣(mài)的基礎(chǔ)之上進(jìn)一步研究.首先討論了VCG(Vickrey-Clarke-Groves auction)模型和基本的嵌釘拍賣(mài)在視頻廣告模型中的不適用性;然后給出了一種激勵(lì)相容的拍賣(mài)機(jī)制模型，并證明了該模型的一些基本性質(zhì);最后通過(guò)算例來(lái)解釋該模型.

3.1 VCG模型

當(dāng)參與者具有擬線性收益函數(shù)時(shí)，VCG機(jī)制是一種最大化社會(huì)效用的激勵(lì)相容機(jī)制.但是當(dāng)參與者的收益函數(shù)為非擬線性設(shè)置時(shí)，VCG機(jī)制的激勵(lì)相容性就難以被保證.如在添加了預(yù)算約束的情況下，競(jìng)拍者的收益函數(shù)變?yōu)?/p>

(2)

若在VCG機(jī)制中，分配給競(jìng)拍者的物品價(jià)格高于其預(yù)算約束，則該分配會(huì)被取消，競(jìng)拍者效用為0.此時(shí)競(jìng)拍者可能會(huì)改變其報(bào)價(jià)，使得在其預(yù)算約束內(nèi)獲得較少的物品而達(dá)到高于0的效用.此時(shí)的VCG機(jī)制就不再激勵(lì)相容.

3.2 基本的嵌釘拍賣(mài)

基本的嵌釘拍賣(mài)是 Ausubel[7]首次提出的，嵌釘拍賣(mài)是一種升價(jià)拍賣(mài)，在每一次價(jià)格升高時(shí)，競(jìng)價(jià)者會(huì)提交一個(gè)對(duì)于該價(jià)格的物品需求數(shù)量.該拍賣(mài)機(jī)制對(duì)于復(fù)雜的多物品拍賣(mài)與VCG機(jī)制具有相同的輸出，但是同時(shí)具有易于理解和實(shí)現(xiàn)等優(yōu)點(diǎn).Dobzinski等人在Ausubel工作的基礎(chǔ)上對(duì)于嵌釘拍賣(mài)進(jìn)行了改進(jìn)，他們提出了一種在預(yù)算約束下的嵌釘多物品拍賣(mài)機(jī)制.特別地,他們指出，在私有預(yù)算約束和私有價(jià)值函數(shù)信息的條件下，不存在同時(shí)滿足激勵(lì)相容性和帕累托最優(yōu)的機(jī)制.而在公共預(yù)算和私有價(jià)值函數(shù)以及所有競(jìng)拍者的邊際價(jià)值是固定不變的情況下，基于預(yù)算約束的嵌釘拍賣(mài)是唯一同時(shí)滿足激勵(lì)相容性和帕累托最優(yōu)的機(jī)制.

在嵌釘拍賣(mài)中首先定義參與競(jìng)拍者的需求為:

(3)

在基于預(yù)算約束的嵌釘拍賣(mài)問(wèn)題中，基礎(chǔ)價(jià)格逐步增加，而每一個(gè)競(jìng)價(jià)者對(duì)于物品的需求隨著價(jià)格的增加逐步降低.每一個(gè)物品給競(jìng)價(jià)者所帶來(lái)的價(jià)值在競(jìng)價(jià)的過(guò)程中是穩(wěn)定不變的.而需求則被定義為在當(dāng)前的價(jià)格下，每一個(gè)競(jìng)價(jià)者在其預(yù)算約束下能負(fù)擔(dān)的最多的個(gè)體數(shù)量.在除了某競(jìng)價(jià)者i之外的所有人的需求之和小于當(dāng)前市場(chǎng)可提供的物品總量時(shí)，該競(jìng)價(jià)者i則會(huì)以當(dāng)前的價(jià)格“釘住”滿足所有其他競(jìng)價(jià)者需求時(shí)的剩余物品.因此，在不同的價(jià)格下，每一個(gè)競(jìng)價(jià)者所能獲得的價(jià)格不同.在拍賣(mài)最后，每一個(gè)競(jìng)價(jià)按照其所釘住的物品的數(shù)量和對(duì)應(yīng)的價(jià)格的總和支付.

在基本嵌釘拍賣(mài)中討論的是離散的同質(zhì)多物品拍賣(mài)，對(duì)于每一個(gè)競(jìng)價(jià)者來(lái)說(shuō)，其邊際價(jià)值在拍賣(mài)過(guò)程中是恒定不變的.但是，在線視頻廣告問(wèn)題中，拍賣(mài)的標(biāo)的物品為播放時(shí)長(zhǎng)，該物品是無(wú)限可分的，且不同長(zhǎng)度的廣告會(huì)為廣告商帶來(lái)不同的利潤(rùn).此外，每一個(gè)廣告的位置也會(huì)影響到每一個(gè)競(jìng)價(jià)者的效用，這使得本文的問(wèn)題變成了一種復(fù)雜的異質(zhì)多物品拍賣(mài)問(wèn)題.接下來(lái)的內(nèi)容會(huì)給出一種改進(jìn)的嵌釘拍賣(mài)算法，來(lái)解決這些問(wèn)題.

3.3 同質(zhì)約束嵌釘拍賣(mài)

為方便討論，首先考慮一個(gè)同質(zhì)連續(xù)物品拍賣(mài)的問(wèn)題，即假設(shè)所有的廣告的關(guān)注程度與播放順序無(wú)關(guān).視頻廣告拍賣(mài)機(jī)制的輸出則為：為每一個(gè)競(jìng)價(jià)者分配一個(gè)播放時(shí)長(zhǎng)xi并為其確定支付價(jià)格{pi}.那么對(duì)于廣告商i，其獲得任何不同的一個(gè)時(shí)長(zhǎng)對(duì)于其效用不會(huì)產(chǎn)生影響.廣告商Agenti的效用計(jì)算方式為

(4)

在同質(zhì)約束嵌釘拍賣(mài)中，為每一個(gè)參與者i記錄已經(jīng)分配給其的物品數(shù)量xi，當(dāng)前的全部需要支付價(jià)格pi，以及其剩余預(yù)算Bi=βi-pi.機(jī)制也會(huì)記錄基礎(chǔ)價(jià)格b*和剩余物品的數(shù)量q.價(jià)格p*隨著需求嚴(yán)格大于全部可供應(yīng)量而逐步上升.在基于預(yù)算約束的嵌釘拍賣(mài)中，每一個(gè)參與者Agent的邊際效益在拍賣(mài)過(guò)程中保持不變，則其需求定義為能使得競(jìng)拍Agenti帶來(lái)最高收益的單元數(shù)量.但是在考慮不限制邊際價(jià)值分布的情況下，為了保持機(jī)制的激勵(lì)相容性，本文定義最大需求(max-demand)，即在不考慮競(jìng)價(jià)者的估值情況下，基于當(dāng)前的價(jià)格，其所能負(fù)擔(dān)的最多物品的數(shù)量：

Di=Bip.

(5)

則機(jī)制按如下步驟運(yùn)行：

2) 通過(guò)價(jià)格增量ε持續(xù)增加基礎(chǔ)價(jià)格，同時(shí)競(jìng)拍Agent的max-demand持續(xù)降低.直到對(duì)于競(jìng)價(jià)者i，除其以外的其他所有人的max-demand之和嚴(yán)格小于剩余物品的數(shù)量，計(jì)算這個(gè)差值為πi.πi為當(dāng)價(jià)格為p時(shí)，競(jìng)價(jià)者i可以獲得的最多物品量：

(6)

為每一個(gè)Agent計(jì)算其max-demand的差值后，機(jī)制儲(chǔ)存每一輪為Agent分配的時(shí)長(zhǎng)及價(jià)格.根據(jù)以下的公式更新相關(guān)變量：

(7)

3) 重復(fù)步驟2.直到所有人的最大需求之和小于當(dāng)前系統(tǒng)所能提供的全部物品的數(shù)量∑D(bp)≤q，則按照當(dāng)前的價(jià)格滿足所有人的最大需求.

4) 在拍賣(mài)結(jié)束后，按照Agenti對(duì)于不同長(zhǎng)度廣告所獲的的效用， 選擇使得Agenti收益最大的時(shí)長(zhǎng)最終分配給該Agent，將剩余的物品丟棄.至此完成了對(duì)所有競(jìng)價(jià)者時(shí)長(zhǎng)的分配.

3.4 異質(zhì)約束嵌釘拍賣(mài)

本節(jié)將同質(zhì)約束嵌釘拍賣(mài)擴(kuò)展到異質(zhì)物品的情況，即對(duì)于不同的廣告，先播放能使其獲得更高的關(guān)注率.機(jī)制的輸出為分配X={di,q∈M×Q}和支付{pi}.此時(shí)競(jìng)價(jià)者的效用函數(shù)改變?yōu)?/p>

(8)

由Colini-Baldeschi[9]和Goel等人[10]的工作，對(duì)于異質(zhì)拍賣(mài)，并且估值函數(shù)并不是擬線性情況下，不存在確定性的算法滿足IC和PO的性質(zhì).所以選擇一種簡(jiǎn)單的方式來(lái)保證算法激勵(lì)相容性，將所有的競(jìng)價(jià)者以分布為U(0，m)的情況隨機(jī)取樣，來(lái)決定最終Agent的分配順序.

3.5 性 質(zhì)

對(duì)于上述的同質(zhì)和異質(zhì)約束嵌訂拍賣(mài)機(jī)制，由于每一個(gè)競(jìng)價(jià)者的全部支付不會(huì)超過(guò)其預(yù)算，個(gè)體理性的性質(zhì)可以立刻得到.

定理1. 競(jìng)價(jià)者的支付將永遠(yuǎn)不會(huì)高于其預(yù)算.

(9)

證畢.

定理2. 在任意的邊際效益分布條件下，同質(zhì)拍賣(mài)機(jī)制是激勵(lì)相容的.

證明. 對(duì)于每一個(gè)i和v-i來(lái)說(shuō)，由于其滿足以下條件，該機(jī)制是激勵(lì)相容的：

1) 支付pi只依賴于其預(yù)算約束，而不依賴于vi.此外由于預(yù)算是公共信息，則對(duì)于每一個(gè)vi，θi∈θ存在著價(jià)格pθ∈，因此對(duì)于所有使得f(vi,v-i)=x的vi，都有p(vi,v-i)=pθ.

證畢.

定理3. 同質(zhì)機(jī)制總是銷(xiāo)售市場(chǎng)上的所有單元.

定理4. 異質(zhì)約束嵌釘拍賣(mài)機(jī)制在所有的邊際效益分布情況下都是滿足IC，IR的.

異質(zhì)物品拍賣(mài)機(jī)制并不改變每一個(gè)競(jìng)價(jià)者的支付規(guī)則，所以IR和IC等性質(zhì)可以容易地從同質(zhì)物品拍賣(mài)的情況得到.

4 收益分析

4.1 最優(yōu)收益定價(jià)拍賣(mài)機(jī)制

為了方便比較分析，首先定義定價(jià)最優(yōu)收益拍賣(mài)機(jī)制.在Borgs等人[6]的工作中，他們描述了一種對(duì)于所有Agent都以確定的價(jià)格進(jìn)行銷(xiāo)售，該機(jī)制可以在不考慮其他性質(zhì)的前提下最大化拍賣(mài)者的收益.假設(shè)在該機(jī)制中，分配給競(jìng)價(jià)者i的物品數(shù)量為xi, 且所有的物品以確定價(jià)格p銷(xiāo)售.針對(duì)視頻廣告拍賣(mài)環(huán)境下，滿足個(gè)體理性的分配中可行的定價(jià)拍賣(mài)需要滿足以下條件：xi≥0，βi≥xip且vi,xi≥xip.假設(shè)當(dāng)價(jià)格p=p*時(shí)，此時(shí)分配X={x*}，能最大化拍賣(mài)商的收益：

,

(10)

本文和Dobzinski等人[8]的工作一樣，定義競(jìng)價(jià)者支配因子：

.

(11)

4.2 同質(zhì)物品拍賣(mài)收益

本節(jié)分析對(duì)于同質(zhì)物品拍賣(mài)情況下的收益.

(12)

證畢.

進(jìn)而可以得到如下的引理.

證畢.

4.3 支付和分配分析

在確定性同質(zhì)約束嵌釘拍賣(mài)機(jī)制中，支付和分配規(guī)則都是由預(yù)算確定的.現(xiàn)在討論在不同的估值函數(shù)下，機(jī)制的收益與預(yù)算之間的關(guān)系.首先考慮一種簡(jiǎn)單的情況，假設(shè)市場(chǎng)中有m個(gè)單元需要出售，2個(gè)競(jìng)價(jià)Agent參與競(jìng)拍，其預(yù)算分別為β1,β2，且β1>β2.

(13)

且F(x)為

(14)

(15)

(16)

(17)

(18)

剩下的物品的單位價(jià)格可以通過(guò)歸納法獲得：

(19)

通過(guò)非齊次線性方程，可求得，

(20)

所以對(duì)于任意數(shù)量的物品所需要支付的價(jià)格為

F(x)=∫p(x)dx=

(21)

證畢.

這個(gè)結(jié)果也很容易擴(kuò)展到多個(gè)Agent的市場(chǎng)中.

4.4 丟棄物品后的收益

4.1～4.3節(jié)分析了算法1中的前3步的收益.然而，最終的收益會(huì)受到被丟棄的物品數(shù)量的影響.因此，本節(jié)分析不同的邊際函數(shù)的收益損失.

(22)

假設(shè)競(jìng)價(jià)者i有最高的預(yù)算，則拍賣(mài)商最終從i處獲得的收益為

(23)

(24)

為了簡(jiǎn)化分析，定義xmax是在市場(chǎng)中最后被分配的單元，則

(25)

Fig. 2 An example of revenue analysis圖2 收益分析實(shí)例

5 實(shí) 驗(yàn)

由于拍賣(mài)者的收益和社會(huì)總效用受競(jìng)拍者的價(jià)值函數(shù)和預(yù)算約束的影響.所以在本節(jié)中，設(shè)計(jì)了3個(gè)實(shí)驗(yàn)來(lái)分析不同情況下的價(jià)值函數(shù)分布以及預(yù)算約束對(duì)算法效果的影響.實(shí)驗(yàn)運(yùn)行在Windows 7平臺(tái)上，處理器為core 2 2.66 GHz，內(nèi)存為2.00 GB，采用的運(yùn)行環(huán)境為matlab2015b.

5.1 擬線性價(jià)值函數(shù)對(duì)收益影響分析

在實(shí)際應(yīng)用中競(jìng)拍者的收益函數(shù)可能是多樣的.所以在本節(jié)中，對(duì)競(jìng)拍者邊際價(jià)值(marginal value,mv)的幾種不同情況進(jìn)行了實(shí)驗(yàn)分析，比較本文提出的H-Clinching拍賣(mài)機(jī)制、VCG機(jī)制和定價(jià)拍賣(mài)的收益和社會(huì)效用.

1) 邊際價(jià)值為固定值

設(shè)置2個(gè)競(jìng)價(jià)者的預(yù)算約束都為100，拍賣(mài)者提供的播放時(shí)長(zhǎng)為15 s.競(jìng)價(jià)者1的邊際效益為100;競(jìng)價(jià)者2的邊際價(jià)值在[0,100]區(qū)間線性增加.

圖3是社會(huì)效用受拍賣(mài)者邊際效益變化的影響.

Fig. 3 The revenue from various fix marginal valuations圖3 不同定值邊際價(jià)值對(duì)拍賣(mài)者收益的影響

從圖3中可以看出，隨著競(jìng)價(jià)者2的邊際效益的增加，定價(jià)拍賣(mài)和H-Clinching拍賣(mài)機(jī)制的收益都隨之增加.但是對(duì)于定價(jià)拍賣(mài)機(jī)制來(lái)說(shuō)，當(dāng)競(jìng)價(jià)者2的價(jià)值小于10時(shí)，由于價(jià)值過(guò)低的情況導(dǎo)致了機(jī)制無(wú)法收取其全部的預(yù)算，所以系統(tǒng)的收益隨著競(jìng)價(jià)者的邊際價(jià)值遞增而線性增加；但是當(dāng)邊際收益增加到10以后，此時(shí)機(jī)制會(huì)收取其全部的預(yù)算作為支付價(jià)格.對(duì)于H-Clinching來(lái)說(shuō)，由于其預(yù)算固定不變，Agent的價(jià)值函數(shù)會(huì)影響其棄掉的物品個(gè)數(shù).隨著競(jìng)價(jià)者2的邊際價(jià)值升高，丟棄的物品會(huì)越來(lái)越少，從而使得整個(gè)系統(tǒng)的收益值增加.當(dāng)Agent 2的邊際價(jià)值達(dá)到60時(shí)，其收益值大于系統(tǒng)分配給其最后一個(gè)物品所應(yīng)該付出的最高價(jià)格，則任何分配給競(jìng)價(jià)者2的物品都不會(huì)被棄掉，此時(shí)系統(tǒng)達(dá)到了最大收益.而對(duì)于VCG機(jī)制，根據(jù)機(jī)制的分配方式，其會(huì)將物品分配給對(duì)其最有價(jià)值的Agent.但是由于基于預(yù)算約束的VCG機(jī)制是選取了預(yù)算和價(jià)值函數(shù)的最小值作為其分配過(guò)程中的價(jià)值函數(shù).則由于競(jìng)價(jià)者2的存在，不會(huì)對(duì)競(jìng)價(jià)者1所獲得的價(jià)值產(chǎn)生任何影響，同理競(jìng)價(jià)者1也如此，則對(duì)于2個(gè)Agent所收取的價(jià)格都為0，此時(shí)系統(tǒng)的收益為0.

圖4展示了固定邊際效益值下不同邊際效益對(duì)拍賣(mài)效率的影響.

Fig. 4 Social welfare from various fix marginal valuations圖4 不同的定值邊際價(jià)值對(duì)拍賣(mài)效率的影響

從圖4可知，可以看出對(duì)于拍賣(mài)效率來(lái)說(shuō),VCG機(jī)制和H-Clinching 機(jī)制都遠(yuǎn)遠(yuǎn)高于定價(jià)拍賣(mài)機(jī)制，這是由于定價(jià)拍賣(mài)機(jī)制僅考慮最優(yōu)化其收益值，其總是將物品分配給首先達(dá)到最優(yōu)收益的Agent，導(dǎo)致其社會(huì)總福利非常低.在基于預(yù)算約束的VCG機(jī)制總是最優(yōu)化當(dāng)前社會(huì)福利，但由于預(yù)算約束，其按照Agent的收益函數(shù)和預(yù)算約束的最小值作為其新的收益函數(shù).競(jìng)價(jià)者1的收益值較高，從而其分配受到了預(yù)算約束的限制.但是當(dāng)競(jìng)價(jià)者2的收益值較小時(shí)，反而沒(méi)有受到預(yù)算約束限制，這導(dǎo)致了改進(jìn)的VCG機(jī)制將更多的資源分配給了價(jià)值較小的競(jìng)價(jià)者2.對(duì)于H-Clinching拍賣(mài)機(jī)制，其按照競(jìng)價(jià)者的收益函數(shù)從高到低丟棄物品，所以其社會(huì)總福利隨著邊際效益的增加而線性增加.

2) 邊際收益線性增加

在本實(shí)驗(yàn)中，設(shè)置競(jìng)價(jià)者1的邊際價(jià)值為100；Agent 2的邊際價(jià)值函數(shù)為：mv2=kx.此時(shí)，對(duì)于競(jìng)價(jià)者2，獲得新的物品會(huì)對(duì)其帶來(lái)更高的收益.2個(gè)競(jìng)價(jià)者對(duì)應(yīng)的收益函數(shù)為

(26)

設(shè)置2個(gè)競(jìng)價(jià)者的預(yù)算約束均為100，當(dāng)競(jìng)價(jià)者2的遞增邊際價(jià)值系數(shù)k∈[0,25]時(shí)，比較基于預(yù)算約束的VCG機(jī)制、定價(jià)拍賣(mài)機(jī)制和H-Clinching拍賣(mài)機(jī)制的收益和社會(huì)福利，如圖5、圖6所示.

從圖5中可以看出，隨著競(jìng)價(jià)者的邊際價(jià)值的增加，定價(jià)拍賣(mài)和H-Clinching機(jī)制的收益都會(huì)增加，但是當(dāng)邊際效益增加到一定程度時(shí)，由于預(yù)算約束的限制，2個(gè)拍賣(mài)機(jī)制的收益都趨于穩(wěn)定.當(dāng)邊際效益線性增加時(shí)，3個(gè)機(jī)制的社會(huì)總效用也產(chǎn)生了和固定邊際價(jià)值相同的結(jié)果.

Fig. 5 The revenue from various increasing marginal valuations圖5 不同的遞增邊際價(jià)值對(duì)拍賣(mài)者收益的影響

Fig. 6 Social welfare from various increasing marginal valuations圖6 不同的遞增邊際價(jià)值對(duì)拍賣(mài)效率的影響

3) 邊際收益線性遞減

下面我們將討論邊際價(jià)值遞減的情況下3個(gè)拍賣(mài)機(jī)制在收益和社會(huì)總效用2個(gè)指標(biāo)上的異同.在這個(gè)實(shí)驗(yàn)中，假設(shè)競(jìng)價(jià)者1的邊際價(jià)值為mv1=100; Agent2的邊際價(jià)值函數(shù)為

mv2=-kx+200.

(27)

2個(gè)競(jìng)價(jià)者對(duì)應(yīng)的收益函數(shù)為

(28)

設(shè)置2個(gè)競(jìng)價(jià)者的預(yù)算約束均為100，當(dāng)競(jìng)價(jià)者2的遞增邊際價(jià)值系數(shù)k∈[0,375]時(shí)，比較基于預(yù)算的VCG機(jī)制、定價(jià)拍賣(mài)機(jī)制和H-Clinching拍賣(mài)機(jī)制的收益和社會(huì)福利，如圖7、圖8所示.

Fig. 7 Revenue from various decreasing marginal valuations圖7 不同的遞減邊際價(jià)值對(duì)拍賣(mài)者收益的影響

Fig. 8 Social welfare from decreasing marginal valuations圖8 不同的遞增邊際價(jià)值對(duì)拍賣(mài)效率的影響

從圖7可以看出，H-Clinching拍賣(mài)機(jī)制和定價(jià)拍賣(mài)機(jī)制的收益仍遠(yuǎn)高于VCG機(jī)制.當(dāng)競(jìng)價(jià)者2的單位價(jià)值很高時(shí)，其收益較高.但是隨著k的增加，競(jìng)價(jià)者的收益值下降，由于H-Clinching拍賣(mài)的價(jià)格隨著物品的增加呈指數(shù)增長(zhǎng), 這是由于首先丟棄的物品是為拍賣(mài)商帶來(lái)最大利潤(rùn)的物品，所以收益值下降較快.在下降一段區(qū)間內(nèi)，收益呈平穩(wěn)趨勢(shì).而對(duì)于定價(jià)拍賣(mài)機(jī)制來(lái)說(shuō)，當(dāng)競(jìng)價(jià)者的邊際效益較高時(shí)，其收取競(jìng)價(jià)者全部預(yù)算作為支付;當(dāng)邊際價(jià)值降低到一定階段，定價(jià)拍賣(mài)機(jī)制的收益也會(huì)降低.VCG機(jī)制與固定邊際價(jià)值相同的原因，使得其收益一直為0.

從圖8可以看出，VCG機(jī)制和H-Clinching機(jī)制都可以達(dá)到較高的社會(huì)福利.k<12.5時(shí)，相比較VCG和定價(jià)拍賣(mài)來(lái)說(shuō)，H-Clinching機(jī)制最優(yōu)化的分配了全部物品.由于H-Clinching在邊際價(jià)值開(kāi)始降低時(shí)會(huì)放棄較多的物品，隨著競(jìng)價(jià)者的收益降低而趨于穩(wěn)定.而VCG機(jī)制中，由于競(jìng)價(jià)者1的收益受到其約束的限制，當(dāng)競(jìng)價(jià)2的邊際價(jià)值較高時(shí)，它會(huì)將更多的物品分配給競(jìng)價(jià)者2，為系統(tǒng)帶來(lái)更高的福利.隨著競(jìng)價(jià)者2的邊際價(jià)值降低，系統(tǒng)的福利降低.直到競(jìng)價(jià)者2的邊際價(jià)值與競(jìng)價(jià)者1的邊際價(jià)值持平或更低時(shí)，2個(gè)競(jìng)價(jià)者同樣受到其預(yù)算約束的限制，此時(shí)的社會(huì)總福利不再變化.

5.2 非擬線性價(jià)值函數(shù)對(duì)收益影響

在本節(jié)我們假設(shè)競(jìng)價(jià)者的邊際價(jià)值是先上升后下降，這種問(wèn)題在現(xiàn)實(shí)生活中是可能發(fā)生的，即當(dāng)競(jìng)價(jià)者拿到一定數(shù)量的播放時(shí)長(zhǎng)之前，每多獲得1 s所能帶來(lái)的利潤(rùn)增加，但是當(dāng)其獲得的時(shí)長(zhǎng)超過(guò)某一固定的廣告長(zhǎng)度之后，邊際價(jià)值會(huì)降低.這種設(shè)置的邊際效益可以形式化表示為

(29)

其價(jià)值函數(shù)可以表示為

v=∫mv(x)dx=

(30)

假設(shè)競(jìng)價(jià)者的預(yù)算約束均為100.競(jìng)價(jià)者1的邊際價(jià)值為固定值100，而競(jìng)價(jià)者2的邊際收益遵循上面的函數(shù)，且假設(shè)x*=5.當(dāng)k在[0,100]區(qū)間內(nèi)變化時(shí)對(duì)3個(gè)不同機(jī)制的收益以及社會(huì)效用產(chǎn)生的影響如圖9、圖10所示:

Fig. 9 Revenue from various non-qusi linear marginal valuations圖9 非線性邊際價(jià)值對(duì)拍賣(mài)者收益的影響

Fig. 10 Social welfare from various non-qusi linear marginal valuation圖10 非線性邊際價(jià)值對(duì)拍賣(mài)者收益的影響

從圖9可以看出，對(duì)于H-Clinching機(jī)制，當(dāng)競(jìng)價(jià)者的邊際價(jià)值較低(k<2)時(shí)，分配給競(jìng)價(jià)者2的物品被全部被丟棄；但是當(dāng)k持續(xù)增加(25之后迅速達(dá)到了收益最大化，其收益占定價(jià)拍賣(mài)機(jī)制的92%.而對(duì)于VCG機(jī)制的收益，與上節(jié)討論的內(nèi)容相同.

從圖10可以看出，VCG機(jī)制和H-Clinching機(jī)制的拍賣(mài)效率都遠(yuǎn)遠(yuǎn)高于定價(jià)拍賣(mài)機(jī)制，這是由于定價(jià)拍賣(mài)機(jī)制僅考慮最優(yōu)化其收益值，而不考慮社會(huì)效用，所以其總是將物品分配給首先達(dá)到最優(yōu)收益的Agent，導(dǎo)致其社會(huì)總福利非常低.在圖10中，H-Clinching機(jī)制產(chǎn)生的社會(huì)福利甚至超過(guò)了VCG機(jī)制，這是由于約束限制的存在，當(dāng)競(jìng)價(jià)者2的價(jià)值增加超過(guò)競(jìng)價(jià)者1時(shí)，在VCG機(jī)制中體現(xiàn)不出競(jìng)價(jià)者2的優(yōu)勢(shì)，從而將更多的物品分配給了價(jià)值較低的競(jìng)價(jià)者1.但是在H-Clinching機(jī)制中，價(jià)值更大的拍賣(mài)者的物品會(huì)被保留而不是丟棄，從而保證了總體社會(huì)效用.

5.3 預(yù)算約束對(duì)收益的影響

在本節(jié)中，我們將對(duì)2個(gè)競(jìng)價(jià)者預(yù)算約束值的分布不同對(duì)收益產(chǎn)生的影響進(jìn)行討論.為了減少其他因素對(duì)結(jié)果的影響，簡(jiǎn)單化設(shè)置:2個(gè)Agent的邊際收益10，競(jìng)價(jià)者1的預(yù)算約束固定為100，競(jìng)價(jià)者2的預(yù)算約束從20線性增加到120.圖11和圖12分別展示了3個(gè)機(jī)制的收益和社會(huì)效用值的關(guān)系.

Fig. 11 Revenue from various budget limits圖11 預(yù)算約束對(duì)拍賣(mài)者收益的影響

Fig. 12 Social welfare from various budget limits圖12 預(yù)算約束對(duì)拍賣(mài)效率的影響

從圖11可以看出隨著競(jìng)價(jià)者2預(yù)算約束的增加，定價(jià)拍賣(mài)機(jī)制和H-Clinching拍賣(mài)的收益都隨其增加.在[20, 80]的區(qū)間上，H-Clinching拍賣(mài)機(jī)制的收益增加較快，達(dá)到80之后線性增加.而VCG機(jī)制由于預(yù)算對(duì)其價(jià)值的受約束，使得2個(gè)競(jìng)拍者在彼此不存在的條件下都無(wú)法獲得更高的收益，其收益一直為0.從圖11可以看出，H-Clinching 拍賣(mài)機(jī)制在2個(gè)競(jìng)價(jià)者的預(yù)算相差較大時(shí)收益值較低，但是隨著2個(gè)Agent預(yù)算差距的減小，其收益增加較快，在達(dá)到一個(gè)穩(wěn)定狀態(tài)之后，整個(gè)系統(tǒng)的收益與定價(jià)拍賣(mài)機(jī)制一樣線性增加.

在社會(huì)效用方面，對(duì)于VCG機(jī)制預(yù)算的大小不影響其分配，其一直是處于最大化社會(huì)效用的分配方式.在H-Clinching機(jī)制中而隨著競(jìng)價(jià)者2預(yù)算的增加，其可以獲得更多的物品，由于競(jìng)價(jià)者2的邊際效益較高，則所有競(jìng)價(jià)者帶來(lái)的社會(huì)福利緩慢增加.直到競(jìng)價(jià)者2的預(yù)算約束增加到80時(shí)，2個(gè)競(jìng)價(jià)者所獲得的所有物品都不會(huì)被丟棄掉，此時(shí)達(dá)到了社會(huì)福利最大化.定價(jià)拍賣(mài)機(jī)制不考慮激勵(lì)相容和社會(huì)福利的性質(zhì)，使得社會(huì)福利在競(jìng)價(jià)者的預(yù)算約束增加時(shí)僅僅小幅增加.

6 結(jié) 論

本文提出了一種形式化的視頻廣告拍賣(mài)模型.特別地，和YouTube現(xiàn)在運(yùn)行的廣告系統(tǒng)不同，在該模型中可以有多個(gè)廣告同時(shí)在視頻播放前被播放.并且對(duì)于每一個(gè)參與競(jìng)拍的廣告商，他們擁有一些不同時(shí)長(zhǎng)的廣告，同時(shí)每個(gè)廣告都有一個(gè)對(duì)應(yīng)的私有價(jià)值信息.每一個(gè)參與競(jìng)拍的Agent對(duì)于其要支付的價(jià)格都有一個(gè)公共信息的預(yù)算約束限制.最終拍賣(mài)會(huì)為每一個(gè)Agent分配一個(gè)播放時(shí)長(zhǎng)用以播放其廣告，確定所有廣告的播放次序和為每個(gè)廣告展示確定一個(gè)支付價(jià)格.這是一個(gè)基于約束限制的異質(zhì)多物品拍賣(mài)問(wèn)題.之前的研究已經(jīng)指出，對(duì)于公共信息的預(yù)算約束限制的多物品拍賣(mài)問(wèn)題，不存在著同時(shí)滿足激勵(lì)相容、個(gè)體理性和有效性性質(zhì)的機(jī)制.且之前的研究工作基本上都是以邊際價(jià)值非增為條件展開(kāi)的.所以，在不限制價(jià)值的分布條件下，提出了一種IC、IR和無(wú)正向傳播的機(jī)制, 并且通過(guò)推導(dǎo)證明給出了這個(gè)激勵(lì)相容機(jī)制的收益的下限.最后，本文通過(guò)對(duì)3種不同的線性收益函數(shù)和一種非線性收益函數(shù)的實(shí)驗(yàn)分析，對(duì)比與能帶來(lái)最大收益的定價(jià)拍賣(mài)和改進(jìn)的VCG機(jī)制，證明了本文提出的機(jī)制在收益和社會(huì)效用指標(biāo)上的有效性,并分析了不同的預(yù)算約束對(duì)3種機(jī)制的收益和社會(huì)效用的影響.

本文的工作是首次將在線視頻廣告拍賣(mài)與預(yù)算約束限制結(jié)合研究，對(duì)于未來(lái)還有很多方向可以研究.首先，在確定性機(jī)制中，為了保證效用最大化，將Agent所獲得的多余物品丟棄，而且，在隨機(jī)機(jī)制中，是利用均勻分布的方法對(duì)所有的Agent進(jìn)行排序.這保證了系統(tǒng)的激勵(lì)相容的性質(zhì)，但是可能會(huì)降低系統(tǒng)的效率.所以未來(lái)可以對(duì)這種次序分配進(jìn)行研究，在保證激勵(lì)相容的條件下，將被丟棄的物品重新分配，并且找到更合理的次序分配方式，提高系統(tǒng)的效率.另外對(duì)于機(jī)制的收益進(jìn)行分析的部分，本文僅考慮了邊際價(jià)值呈線性變化的條件下的收益，接下來(lái)希望能對(duì)單位估值的一般分布情況進(jìn)行分析，得出一般性的結(jié)果.未來(lái)我們也希望對(duì)非硬性預(yù)算約束限制進(jìn)行研究，即Agent的支付可以在不超過(guò)非硬預(yù)算的區(qū)間內(nèi)進(jìn)行浮動(dòng)，這將是一個(gè)非常有挑戰(zhàn)性的工作.

[1]Braude N. Global entertainment and media outlook 2015-2019: Hot topics: PwC[R]. London: Price Waterhouse and Coopers & Lybrand, 2014

[2]Kumar S. Evolution of Web advertising[M] //Optimization Issues in Web and Mobile Advertising. Berlin: Springer International Publishing, 2016

[3]Varian H R. Online ad auctions[J]. American Economic Review, 2009, 99(2): 430-34

[4]Edelman B, Schwarz M. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords[J]. American Economic Review, 2015, 97(1): 242-259

[5]Díaz J, Giotis I, Kirousis L, et al. On the stability of generalized second price auctions with budgets[C] //Proc of Latin American Symp on Theoretical Informatics. Berlin: Springer, 2014: 695-706

[6]Borgs C, Chayes J, Immorlica N, et al. Multi-unit auctions with budget-constrained bidders[C] //Proc of the 6th ACM Conf on Electronic Commerce. New York: ACM, 2005: 44-51

[7]Ausubel L M. Efficient ascending-bid auction for multiple objects[J]. American Economic Review, 2004, 94(5): 1452-1475

[8]Dobzinski S, Lavi R, Nisan N. Multi-unit auctions with budget limits[J]. Games and Economic Behavior, 2012, 74(2): 486-503

[9]Colini-Baldeschi R, Henzinger M, Leonardi S, et al. On multiple keyword sponsored search auctions with budgets[M] //Automata, Languages, and Programming. Berlin: Springer, 2012: 1-12

[10]Goel G, Mirrokni V, Leme R P. Polyhedral clinching auctions and the AdWords polytope[C] //Proc of the 44th ACM Symp on Theory of Computing. New York: ACM, 2012: 107-122

[11]Goel G, Mirrokni V, Paes L R. Clinching auctions beyond hard budget constraints[C] //Proc of the 15th ACM Conf on Economics and Computation. New York: ACM, 2014: 167-184

[12]Lavi R, May M. A note on the incompatibility of strategy-proofness and pareto-optimality in quasi-linear settings with public budgets[J]. Economics Letters, 2012, 115(1): 100-103

[13]Sakurai Y, Saito Y, Iwasaki A, et al. Beyond quasi-linear utility: Strategy/false-name-proof multi-unit auction protocols[C] //Proc of Web Intelligence and Intelligent Agent Technology. New York: ACM, 2008: 417-423

[14]Bhattacharya S, Conitzer V, Munagala K, et al. Incentive compatible budget elicitation in multi-unit auctions[J]. Computer Science, 2009, 107(5): 1472-1478

[15]Itai A, Mark B, Avinatan H, et al. Position auctions with budgets: Existence and uniqueness[J]. The BE Journal of Theoretical Economics, 2010, 10(1): 1-32

[16]Wu Fan, Zheng Zhenzhe. Game theory based spectrum dynamic management[J]. Journal of Computer Research and Development, 2016, 53(1): 38-52 (in Chinese)(吳帆, 鄭臻哲. 基于博弈論的頻譜動(dòng)態(tài)管理研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(1): 38-52)

[17]Poole L D, Mackworth A. Artificial Intelligence Foundations of Computational Agents[M]. Translated by Dong Hongbin, et al. Beijing: China Machine Press, 2015 (in Chinese)(Poole L D, Mackworth A. 人工智能：計(jì)算Agent基礎(chǔ)[M]. 董紅斌等譯, 北京: 機(jī)械工業(yè)出版社, 2015)

Yang Xue, born in 1986. PhD candidate in Harbin Engineering University. Her main research interests include intelligent optimization algorithm and auction online advertising.

Dong Hongbin, born in 1963. Professor and PhD supervisor in Harbin Engineering University. His main research interests include multi-agent system and machine learning.

Teng Xuyang, born in 1987. PhD candidate in Harbin Engineering University. His main research interests include machine learning and intelligent information processing.

Budget Constraint Auction Mechanism for Online Video Advertisement

Yang Xue, Dong Hongbin, and Teng Xuyang

(CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin150001)

As an important segment in IT industry, online advertising brings huge revenue to publishers. Most of the video advertisement auction are traded as keyword action. Due to the selling object are divisible in video ad auction, these two issues are two internal different problems. Hence, we formulate a novel market model to allocate video advertisements in a playing order as a pre-roll ads sequence. In this model each bidder holds various ads with diverse durations, private valuations and public budget limit. It has been proved that there is no individual rationality, positive transfer and Pareto optimal deterministic mechanism for private budget assumption case. Hence for this heterogeneous commodities allocation problem with budget constrain, we develop a randomize mechanism based on “Clinching auction” frame. In particular, we study no limited valuation distribution setting and show that this mechanism is incentive compatible, individually ration and no positive transfer. Furthermore, compared with the fixed price revenue optimize auction, our mechanism has lower bound revenue based on a dominance parameter which measures the size of the budget of a single agent relative to the maximum revenue. And the availability on revenue and efficiency of H-Clinching auction has been proved by several experiments.

multi-agent system; auction mechanism design; online video advertisement; budget constraints; non-linear marginal valuation

2016-06-27；

2016-10-10

國(guó)家自然科學(xué)基金項(xiàng)目(61472095，61502116，41306086)；黑龍江省教育廳智能教育與信息工程重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金項(xiàng)目 This work was supported by the National Natural Science Foundation of China (61472095, 61502116, 41306086) and the Open Foundation of the Heilongjiang Provincial Education Department Key Laboratory of Intelligent Education and Information Engineering.

董紅斌(donghongbin@hrbeu.edu.cn)

TP301