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

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

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

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