分布式語義自動協(xié)商與博弈機制研究

何雨青 朱俊武 李開榮

摘? ?要：文章在語義集成中引入了協(xié)商—博弈機制。各個Agents由于對領域的認知程度不同，因此，他們構建本體的“可信度”也是不同的。本體“可信度”越高，基于本體語義進行的檢索準確率就越高。注意到每個Agent構建的本體與最終本體之間相似度可以看作Agent的收益，Agents之間如果通過協(xié)商與博弈來形成均衡，那么這個均衡就是所有Agents最能接受的結果，即“可信度”最高的本體。因此，模擬Agents之間的協(xié)商與博弈，構建更“可信”的本體，是完全可行的。

關鍵詞：機制設計;協(xié)商—博弈;本體論

當兩個本體之間存在語義關聯(lián)時，就可以通過本體映射來將源本體的實例映射到目標本體，從而解決異構本體的共享和重用問題[1]。現(xiàn)有的本體映射工作并不能適用于那些規(guī)模較大的本體通信與共享的情況。本文擬設計一種新穎的本體合并方法，即把多個同主題領域的本體相結合，從而構建一個規(guī)模更大的語義共享空間。那就是本體構建者對領域知識的認知程度不同。由于認知程度較低的Agent所構建出的本體可信度不高，基于該現(xiàn)狀，在設計的本體合并方法基礎上增加“可信度”這樣一個概念是必要的。

1? ? Agent協(xié)商系統(tǒng)

在Agent協(xié)商與博弈的情形下，大多數(shù)學者沒有考慮到一個事實，那就是Agent之間的知識共享[2]。知識共享在協(xié)商—博弈系統(tǒng)中是非常有必要的，在協(xié)商階段進行知識共享，可以更有效地達成一致，從而進行下一個階段，即博弈階段。在博弈階段，知識共享能幫助博弈雙方根據(jù)對方的知識對自己的策略進行改良，從而使得自己的收益盡可能大。

現(xiàn)有的Agent協(xié)商系統(tǒng)中，協(xié)商環(huán)境復雜、動態(tài)，Agent存在異構的可能。Agent對于特定的協(xié)議和領域具有依賴性，因此，沒有辦法讓協(xié)議與領域無關[3]。選擇適當?shù)男问交ぞ呙枋鰠f(xié)商Agent的交互和規(guī)則問題，使得協(xié)商Agent不依賴于特定的協(xié)商和博弈機制，如何做到領域無關是極具研究價值的問題[4]。

2? ? 協(xié)商—博弈本體定義

協(xié)商和博弈本體（Negotiation/Game Ontology，NO/GO）分別對協(xié)商領域和博弈領域進行建模，提供了Agent互相之間可以進行共享的協(xié)商或博弈知識庫，使得Agent與領域知識、協(xié)商/博弈協(xié)議相分離，能夠在加入?yún)f(xié)商或博弈時自動獲取該領域的知識本體并通過自身的推理機制解析協(xié)商/博弈對象、協(xié)商/博弈規(guī)則等通信信息從而更適用于語義Web的環(huán)境，能夠參與任何領域的協(xié)商/博弈活動。

描述邏輯（Description Logic）是基于對象的知識表示的形式化，建立在概念和關系之上，具有很強的表達能力與可判定性。基于描述邏輯，將本體定義為一個二元組，即O=（Tbox，Abox），其中，Tbox=（C，R，P）包含內(nèi)涵知識用于描述概念的一般性質(zhì)，（C，R，P）分別表示概念（concept）、角色（role）和屬性（property）;Abox包含外延知識（又稱斷言知識）用于某個特定個體。

構建了如下的協(xié)商本體和博弈本體，如圖1—2所示。

