基于Agent的兩階段一對多談判模型研究

[摘 要] 本文提出了一種基于Agent的兩階段一對多談判模型。與單階段一對多并行談判模型相比，這種模型在談判第一階段不主動淘汰賣方，賣方不會因為在談判初期采取較為的保守策略而過早失去繼續(xù)談判的機(jī)會，同時也增加了買方最終得到更好成交價格的機(jī)會。本文還提出了一種改進(jìn)的基于合作可能度的淘汰談判機(jī)制，在談判模型的第二階段逐步淘汰合作可能度小的賣方，達(dá)到減少談判成本的目的。

[關(guān)鍵詞] 基于Agent的一對多談判;兩階段談判;談判模型;談判策略

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2009 . 21 . 027

[中圖分類號]F724.6;F407.67[文獻(xiàn)標(biāo)識碼]A[文章編號]1673 - 0194(2009)21 - 0086 - 03

1引言

基于Agent的談判是用Agent這一人工智能領(lǐng)域的新興手段來實現(xiàn)談判的智能化和自動化的技術(shù)[1]。按照談判過程中參與談判的買賣各方Agent數(shù)量的不同，可以將談判分為一對一談判、一對多談判和多對多談判等。其中，一對多談判是指由一個買方Agent就同一份合同同時與多個賣方Agent進(jìn)行談判，在綜合所有的談判結(jié)果后選擇其中的一個賣方Agent達(dá)成協(xié)議的過程。

早期的自動談判系統(tǒng)多采用拍賣的形式實現(xiàn)，買方在拍賣過程中不提出反報價，從多個賣方Agent的報價方案中選擇最優(yōu)的進(jìn)行合作[2-3]。這種方法在形式上簡單，但對于賣方來說明顯不公平，買方也無法通過合理運(yùn)用談判策略來得到更優(yōu)的報價。后來的研究者提出將一對多談判轉(zhuǎn)化為多個并行的一對一談判，通過某種協(xié)調(diào)控制策略來協(xié)調(diào)處理各談判的結(jié)果[4-7]。這樣可以產(chǎn)生比較理想的談判結(jié)果，但對多個并行談判進(jìn)行協(xié)調(diào)必然導(dǎo)致額外的通訊和協(xié)調(diào)成本的產(chǎn)生。有人提出了兩階段式的一對多談判模型，將談判分成預(yù)談判和競標(biāo)兩個階段來進(jìn)行[8]，但這種模型和早期的競標(biāo)模型一樣，存在顯著的談判公平性缺失的問題。針對這些模型中存在的問題，本文提出一種兩階段的談判模型，在談判的第二階段逐步淘汰賣方Agent來減少參與談判的Agent數(shù)量，以達(dá)到減少談判成本的目標(biāo)。

2兩階段一對多談判

兩階段一對多談判是在現(xiàn)有一對多并行談判模式基礎(chǔ)上的改進(jìn)，將談判分成了兩個階段:第一階段為預(yù)談判階段，在這個階段中，買賣各方正常進(jìn)行有反報價的談判，但是不淘汰賣方;在第二階段，買方根據(jù)談判進(jìn)行的情況，根據(jù)一定標(biāo)準(zhǔn)對賣方進(jìn)行淘汰。將談判分為兩個階段有以下優(yōu)點:

(1) 保證了談判的公平性。在談判的第一階段，賣方不會因為報價策略的保守而導(dǎo)致被過早淘汰，有充分的機(jī)會來通過買方的反報價來判斷買方的意圖，及時調(diào)整自身的報價策略。

(2) 降低了談判的總體成本。在談判的第二階段，買方根據(jù)談判情況淘汰成交可能性低的賣方，減少了通訊和協(xié)調(diào)成本的浪費(fèi)，從總體上降低了談判成本。

3改進(jìn)的基于合作可能度的淘汰談判機(jī)制

談判第二階段的核心問題是淘汰標(biāo)準(zhǔn)的選擇。李冉冉 等提出了合作可能度的概念和基于合作可能度的淘汰賣方Agent的談判機(jī)制[9]，能夠得到較為理想的淘汰效果。但該談判機(jī)制存在兩個缺陷:

