多Agent兩標的序貫拍賣最優排序策略研究

安陽師范學院 趙 月

多Agent兩標的序貫拍賣最優排序策略研究

安陽師范學院 趙 月

序貫拍賣是多Agent系統中資源分配的一項主要機制。考慮現實拍賣環境，放寬基準拍賣模型假設，提出一個公開標的信息的多Agent兩標的序貫拍賣模型，分別給出買家Agent在FPSA、SPSA拍賣規則下的競價策略。根據兩標的間不同關系，分析了買家Agent利潤和賣家Agent收益的變化情況，由此得到兩標的拍賣的最優排序策略。

多Agent序貫拍賣；兩標的；公開信息；最優排序策略

多Agent技術在分布式、自由交互、動態環境的系統中具有相當優勢。當前，基于多Agent的電子拍賣理論得到眾多學者的研究。在多Agent系統中，序貫拍賣變得越來越重要，已成為資源分配的一項主要機制[1]。

Shaheen Fatima在一個買家預算受限、非完全信息環境下的拍賣模型中[2]，分析了買家Agent在第一、第二價格拍賣規則下的均衡競價策略；Edith在文獻[3]中指出為到達收益最大化（revenue-maximizing），賣家Agent應采取的最優拍賣順序，但這是一個標的只具有私人價值的拍賣模型；Giuseppe給出兩個在線序貫拍賣的模型[4]，并分別給出賣家Agent的最優起拍價，但這兩個序貫拍賣模型的假設過于嚴格，并沒有考慮標的間的關系，不符合在線拍賣的實際環境。

本文放寬基準拍賣模型假設，提出一個多Agent兩標的序貫拍賣模型：D_Riapcv(Double Bids Revealed Information Auction with Private and Common Value)，設定兩標的間存在互相影響的關聯因子，假設買家Agent不受限制可以參加兩次拍賣，分析了兩標的之間的關系對買家Agent的利潤及競價策略和賣家Agent的收益有不同的影響?；趦蓸说拈g的關系，給出拍賣員為使賣家Agent為獲得較高收益的最優標的拍賣排序策略。

1.拍賣模型

兩標的D_Riapcv模型定義為M=。其中：

●seller表示賣家Agent的數量，這里研究的是一對多模型，所以seller=1。

●buyer表示買家Agent的數量，buyer=1，2，…n個風險中性的買家Agent。

●R表示買家Agent在不同拍賣規則下的競價策略，本模型只考慮兩種拍賣規則：FPSA和SPSA，取R={FPSA，SPSA}。

●V={VA，VB}，分別表示拍賣中的第一個標的A和第二個標的B的共同價值。

●c={cA，cB}，分別表示標的A和標的B的私人價值。

●Y={YA，YB}表示拍賣員公開兩個標的的相關信息。

●a表示兩個標的之間的關系，取值{互補，替代，無關性}。

互補、替代的定義如下：

買家Agent i的個人偏好決定標的私人價值的大小，取值獨立于信息Y的公開和外部拍賣環境的影響。對標的共同價值的估值則會受到公開信息Y的影響，記二者之間的關系為：

類似于單標的拍賣，為使拍賣員能把買家Agent按照標的的競價能力排序，須引入下面假設和引理。

據此，買家Agent i可以把共同價值和私人價值二維取值轉化成盈余(surplus)的形式把競價能力表現出來，拍賣員按照每個買家Agent的盈余排序，決定誰能獲得標的。

兩標的模型考慮以下兩點：第一，允許每個買家Agent不受限制的參加兩次拍賣。第二，買賣雙方都不同程度受到標的間不同關系帶來的影響。

假設3：拍賣開始前每個買家Agent分別收到兩個標的間私人價值的關聯因子a。a在買家Agent之間取獨立同分布，取值范圍是[αl,αh]。

允許所有買家Agent不受限制地參加兩個標的的拍賣，肯定存在某一個買家同時獲得兩個標的的可能，設買家Agent i同時贏得了兩個標的。

