【正文】 機(jī)制設(shè)計是微觀經(jīng)濟(jì)學(xué)和博弈論的一個重要分支，它是研究如何使系統(tǒng)成員履行全局最優(yōu)解的問題。近年來，機(jī)制設(shè)計已被應(yīng)用于電子市場設(shè)計、時刻表的制定問題東北大學(xué)碩士學(xué)位論文 第二章 相關(guān)理論概述 6 和資源組合分配等問題中，其應(yīng)用前景廣闊。本文研究的電子逆向拍賣招投標(biāo)機(jī)制是機(jī)制設(shè)計理論的典型應(yīng)用。機(jī)制設(shè)計理論本質(zhì)上是非對稱信息對策論在經(jīng)濟(jì)學(xué)上的應(yīng)用。根據(jù)信息完全與否，結(jié)合對參與者行動先后次序的界定，可分為以下四種不同類型的博弈:完全信息靜態(tài)博弈、完全信息動態(tài)博弈、不完全信息靜態(tài)博弈和不完全信息動態(tài)博弈。機(jī)制設(shè)計實(shí)際是一個不完全信息博弈，可以用不完全信息博弈理論來處理。機(jī)制設(shè)計是一種典型的三階段不完全信息(貝葉斯)博弈:第一階段，委托人提供一種機(jī)制或契約:第二階段代理人行動，他決定是否接受這種機(jī)制或契約。如果他接受，則進(jìn)入第三階段，代理人在機(jī)制約束下選擇自己的行動。在本文中，供應(yīng)商每輪制定的標(biāo)的是供應(yīng)商的行為，供應(yīng)商制定行為的原則表現(xiàn)為其戰(zhàn)略。在采購拍賣過程中，供應(yīng)商成本函數(shù)的形式是共同知識，但是成本函數(shù)中各參數(shù)的具體數(shù)值卻不是共同知識。在每輪拍賣中，供應(yīng)商同時競標(biāo)，屬于靜態(tài)博弈。在整個競標(biāo)過程中，反復(fù)不斷的競標(biāo)和選標(biāo)就是一個不完全信息的動態(tài)博弈的過程。賣家的對策問題在博弈論的機(jī)制設(shè)計中得到詳盡研究，每一種拍賣方式都可看作一種機(jī)制的實(shí)例。如果某種機(jī)制僅要求競標(biāo)人報出對物品的估價，則這種機(jī)制就是一種直接機(jī)制。如果某種機(jī)制被設(shè)計成競標(biāo)人處于自身利益而愿意誠實(shí)的報出對拍賣物品的真實(shí)估值，則這種機(jī)制就是一種激勵相容機(jī)制。假設(shè)競標(biāo)人之間不存在共謀，那么機(jī)制設(shè)計中的顯示原理可以表述如下：對于任何一種機(jī)制，都存在一個直接的、激勵相容的機(jī)制與之等價。因此，最優(yōu)拍賣機(jī)制就是一種直接的、激勵相容的機(jī)制，兩者是等效的。顯示原理 [48]是一個純粹的理論概念，其主要應(yīng)用就是求解滿足兩個限制條件的數(shù)學(xué)規(guī)劃問題：第一，激勵相容條件，即競標(biāo)人不可能通過謊報估價而獲益；第二，個體理性條件，即競標(biāo)人不會拒絕參加拍賣而得到更好的收益。 決策概述決策是人們在政治、經(jīng)濟(jì)、技術(shù)以及日常生活中普遍遇到的一種選擇方案的行為。由之前的機(jī)制設(shè)計的理論可以看出，決策是機(jī)制設(shè)計的一個至關(guān)重要的環(huán)節(jié)。決策或者說策略的好壞將直接影響到機(jī)制的最終效果。作為決策問題，一般應(yīng)該具備以下條件：(1) 存在一個明確的目標(biāo)；(2) 存在至少兩個及以上可供選擇的可行方案，即策略；(3) 存在一種或幾種不以人的已知而改變的自然狀態(tài)；(4) 各可行方案在自然狀態(tài)下可計算相應(yīng)的收益值。東北大學(xué)碩士學(xué)位論文 第二章 相關(guān)理論概述 7 從不同的角度出發(fā)可得不同的決策分類 [49]：(1) 按性質(zhì)的重要性分類可將決策分為戰(zhàn)略決策、策略決策和執(zhí)行決策，或叫戰(zhàn)略計劃、管理控制和運(yùn)行控制。戰(zhàn)略決策是涉及某組織發(fā)展和生存有關(guān)的全局性、長遠(yuǎn)問題的決策，如廠址的選擇、新產(chǎn)品的開發(fā)方向、新市場的開發(fā)、原料供應(yīng)地的選擇等。策略決策是為完成戰(zhàn)略決策所規(guī)定的目的而進(jìn)行的決策，如對一個企業(yè)產(chǎn)品規(guī)格的選擇、工藝方案和設(shè)備的選擇、廠區(qū)和車間內(nèi)工藝路線的布置等。執(zhí)行策略式根據(jù)策略決策的要求對執(zhí)行行為方案的選擇，如生產(chǎn)中產(chǎn)品合格標(biāo)準(zhǔn)的選擇、日常生產(chǎn)調(diào)度的決策等。(2) 按決策的結(jié)構(gòu)分類分為程序決策和非程序決策。程序決策是一種有章可循的據(jù)側(cè)，一般是可重復(fù)的。非程序決策一般是無章可循的決策，只能憑經(jīng)驗(yàn)直覺做出應(yīng)變的決策，一般是一次性的。(3) 按定量和定性分類分為定量決策和定性決策。描述決策對象的指標(biāo)都可以量化時可用定量決策，否則只能用定性決策?？偟陌l(fā)展趨勢盡可能地把決策問題量化。(4) 按決策環(huán)境分類可將決策問題分為確定型的、風(fēng)險型的和不確定型的三種。確定型的決策是指決策環(huán)境是完全確定的，做出選擇的結(jié)果也是確定的。風(fēng)險型決策是指決策環(huán)境不是完全確定的，而其發(fā)生的概率是已知的。不確定型決策是指決策者對講發(fā)生結(jié)果的概率一無所知，只能憑決策者的主觀傾向進(jìn)行決策。(5) 按決策過程的連續(xù)性分類可分為集中式?jīng)Q策和分布式?jīng)Q策。集中式?jīng)Q策是指整個過程只做一次決策就得到結(jié)果。分布式?jīng)Q策是指整個決策過程由一系列的決策組成，一般來講，管理活動是由一系列決策組成的，但在這一系列決策中往往有幾個關(guān)鍵環(huán)節(jié)要作決策，可以把這些關(guān)鍵的決策分別看作單項決策。 集中式?jīng)Q策概述集中式?jīng)Q策(Centralized Decision Making)：是指在一個系統(tǒng)中只有一個決策單元或者決策者，該決策者完成其所在的整個系統(tǒng)的決策。集中式?jīng)Q策的先決條件是所有信息已知。東北大學(xué)碩士學(xué)位論文 第二章 相關(guān)理論概述 8 當(dāng)一個系統(tǒng)由多個部分構(gòu)成時，需要決策者對系統(tǒng)的各個部分有很好的了解，才能保證最終做出準(zhǔn)確的決策。從集中式?jīng)Q策的角度來講，決策者將所有的決策集中于一身。系統(tǒng)中的各部分沒有決策權(quán)，只是去執(zhí)行決策結(jié)果。在已知供應(yīng)商成本信息的采購中，采購者的決策就是一種集中式?jīng)Q策，采購者是唯一的決策者。采購者根據(jù)各供應(yīng)商的具體成本情況，在保證供應(yīng)商獲得一定利益的情況下，決策出對自己最優(yōu)的分配方案。已知供應(yīng)商成本信息的采購分配是一種典型集中式?jīng)Q策行為。 分布式?jīng)Q策概述分布式?jīng)Q策(Distributed Decision Making)又叫多層決策或多階段決策(Multi—Stage Decision Process)，是指這樣一類活動過程：即根據(jù)問題本身的特點(diǎn)，可以將其求解的全過程劃分為若干相互聯(lián)系的階段(即將問題劃分為許多個相互聯(lián)系的子問題)，在它的每一階段都需要做出決策，并且在一個階段的決策確定以后再轉(zhuǎn)移到下一個階段。往往前一階段的決策要影響到后一階段的決策，從而影響整個過程。分布式?jīng)Q策最典型的特點(diǎn)就是多次決策，并且各個決策間都相互影響。多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實(shí)現(xiàn)的。一般情況下，系統(tǒng)在某個階段的決策，除了與本階段的狀態(tài)有關(guān)外，還與之前的歷史狀態(tài)和決策有關(guān)。多階段決策過程的目標(biāo)函數(shù)值是由多次決策的效應(yīng)綜合形成的。在某個階段 k，處于狀態(tài) xk 執(zhí)行決策uk 時帶來的目標(biāo)函數(shù)值得增量，稱為 k 階段效應(yīng)，階段效應(yīng)僅由階段所處狀態(tài)和決策確定，因此 k 階段效應(yīng)是該階段狀態(tài)和決策的函數(shù)，可以表示為 gk(xk,uk)。在分布式?jīng)Q策的每一個階段，都要涉及一個概念，就是策略。所謂策略(Policy)就是確定系統(tǒng)過程發(fā)展的方案，策略的實(shí)質(zhì)是關(guān)于狀態(tài)的選擇，是決策者從給定階段狀態(tài)出發(fā)對下一階段狀態(tài)做出的選擇。策略也叫決策序列。策略有全過程策略和 k 步子策略之分，全過程策略是指具有 n 個階段的全部過程，由依次進(jìn)行的 n 個階段決策構(gòu)成的決策序列，表示為{u 1,u2,…un}。從 k 階段到第 n 階段，依次進(jìn)行的階段決策構(gòu)成的決策序列稱為 k 步子策略。表示為 {uk,uk+1,…un}，顯然當(dāng) k=1 時的 k 步子策略就是全過程策略。當(dāng) k=n 時的 k 步子策略就是單步策略。在實(shí)際問題中，由于在各個階段可供選擇的決策有許多個，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列(策略)，由他們組成的集合，稱之允許策略集合，從允許策略集中，找出具有最有效果的策略稱為最優(yōu)策略。雙層決策是分布式?jīng)Q策的一種。決策過程中只有上下兩層。通常情況下上層(Uplevel)決策完之后下層(DownLevel)，上下層各自的決策都將對對方產(chǎn)生一定的影響。東北大學(xué)碩士學(xué)位論文 第二章 相關(guān)理論概述 9 一般情況下，由于上層先決策，故上層具有先行動優(yōu)勢。上層的決策能夠引導(dǎo)整個決策過程的發(fā)展。雙層決策的大體流程如下：首先上層決策者向下層宣布其決策 x，這一決策將影響到下層決策的約束或目標(biāo)函數(shù)；然后下層決策者在這一限制條件下選擇決策 y,以此對上層決策者的決策做出反應(yīng)，影響到上層決策者的目標(biāo)函數(shù)值及 x 的可行性；最后上層決策者再調(diào)整其 x，反復(fù)循環(huán)，達(dá)到均衡。在雙層決策問題中，雙方不斷地決策，然后相互影響，這種模式類似于招投標(biāo)中的協(xié)商模式。協(xié)商是經(jīng)濟(jì)學(xué)家、博弈論專家一直深刻探討的課題，是人類互動模式中一種最復(fù)雜的溝通方式。在協(xié)商過程中，兩個或更多的參與者各自做出決策，并為了各自的利益相互進(jìn)行交流，協(xié)商的結(jié)果不是一方得到的更多，另一方得到的就少，而是通過協(xié)商能使雙方都有收獲 [50]。協(xié)商主要包括三個要素：即雙方進(jìn)行信息交流，雙方從自己的觀點(diǎn)出發(fā)評估信息和最終通過相互選擇達(dá)成一致意見。一個協(xié)商系統(tǒng)主要由三個部分組成，協(xié)商協(xié)議，協(xié)商策略和協(xié)商目標(biāo)。協(xié)商協(xié)議是指控制、管理 Agent間交互協(xié)商的規(guī)則集合。協(xié)商策略是 Agent 決策和選擇協(xié)商協(xié)議和通信消息的策略，協(xié)商策略模型的復(fù)雜程度、決策范圍主要是受協(xié)商協(xié)議設(shè)計的影響與制約。協(xié)商協(xié)議和協(xié)商策略，這兩者共同構(gòu)成了一個協(xié)商系統(tǒng)的協(xié)商機(jī)制。協(xié)商目標(biāo)是指要達(dá)成的協(xié)議所覆蓋的問題范圍，即協(xié)商問題的數(shù)量，最簡單的屬于單一屬性的協(xié)商。在雙層模型中，上下層直接反復(fù)投標(biāo)、選標(biāo)的過程可以看作一個協(xié)商過程，故協(xié)商理論也可以被雙層決策模型所使用。 本章小結(jié)本章主要對拍賣理論，逆向拍賣理論和機(jī)制設(shè)計理論進(jìn)行了綜述。首先對傳統(tǒng)拍賣理論進(jìn)行了概述，并結(jié)合電子商務(wù)，說明了網(wǎng)上拍賣與傳統(tǒng)拍賣的區(qū)別。隨后，引出了逆向拍賣理論。通過對逆向拍賣理論的分析，找到了對逆向拍賣研究的關(guān)鍵，即機(jī)制設(shè)計問題。最后對機(jī)制設(shè)計理論進(jìn)行了相關(guān)的綜述，對策略，決策，集中式?jīng)Q策和分布式?jīng)Q策理論都進(jìn)行了詳細(xì)的理論描述，為后邊相關(guān)理論的實(shí)際應(yīng)用做好了鋪墊。東北大學(xué)碩士學(xué)位論文 第 3 章 供應(yīng)商成本信息已知的機(jī)制設(shè)計問題研究 0 第 3 章 供應(yīng)商成本信息已知的機(jī)制設(shè)計問題研究在供應(yīng)商成本信息已知的前提下，我們可以采用集中式?jīng)Q策的方法對電子逆向拍賣進(jìn)行研究。集中式?jīng)Q策的本質(zhì)就是優(yōu)化，通過數(shù)學(xué)建模尋找最優(yōu)點(diǎn)，如最優(yōu)分配，最優(yōu)規(guī)劃等。本章基于這種方法，進(jìn)行了一系列的研究，這樣做的目的不僅僅是為了得出結(jié)論，更重要的是為了給第四章的分布式?jīng)Q策結(jié)論形成一個可以對比分析的基準(zhǔn)。 問題描述在一次電子逆向拍賣中，拍購方要采購 M 個某產(chǎn)品，這些產(chǎn)品是由 N 個供應(yīng)商來提供，每一個供應(yīng)商都有各自的供應(yīng)上限，沒有一個供應(yīng)商能夠完全提供所有的產(chǎn)品。各個供應(yīng)商的單個產(chǎn)品供應(yīng)成本是隨著供應(yīng)量的變化而變化的，并且每當(dāng)拍購方與某一供應(yīng)商發(fā)生交易時，都會產(chǎn)生一個交易成本。假設(shè)供應(yīng)商的成本信息已經(jīng)全部展現(xiàn)給了拍購方，那么拍購方應(yīng)該如何選擇供應(yīng)商，才能使總的采購成本達(dá)到最低？其實(shí)對于上述問題，本質(zhì)上講就是一個勝者確定問題，如何優(yōu)化分配才能使拍購方的總費(fèi)用最小，這是一個典型的優(yōu)化問題。 供應(yīng)商的成本結(jié)構(gòu)類型在整個電子逆向拍賣過程中參與的供應(yīng)商個數(shù)是不止一個的，對于每個供應(yīng)商的類型也是不同的，此處，在給出拍購方選擇模型之前，先對供應(yīng)商的類型進(jìn)行分析，以有利于后期模型的建立。分類如下：目前關(guān)于供應(yīng)商的分類方法有好多種，針對本文的問題，我們以供應(yīng)商的成本結(jié)構(gòu)進(jìn)行分類，即可分為分銷商和生產(chǎn)商。分銷商是指是 指 那 些 專 門 從 事 將 商 品 從 生 產(chǎn) 者 轉(zhuǎn) 移 到 消 費(fèi) 者 的 活 動 的 機(jī) 構(gòu)和人員，當(dāng)這些分銷 商 的 活 動 產(chǎn) 業(yè) 化 以 后 ， 分 銷 業(yè) 也 就 形 成 了 。 對 于 分 銷 商 來 講 ， 他 的成 本 結(jié) 構(gòu) 應(yīng) 該 是 隨 著 訂 貨 批 量 的 上 升 ， 單 個 產(chǎn) 品 的 成 本 是 下 降 的 ， 直 到 供 應(yīng) 上 線 。生 產(chǎn) 商 是 指 那 些 利 用 各 種 原 材 料 進(jìn) 行 自 主 生 產(chǎn) 的 企 業(yè) 。 對 于 這 類 供 應(yīng) 商 來 講 ，當(dāng) 產(chǎn) 品 的 供 應(yīng) 量 在 一 定 的 范 圍 內(nèi) 時 ， 供 應(yīng) 成 本 會 隨 著 供 應(yīng) 量 的 增 加 而 減 少 。 當(dāng) 供 應(yīng)量 超 過 了 供 應(yīng) 商 的 正 常 生 產(chǎn) 能 力 時 ， 供 應(yīng) 成 本 就 會 隨 著 供 應(yīng) 量 的 增 加 而 升 高 。東北大學(xué)碩士學(xué)位論文 第 3 章 供應(yīng)商成本信息已知的機(jī)制設(shè)計問題研究 1 在 一 個 具 體 的 拍 賣 過 程 中 ， 參 與 拍 賣 的 供 應(yīng) 商 不 止 一 個 ， 故 可 以 依 據(jù) 供 應(yīng) 商 的成 本 結(jié) 構(gòu) 將 供 應(yīng) 商 進(jìn) 行 分 類 。 分 為 如 下 三 種 ：純分銷商：所有參與拍賣的供應(yīng)商都是分銷商。純生產(chǎn)商：所有參與拍賣的供應(yīng)商都是生產(chǎn)商。混合型：參與拍賣的供應(yīng)商是兩種類型的混合體。 拍購方的選擇模型與相關(guān)算法有了以上基礎(chǔ)，我們就可以給出拍購方的選擇模型，具體如下： 符號定義： 二進(jìn)制決策變量，如果供應(yīng)商 i 被選擇，那么 xi=1，否則 xi=0；ix： 整數(shù)決策變量，表示拍購方從第 i 個供應(yīng)商那購買的產(chǎn)品數(shù)量；iq： 當(dāng)拍購方與供應(yīng)商 i 發(fā)生交易時，所產(chǎn)生的交易成本；ik：供應(yīng)商 i 的成本矩陣，即當(dāng)拍購方從第 i 個供應(yīng)商處采購 qi 個產(chǎn)品時，單()iC個產(chǎn)品的購買價格；： 第 i 個供應(yīng)商能夠提供的最大供應(yīng)量；maxiQ?：