(1) 合作可能度的計算依賴于對最終成交價格的預(yù)測，其準(zhǔn)確程度是隨著談判輪次的增加而逐漸增大的。始終用一個固定的闕值來作為淘汰的標(biāo)準(zhǔn)，合理性較差。

(2) 用合作可能度作為權(quán)重來計算統(tǒng)一的反報價，這個反報價必然低于各Agent單獨(dú)計算的反報價中的最低值。對買方而言，這顯然不是最優(yōu)的選擇。

針對以上模型存在的問題，本文提出了一種改進(jìn)的基于合作可能度的淘汰談判機(jī)制。它在原有機(jī)制的基礎(chǔ)上做出了兩點改進(jìn):

(1) 采用隨著輪數(shù)t變化的函數(shù)σ(t)作為淘汰的判斷標(biāo)準(zhǔn)，其計算方式如下:

σ(t) = σmin + (σmin - σmin) × ( )λ(1)

式中，T1是第一階段的談判輪數(shù);Tb是允許談判的最大輪數(shù)，σmin 和σmax是σ(t)的上下限，λ是控制σ(t)變化策略的參數(shù)。

(2) 采用各Agent單獨(dú)計算的反報價中的最小值作為下一輪買方提出的統(tǒng)一反報價。

4一對多兩階段談判模型

4.1 一對多兩階段談判模型描述