則兩個標的對于贏家Agent i的私人價值會因為存在關聯因子a而變為：

2.買家Agent的競價策略

兩個標的之間存在三種關系：互補、替代、無關系。如果一個買家同時獲得兩個標的，他的利潤在三種不同關系下是不一樣的，所以每個買家在標的存在不同關系時的競價策略也是不一樣的。

（1）無關系

如果兩個標的之間不存在任何關系，即a=0，買家Agent i對第一個標的提交的競拍價格、采用的競價策略，不會對第二個標的的競價策略和利潤分析產生任何影響；同樣，是否贏得第二個標的，以及在第二個標的中獲益多少，也不會對第一個標的的競價策略產生影響。這種情況下，買家的競價策略完全可以按照單標的競價策略[5]來競拍。如不贅述。

（2）互補關系

如果兩個標的存在互補關系，即a>0。假設買家Agent i只贏得標的A，獲得利潤PA；如果他只贏得標的B，獲得利潤PB；如果他同時贏得兩個標的，將獲得利潤為P，則P>PA+PB。

所以每一個買家Agent在參加第一個標的A拍賣時，都會考慮參加第二個標的B的拍賣，并計算從中可能獲得的利潤，綜合分析后才提交第一個標的的競價；

在給出第一個競價策略函數前，先來計算買家Agent可能從第二個拍賣中獲得的利潤。PB是第二個標的贏家的利潤：

在第二個拍賣開始前，每一個買家Agent都有可能成為第二個標的的贏家，所以每個買家Agent獲得第二個標的的機率是相同的。

1）設拍賣員首先拍賣標的A，第二個拍賣標的B。

則FPSA規則中買家Agent i對標的A的競價策略函數：

標的B拍賣是最后一個拍賣，沒有從后面的拍賣中獲利的可能，這時候買家Agent對標的B的競價策略同單標的拍賣時的競價策略一樣。所以這里只給出FPSA、SPSA兩個拍賣規則中買家Agent第一個標的的競價策略函數。第二個標的競價的策略請參考單標的拍賣競價策略[5]。

2）如果拍賣員首先拍賣的是標的B，再拍賣A，則FPSA、SPSA兩個拍賣規則中買家Agent的競價策略分析同上。

（3）替代關系

系統可以接受兩種相同格式不同子系統的并行控制信號來完成對機器人內部與外部的并行控制，信號分別來自于機器人語言識別系統和遙控.計算機與聲像采集、傳輸系統結合使得操作者獲得較強的臨場感.

如果兩個標的之間存在替代關系，那么每一個買家可以根據自己的需要來選擇是獲得標的A，還是獲得標的B。顯然這種情況下的競價策略和單標的拍賣時一樣。不管拍賣員先拍賣哪個標的，對買家Agent的策略都沒有影響。但在第二個標的拍賣時，買家Agent的數量不是n，而是（n-1），因為第一個標的的贏家是不會參加第二個標的拍賣。

3.買家Agent利潤和賣家Agent收益

對于買家Agent的利潤和賣家Agent的收益分析也從兩個標的間的三種關系入手，分開討論。

（1）無關系

由其競價策略可知，我們完全可以按照兩個單標的模型中的拍賣進行處理。是否獲得第一個標的，并不影響買家Agent參加第二個標的的拍賣；同樣，由于每一個買家Agent不知道是否參加第二個標的拍賣并能獲得勝利，所以買家在提交第一個標的競價策略時，并不會設想第二個標的拍賣的情況。

所以，在D_Riapcv拍賣模型中，如果兩標的之間沒有任何關系，買家Agent的利潤和賣家Agent的收益和單標的拍賣模型[5]中情況一樣。

（2）互補關系

標的間屬于互補關系，如果同時獲得兩個標的，買家Agent將會有更大的利潤。不失一般性，假設所有的買家都將參加第二個標的拍賣。買家Agent從第二個拍賣中期望獲得利潤的機會是均等的。

