基于行為圖博弈的Nash均衡算法研究.pdf

1、博弈論（Game theory）是研究競爭條件下決策分析的科學(xué)。它研究的典型問題是若干個利益沖突者在同一環(huán)境中進行決策以求自己的利益得到滿足。近年來，博弈理論模型已經(jīng)在計算機科學(xué)和人工智能領(lǐng)域產(chǎn)生了深遠的影響。尤其是在多Agents領(lǐng)域，很多學(xué)者作出了大量工作，其方向主要集中在：博弈模型研究、博弈算法研究等。
　　 行為圖博弈模型是一種新型的博弈模型。它涵蓋已有的結(jié)構(gòu)化博弈模型，圖型博弈，阻塞博弈和局部效用博弈。求解Nash均衡

2、是行為圖博弈模型的核心問題。本文重點研究行為圖博弈模型上從效用函數(shù)到Nash均衡求解的相關(guān)問題。
　　 首先，在本文中我們詳細分析了博弈中Agent的有關(guān)問題，簡要介紹了規(guī)范型博弈，具有結(jié)構(gòu)化博弈模型的圖型博弈，以及阻塞博弈和局部效用博弈。并且分析了當(dāng)前一些學(xué)者們提出的算法。然后著重考察了行為圖博弈，在行為圖博弈中求解期望收益是通過動態(tài)規(guī)劃來完成的，分析了如何在行為圖博弈中求期望收益。我們把連續(xù)方法應(yīng)用到行為圖博弈中，我們不僅給

3、出如何在行為圖博弈中進行擾動操作、回溯、效用雅克比的計算及其消除累積錯誤，而且，更新混合策略剖面將其應(yīng)用到下一次迭代中。緊接著分析了如何在行為圖博弈中求解Nash均衡。
　　 我們用基GameTracer的規(guī)范型博弈求解期望收益，和本算法進行比較。用動態(tài)規(guī)劃求行為圖博弈的存儲數(shù)目，給出了一個五乘五的博弈來進行實驗。證明行為圖博弈成多項式增長，而規(guī)范型博弈成指數(shù)增長。
　　 其次，我們通過兩個實驗來驗證本算法的有效性，通過