奇數定理

奇數定理

奇數定理是博弈論領域裡與納什均衡相關的一項重要理論,於1971年被威爾遜證明。

定義

在博弈論領域裡,幾乎所有有限策略的博弈都有有限奇數個納什均衡。這就意味著,一般地說,如果一個博弈有兩個純策略納什均衡,那么就一定存在第三個混合策略的納什均衡。即對於大多數雙均衡博弈問題,一般地說,都應該有一個混合策略納什均衡。

相關知識

1.博弈論:

博弈論是二人在平等的對局中各自利用對方的策略變換自己的對抗策略,達到取勝的目的。博弈論思想古已有之,中國古代的《孫子兵法》等著作就不僅是一部軍事著作,而且算是最早的一部博弈論著作。博弈論最初主要研究象棋、橋牌、賭博中的勝負問題,人們對博弈局勢的把握只停留在經驗上,沒有向理論化發展。

博弈論考慮遊戲中的個體的預測行為和實際行為,並研究它們的最佳化策略。

近代對於博弈論的研究,開始於策梅洛( Zermelo),波萊爾( Borel)及馮·諾依曼( von Neumann)。

2.納什均衡:

納什均衡是一種策略組合,使得每個參與人的策略是對其他參與人策略的最優反應。

假設有n個局中人參與博弈,如果某情況下無一參與者可以獨自行動而增加收益(即為了自身利益的最大化,沒有任何單獨的一方願意改變其策略的),則此策略組合被稱為 納什均衡。所有局中人策略構成一個策略組合(Strategy Profile)。納什均衡,從實質上說,是一種非合作博弈狀態。

納什均衡達成時,並不意味著博弈雙方都處於不動的狀態,在順序博弈中這個均衡是在博弈者連續的動作與反應中達成的。納什均衡也不意味著博弈雙方達到了一個整體的最優狀態,需要注意的是,只有最優策略才可以達成納什均衡,嚴格劣勢策略不可能成為最佳對策,而弱優勢和弱劣勢策略是有可能達成納什均衡的。在一個博弈中可能有一個以上的納什均衡,而囚徒困境中有且只有一個納什均衡。

數學意義

若p為質數,則p可整除(p-1)!+1.

證明過程:

p=2,命題顯然成立;
p=3,命題顯然成立;
對於奇質數p>=5,令a∈A={2,3,4.p-2},則B={a,2a,3a,.,(p-1)a}中不會有對於除數p同餘的兩個數;事實上 αa,βa∈B,αa≡βa(mod p),則a|α-β|能被p整除,而a|α-β|∈B,B中的元素不可能被p除盡.於是B中被p除得的餘數形成集合{1,2,3,...,p-1}.
假設B中被p除餘一的數是γa:
一若γ=1,則γa=a,它被p除余a,所以γ=1不成立;
二若γ=p-1,則γa=(p-1)a,它被p除余p-a,所以γ=p-1不成立;
三若γ=a,則γa=a*a,由於a*a≡1(mod p),故應有a*a-1=(a+1)(a-1)≡0(mod p),這只能是a=1或a=p-1,此與a∈A矛盾,故不成立;
有一二三知γ≠a且a,γ∈A.
a不同時,γ也相異;若a1≠a2,a1,a2∈A,且γa1≡γa2≡1(mod p),因,γa1,γa2∈B,而B中的元素關於mod p不同餘,可見a1≠a2,則γ1≠γ2.
即A中的每一個a均可找到與其配對的y,γ∈A使ay≡1(mod p),
又,a不同時,γ也相異.
因此,A中的偶數個(p-3個)元素可以分成(p-3)/2個二元組(a,y),每個二元組都滿足ay≡1(mod p),
∴ 1×2×3×4.(p-2)≡1(mod p)
p-1≡-1(mod p)
∴ (p-1)!≡-1(mod p)
從而p可整除(p-1)!+1

相關詞條

熱門詞條

聯絡我們