同單標的模型一樣，本章的D_Riapcv模型也符合對稱性假設，滿足“收益均衡”定理[6]。買家Agent的利潤和賣家Agent的收益在FPSA、SPSA兩個規則中都是相等的。

1）設拍賣員首先拍賣標的A，第二個拍賣標的B。則標的A拍賣結束，贏家Agent i的利潤是：

2）拍賣員首先拍賣標的B，第二個拍賣標的A。則標的B的獲勝者Agent i的利潤（見公式10）是：

（3）替代關系

如果兩個標的間是替代關系，買家Agent只會二選一進行競拍。這種情況和標的間屬于無關系時基本一樣。假設拍賣第一個標的有n個買家Agent參加，則第二個標的最多只有（n-1）個買家，兩個標的拍賣中的買家Agent利潤和賣家Agent收益分析等同于單標的模型的分析。

4.標的拍賣的最優排序策略

拍賣員通過買家Agent利潤的順序統計才能決定兩個標的拍賣的順序。如果拍賣員先拍賣標的A，后拍賣標的B，稱為策略1；如果拍賣員先拍賣標的B，后拍賣標的A，稱為策略2。首先引入順序統計離散度的定義。

定義：對于兩個標的A和B，如果下面條件成立，則稱標的A的利潤順序統計離散度大于標的B的利潤順序統計離散度。否則，則稱標的A的利潤順序統計離散度小于標的B的利潤順序統計離散度。

假設4：在下面求解兩標的最優拍賣排序策略時，假設標的A的利潤順序統計離散度大于標的B的利潤順序統計離散度。

兩標的間存在不同關系，即ai取不同值時，拍賣員采取的排序策略會不同。下面就從ai取不同的值來分別討論標的拍賣的排序策略。

若式（20）成立，說明這時候策略1和策略2使賣家Agent獲得的收益一樣大。

綜上分析，若式（18）成立，先拍賣標的B，后拍賣標的A，即按照買家Agent利潤順序統計離散度遞增拍賣標的，能使賣家Agent獲得較大的收益。若式（20）成立，先拍賣標的A，后拍賣標的B，即按照買家Agent利潤順序統計離散度遞減拍賣標的，能使賣家Agent獲得較大的收益。若式（22）成立，則兩標的的拍賣順序對賣家Agent的收益沒有影響。

5.結語

本文構造了一個多Agent兩標的序貫拍賣模型D_Riapcv，考慮兩標的之間存在不同關系，分別給出買家Agent在FPSA、SPSA拍賣規則下的競價策略。分析了兩標的拍賣的過程中買家Agent的利潤和賣家Agent的收益。最后，求解出兩標的間的關聯因子取不同值時，拍賣員拍賣兩標的的最優排序策略。

事實上，現實中拍賣雙方面對的問題會更加復雜，例如每次拍賣買家Agent的個人喜好是不盡相同的，那么賣家Agent應如何根據買家Agent的特點有針對性的公開標的屬性信息；如果上一個標的拍賣的結果會影響參與下一場拍賣的買家Agent對標的的估價，賣家Agent又該采取何種拍賣策略以提高期望收益等問題；這些都將作為我們今后要考慮的問題。

[1]Giuseppe Lopomo,Leslie M.Marx and Peng Sun,Bidder collusion at first-price auctions[J].Review of Economic Design2011,15(3):177-211.

[2]柴玉梅,趙月,王黎明.基于信息相似度分類的多agent公開信息拍賣模型[J].計算機應用研究,2009,26(12):4532-4535.

[3]Milgrom.P.R,Weber,R.J.A Theory of Auctions and Competitive Bidding[J].Econometrica,1982,50:1089-1122.

趙月（1982—），男，河南安陽人，碩士，現供職于安陽師范學院，主要研究方向：分布式人工智能。