定義1將一對多兩階段談判模型定義為七元組{A，P，T，β ST，AC，I｝，其中:

A = {b，s1，s2，…，sj，…，sn｝表示參與談判的Agent集合。b表示買方Agent，s1，s2，…，sn分別表示n個相互獨(dú)立的賣方Agent。

T表示談判時間。為了便于討論，將談判時間離散化，即T = {1，2，…，t，…，Tb｝，用T來表示談判輪數(shù)集合;T1是第一階段的談判輪數(shù);Tb是買方談判的最大輪數(shù);Tsj是賣方Sj的最大談判輪數(shù)。其中，買方Agent向賣方發(fā)送一個提議并收到所有賣方Agent回應(yīng)為一輪。

P = {Pj| 0 ≤ j ≤ n，1 ≤ t ≤ Tb｝表示各方報價的集合。P0(t)表示買方b在第t輪的報價，Pj(t)(1 ≤ j ≤ n)則表示賣方Sj在第t輪的報價。每個Agent的報價Pj(t)(0 ≤ j ≤ n)都對應(yīng)一個預(yù)設(shè)的取值范圍[Pjmin，Pjmax]。

β = {β(t) | T1 ≤ t ≤ Tb｝表示賣方的合作可能度集合。β(t) = (β1(t)，β2(t)，…，βj(t)，…，βn(t))是第t輪所有賣方的合作可能度組成的向量。βj(t)是賣方Sj在第t輪的合作可能度。

ST = {spia， smid， simp｝表示Agent采用的談判策略集合，其中包含3種談判策略:spia表示節(jié)儉型策略，smid表示折中型策略，simp表示急躁型策略。Agent根據(jù)采取的策略和對手本輪的報價來生成下一輪的反報價。

AC = {proposal， re-proposal， accept， reject， terminate｝表示參與談判的Agent的原子行為集合。其中，proposal表示向?qū)κ痔岢鲆粋€報價，re-proposal表示拒絕接受對手的報價后向其提出一個新的報價，accept表示接受對手的報價，reject表示拒絕對手的報價并結(jié)束談判，terminate表示結(jié)束所有談判。

I = {Ib(t + 1，Pj(t))，Ij(t + 1，P0(t)｝，1 ≤ j ≤ n，1 ≤ t ≤ Tb，是Agent在收到對方報價后的反應(yīng)行為集合。Ib(t + 1，Pj(t))，為買方b在第t輪收到賣方Sj的報價Pj(t) 后，下一輪將采取的行動;Ij(t + 1，P0(t))，為賣方 Sj在第t輪在收到買方b的報價P0(t)后，下一輪將采取的行動。

4.2報價評估

每輪買賣雙方收到對方的報價后，要對收到的報價進(jìn)行評估，決定接下來要采取的行為。

在談判的第一階段，即1 ≤ t ≤ T1時，買方b不主動淘汰賣方。如果賣方Sj提出的報價Pj(t)低于買方b下一輪的反報價P0(t + 1)，則買方b應(yīng)該采取accept行為;否則，應(yīng)該提出反報價P0(t + 1)。這可以表示為:

Ib(t + 1，Pj(t)) = accept，P0(t + 1) ≥Pj(t) P0(t + 1)，otherwise(2)

在談判的第二階段，即T1 ≤ t ≤ Tb時，買方可以淘汰賣方。如果賣方Sj的合作可能度βj(t)小于σ(t)，則采取reject行為;如果t + 1 > Tb，則采取terminate行為。這可以表示為:

Ib(t + 1，Pj(t)) = accept，P0(t + 1) ≥Pj(t)reject，P0(t + 1) < Pj(t) and βj(t) < σ(t)terminate，P0(t + 1) < Pj(t) and t + 1> TbP0(t + 1)，otherwise (3)

賣方的報價評估過程與買方類似，只是賣方不區(qū)分所處的談判的階段。其采取的行為可以表示為:

Ij(t + 1，P0(t)) = accept，Pj(t + 1) ≤P0(t)reject，Pj(t + 1) > P0(t) and t + 1> TsjPj(t + 1)，otherwise (4)

4.3報價生成

根據(jù)賣方Agent在談判中采取的談判策略的不同，可以將賣方分成急躁型、節(jié)儉型和折中型3種類型[10-12]。具體說來，賣方Sj在第t輪的報價Pj(t)由下式?jīng)Q定:

Pj(t) = Pjmax - (Pjmax - Pjmin) × ( ) (5)

式中，λj為賣方Sj的策略參數(shù)。λj越小賣方越急躁，反之則越節(jié)儉。當(dāng)λj ≥ 2時為節(jié)儉型策略;當(dāng)0.5 < λj < 2時為折中型策略;當(dāng)0 < λj < 0.5時為急躁型策略。

買方用P0min作為首輪談判的報價P0(1)。在以后的輪次中，則根據(jù)賣方的報價計算出下一輪的反報價。買方的反報價P0(t + 1)的具體計算步驟是:

(1) 對每一個賣方sj，分別計算反報價P0 j(t + 1)。其計算方法是，首先根據(jù)談判軌跡圖對應(yīng)的反應(yīng)函數(shù)判斷賣方的談判策略[10];然后，根據(jù)賣方的談判策略采取相應(yīng)的反報價策略[9]，得到報價策略參數(shù)λ0 j(t)。最后，將參數(shù)λ0 j(t)代入公式計算出P0 j(t + 1):

P0j(t + 1) = Pjmin + (Pjmax - Pjmin) × ( ) (6)

(2) 由P0j(t + 1)得到統(tǒng)一的反報價P0(t + 1):

P0(t + 1) =P0j(t + 1) (7)

5實例分析

本文采用文獻(xiàn)[9]中的實例來對談判模型進(jìn)行分析。在本例中，各方的談判參數(shù)如表1所示:

其他參數(shù)，T1 = 10，Tb = Tsj = 40，買家b針對節(jié)儉型、折中型、急躁型的賣方，λ0 j取值分別為8、5和4。σ(t)的上下限σmax和σmin分別為0.6和0.01，λ取值為1.5。

實驗?zāi)M談判過程，得到的各賣方合作可能度變化如圖1所示。

實驗結(jié)果表明，第26輪買方與賣方3達(dá)成協(xié)議，結(jié)果與文獻(xiàn)[9]一致，證明本文中提出的模型能夠達(dá)到預(yù)期的效果。

6結(jié)論

本文通過對基于Agent的一對多并行談判的研究發(fā)現(xiàn):拍賣模型存在缺乏公平性，買方無法通過使用談判策略來得到更優(yōu)的報價等缺陷;并行談判模型需要對并行的各一對一談判進(jìn)行協(xié)調(diào)控制，引入了額外的通訊和協(xié)調(diào)開銷，增加了談判的成本。針對這些問題，本文提出了一種兩階段的一對多談判模型，將談判分為兩個階段。在談判的第一階段，不主動淘汰賣方，以保證賣方有機(jī)會了解買方的談判策略，不會被過早淘汰;在談判第二階段，買方根據(jù)合作可能度來淘汰不滿足要求的賣方，以此來降低通訊和協(xié)調(diào)開銷，加快談判進(jìn)度，在不影響談判最終結(jié)果質(zhì)量的前提下減少總的談判成本。通過實例驗證表明，本文提出的模型能夠達(dá)到預(yù)期的效果。

主要參考文獻(xiàn)

[1] Minghua He， Ho-fung Leung. Agents in E-Commerce: State of the Art[J]. Knowledge and Information System， 2002，4(3): 257-282.

[2] Martin Bichler. A Roadmap to Auction-based Negotiation Protocols for Electronic Commerce[C]. Proceedings of the 33rd Hawaii International Conference on System Sciences，IEEE Press， 2000.

[3] David Esther， Azoulay-Schwartz Rina， Kraus Sarit. Bidding in Sealed-bid and English Multi- attribute Auctions[J]. Decision Support Systems， 2006， 42(2): 527-556.

[4] Thuc Duong Nguyen， Nicholas R Jennings. A Heuristic Model for Concurrent Bilateral Negotiation in Incomplete Information Settings[C]. Proceedings of 18th International Joint Conference on AI， Morgan Kaufmann， 2003.

[5] Thuc Duong Nguyen， Nicholas R Jennings. Managing Commitments in Multiple Concurrent Negotiations[J]. Electronic Commerce Research and Applications， 2005， 4(4): 362-376.

[6] 張謙. 基于電子商務(wù)環(huán)境的多Agent并發(fā)協(xié)商策略研究[D]. 重慶: 西南大學(xué)， 2006.

[7] Iyad Rahwan， Ryszard Kowalczyk， Ha Hai Pham. Intelligent Agents for Automated One-to-many E-commerce Negotiation[C]. Conferences in Research and Practice in Information Technology Series;Proceeding of the 25th Australasian Conterence on Computer Science，2002: 197-204.

[8] 張蕊芬， 黃梯云， 蔣國瑞. 基于Agent的兩階段式一對多談判模型[J]. 計算機(jī)應(yīng)用，2009， 29(2): 565-567，573.

[9] 李冉冉， 孫華梅， 蔣國瑞，等. 基于Multi-agent的一對多淘汰制談判模型研究[J]. 信息系統(tǒng)學(xué)報， 2008， 2(1): 29-36.

[10] 汪定偉， 王慶， 宮俊，等. 雙邊多輪價格談判過程的建模與分析[J]. 管理科學(xué)學(xué)報， 2007，10(1): 95-97.

[11] 張謙， 邱玉輝. 一種具有自主學(xué)習(xí)能力的并發(fā)協(xié)商模型[J]. 計算機(jī)應(yīng)用. 2006， 26(3): 663-665.

[12] 張宏， 何華燦. 多Agent自動協(xié)商策略和算法[J] . 計算機(jī)應(yīng)用， 2006， 26(8): 1935-1937.

Research on Two-phases One-to-many Negotiation Model Based on Agent

QU Hua

(School of Economics and Management， University of Science and Technology Beijing， Beijing 100083，China)

Abstract:This paper proposes an agent-based two-phases one-to-many negotiation model. Compared with one-phase concurrent one-to-many negotiation， this model doesn’t eliminate sellers in phase one， so seller won't lose its chance too soon because of it’s adoption of conservative strategy in early bargain rounds; And this paper proposes an improved cooperation-degree-based-eliminating negotiation mechanism. In negotiation phase two， this model gradually eliminates sellers with less cooperation-degree， to achieve the goal of reducing negotiation cost.

Key words:Agent-based One-to-many Negotiation; Two-phases Negotiation; Negotiation Model; Negotiation Strategy

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文