協(xié)商Agent根據(jù)分工的不同可分為negotiation participant和negotiation host，兩者分別表示協(xié)商的參與者以及對協(xié)商過程進行監(jiān)督的主持者。其中，對協(xié)商過程進行監(jiān)督的主持者又可根據(jù)職責分為3種類型：validator用于判定各個規(guī)則是否合理、updater用于更新反饋結果、agreement make根據(jù)終態(tài)時得到最終的協(xié)商結果。協(xié)商中有3種狀態(tài)，即初始狀態(tài)、中間狀態(tài)和最終狀態(tài);當?shù)竭_最終狀態(tài)時，Agent達成一致（agreement）或矛盾（conflict），協(xié)商結束。這樣一個由多種協(xié)商Agent進行的，從初始狀態(tài)到最終狀態(tài)的過程，就是一個完整的協(xié)商過程。

與協(xié)商本體類似，博弈的參與者有兩類，分別是game host和game participant;策略是博弈參與者在進行博弈時可選擇的行動集合，而策略的選擇又依賴于外界環(huán)境和參與者所掌握的信息的影響。博弈規(guī)則是指博弈的約束，博弈規(guī)則指導著博弈的進行。收益是指參與者在采取策略后所得到的利益。

3? ? 本體語義支撐的協(xié)商-博弈機制

自動協(xié)商的靜態(tài)成分可以用一組協(xié)議來表示〈Pad，Pal，Pag〉，其中，Pad是規(guī)范如何進入（admission）協(xié)商的協(xié)議，Pal是協(xié)商進行時參與者如何交互（alternate）的協(xié)議，Pag是交互完成時，協(xié)商一致（agreement）如何生成的協(xié)議。

其中，對于任何的協(xié)議，都可以用元組〈Ag，Ac，W， w0，T，L，u〉進行刻畫。其中，Ag={α1，…αn}是協(xié)議的使用者（Agent）的集合;Ac={Ac1，…Acn}是使用者的行動（Action）的集合，其中Aci是αi的行動結合;W是使用本協(xié)議交互過程中，可能達到的狀態(tài)的集合;w0是初始的狀態(tài)，T是結束時可能的終態(tài)集合;L是一組函數(shù)，其中，函數(shù)Li：W+＼T→2Aci被稱為αi在特定狀態(tài)下的合法行動集合，規(guī)定了αi在某一非終狀態(tài)下能采取的交互行動。函數(shù)u：W×A1×…×An→W被稱為狀態(tài)更新函數(shù)，決定了在某個狀態(tài)下，Agent采取一定的行動，狀態(tài)將如何遷移。至此，本文定義了協(xié)商協(xié)議的統(tǒng)一理論數(shù)學模型。

但是此模型應用在開放市場協(xié)商環(huán)境下卻有相當大的局限性，比如協(xié)議中的行動集合、狀態(tài)集合可能非常龐大甚至是無限集。因此，狀態(tài)遷移函數(shù)也有可能難以表示。這意味著很難對協(xié)商的領域知識進行擴充，使得協(xié)商協(xié)議的應用場景受限，可重用性下降。而且在現(xiàn)實的協(xié)商環(huán)境中，存在多個協(xié)議負責約束不同的交互，遵守協(xié)議存在時序關系，而此數(shù)學模型難以表達協(xié)議之間的層級、執(zhí)行順序關系，這對自動協(xié)商程序的編寫造成了極大的困難。

而使用共享協(xié)商本體則可以很好地解決上述問題，對開放環(huán)境下的自動協(xié)商過程進行抽象分析，一般而言，自動協(xié)商可以被抽象成如下3個階段：（1）協(xié)商申請階段。（2）協(xié)商交互階段。（3）協(xié)商一致生成階段。

本體語義支撐的協(xié)商機制可用上述定義的協(xié)商本體進行描述，具體如下。

3.1? 協(xié)商申請階段

協(xié)商申請階段可以被認為是有意愿參加本次協(xié)商的Agent和協(xié)商的主持者Host之間的溝通，具體體現(xiàn)為以下幾點。

（1）Agent向協(xié)商主持者Host提交參加本次協(xié)商的申請。（2）Host收到申請后，向該Agent發(fā)送共享協(xié)商本體（包括：角色、協(xié)商協(xié)議等）。（3）Agent收到貢獻給協(xié)商本體，對本體進行解析，向Host發(fā)送信任狀，表明自己是否可以理解遵循協(xié)商本體所描述的協(xié)商規(guī)則。（4）Host收到Agent的信任狀，根據(jù)信任狀的結果判斷是否允許該Agent參加本次協(xié)商，并將判決結果發(fā)送給Agent。（5）Agent收到Host的判決結果，如不同意，則離開本次協(xié)商;如同意，則進入本次協(xié)商，等待協(xié)商進入下一階段。

具體的交互流程如圖3所示。

3.2? 協(xié)商交互階段

在參與者通過協(xié)商申請階段后，Host會根據(jù)start_rule判定協(xié)商何時進入?yún)f(xié)商交互階段。協(xié)商交互階段本質(zhì)上是參與者之間、參與者與Host之間，Host內(nèi)部各功能Agent之間，根據(jù)協(xié)商協(xié)議進行交互的過程。這樣的過程可以抽象成如下6個基本步驟。

（1）Host的子Agent—terminal_checker會根據(jù)terminal_rule判斷當前狀態(tài)下協(xié)商是否達到了最終狀態(tài)，如果是，則進入?yún)f(xié)商過程的第3階段（協(xié)商一致生成狀態(tài)），否則進入步驟2。

（2）Host根據(jù)voice_rule判定此時哪些協(xié)商參與者可以發(fā)言，協(xié)商參與者根據(jù)proposal_rule計算自己此時可以提出proposal。

（3）協(xié)商參與者向Host提交自己的proposal，Host只會接受在步驟2中判定的可以發(fā)言的協(xié)商者的消息。

（4）Host將接收到的proposal提交給子功能Agent—validator，validator根據(jù)proposal_rule判定各個參與者提交的proposal是否合理，如果不合理，則validator根據(jù)規(guī)則隨機生成一個proposal并發(fā)送給Host，并重復步驟4。如果合理，則把proposal提交給Host的子功能Agent—updater，進入步驟5。

（5）updater收到validator發(fā)送的proposal，根據(jù)proposal對本次協(xié)商的各元素進行信息更新，并將更新結果反饋給Host。

（6）Host收到來自updater的更新反饋結果，Host根據(jù)inform_rule判斷更新結果的哪些部分應該告訴哪些協(xié)商參與者，并告知相應的參與者，進入步驟1。

具體協(xié)商流程如圖4所示。

3.3? ?協(xié)商一致生成階段

當Host的子功能Agent—terminal_checker監(jiān)測到協(xié)商當前達到了終態(tài)時，協(xié)商從交互階段進入到協(xié)商一致生成階段。在此階段，Host的子功能Agent—agreement_maker根據(jù)終態(tài)時的proposal情況得到最終的協(xié)商結果（包括一致agreement和不一致confict兩方面）。并將信息反饋給Host，由Host根據(jù)inform_rule告知協(xié)商的參與者。

4? ? 結語

本文設計了分布式語義自動協(xié)商與博弈機制，能有效提高效率。但是，這仍是非常復雜的問題，僅設計出機制是不夠的。后續(xù)還將對該機制進行求解。

[參考文獻]

[1]KALFOGLOU Y，SCHORLEMMER M.Ontology mapping：the state of the art[J].Knowledge Engineering Review，2003（1）：1-31.

[2]NOY N.Semantic integration：a survey of ontology-based approaches[J].Sigmod Record，2004（4）：65-70.

[3]唐杰，梁邦勇，李涓子，等.語義Web中的本體自動映射[J].計算機學報，2006（11）：1956-1976.

[4]FRIDMAN N，MUSEN M A.Prompt：algorithm and tool for automated ontology merging and alignment[C].Austin：Proceedings of Seventeenth National Conference on Artificial Intelligence（AAAI—2000），2000.