山東大學眾智科學復習筆記

寫在前面：鹿男神yyds，講課詼諧有趣，條理清晰，給分可沖，總而言之，眾智可沖，題主94，12/160，本文是復習時的總結，希望學弟學妹95+

第一章 圖論基礎

1. 圖 = 事物（節(jié)點） + 聯(lián)系（邊）

2. 同構：圖的畫法不同，結構上相同，兩圖同構意味著可以找到一組對應的點，其關系也一致。

3. 鄰接矩陣（點集和點集），關聯(lián)矩陣（點集和邊集）

4. 圖的直徑：任意兩個節(jié)點之間的最大距離

5. BFS（廣度優(yōu)先搜索）—— 可以用于解決最短路徑問題（將節(jié)點分層）

6. $A^{?}$算法——是對BFS求最短路徑的優(yōu)化，BFS是一種亂走，而$A^{?}$算法更智能，將曼哈頓距離（點和點之間坐標縱向和橫向的距離之和）引入BFS中

7. DFS（深度優(yōu)先搜索）—— 用于找到所有路徑（相比于全排列的包利發(fā)，雖然DFS輸出的少但仍然是仍然是指數級別的）

8. 佛洛依德算法 —— 一次性求所有節(jié)點之間的最短距離（是最簡單的最短路算法，比暴力的DFS簡單，但復雜度很高為$n^3$）
   ? 算法圖解
   

9. 貝爾曼福特算法 —— 單源最短路徑問題（給定一個起點s，求其到圖中n個點的最短路徑)
   優(yōu)點是邊的權值可以為負數。
   算法圖解
   
   
   
   
   

10. SPFA = 隊列處理 + 貝爾曼福特算法
    ? 算法步驟
    ? 首先初始化一個數組用以存放源點到每個點的距離（到自己是 0，其他點是無窮），并且把源點加入隊列。隊列隊首元素出列，更新每個節(jié)點（隊首元素指向的點）到源點的距離，再將隊首元素指向的點加入隊列。重復操作，直至隊列元素為空。

11. Dijkstra（迪杰斯特拉）算法 —— 解決單源最短路徑問題（優(yōu)點是高效且穩(wěn)定，缺點是只能處理不含有負權邊的圖）
    ? 算法步驟
    ? 首先初始化數組存放源點到每個點的距離（自己是0，其他是無窮），集合A存放源點，集合B存放剩下的點。更新源點臨接的點的距離，在數組中選到源點距離最短的點，加入A集合，并從B集合中刪除。更新這一點臨接的點的距離，重復上述步驟，直到B集合為空。

12. 在社會網絡意義下，某些邊具有更加特殊的重要性，比如橋（割邊），捷徑
    

13. 入度（以該點為終點），出度（以該點為起點）

14. 歐拉通路（從某點出發(fā)，遍歷整個圖，每條邊通過且只通過一次）；歐拉回路（起點和終點相同的歐拉通路）

15. 判斷一個無向圖是否有歐拉回路？—— 圖中的點都具有偶數度
    一個無向圖是否有歐拉通路？—— 圖中有且僅有兩個奇數度點，其余點都是偶數度

16. 一個圖是二分圖，當且僅當其中不存在長度為奇數的圈

第二章 社會網絡

1. 快照：某一時刻社會網絡圖的形狀

2. 三元閉包：如果兩個互不認識的人有了一個共同的朋友，則他們倆將來成為朋友的可能性會提高。

3. 節(jié)點A的聚集系數=A的任意兩個朋友之間也是朋友的概率（比如A有三個朋友B,C,D，其中B和C是朋友，B和D，C和D都不是朋友，則節(jié)點A的聚集系數為$\frac{1}{C_3^1}=\frac{1}{3}$

4. 度分布函數$P(k)$表示網絡中度為k的節(jié)點在整個網絡中所占的比例。

5. 累計度分布函數，$P_k=\sum _{x=k}^{\infty }P(x)$表示度不小于k的節(jié)點的概率分布。

6. 介數：用來描述網絡中節(jié)點承載最短路徑數的能力（不說人話）
   節(jié)點（或邊）介數=網絡中所有最短路徑中經過該節(jié)點（或邊） 的概率之和

7. 介數計算
   
   實例
   步驟1：先從給定點進行BFS進行分層
   
   步驟2：從頂至下從A點向下一層節(jié)點發(fā)出1個流量
   
   步驟3：從下到上，計算經過每條邊的流量（注意，每個點本身有1個流量）
   
   計算過程：K節(jié)點有1個流量，$\frac{1}{2}$來自I節(jié)點，$\frac{1}{2}$來自J節(jié)點。對于I節(jié)點，A到F有兩條最短路徑，A到G有1條最短路徑，故IF邊和IG邊流量比為2:1，I給K$\frac{1}{2}$的流量，本身自己有1個流量，故到I的流量總和為$\frac{3}{2}$，故IF流量為1，IG流量為$\frac{1}{2}$。

8. 強三元閉包：

   如果A-B和A-C之間的關系為強關系；則B-C之間形成邊的可能性很高，如果B-C之間沒有關系（強或弱），則稱A點違背了強三元閉包原理。

   可以將社交網絡中所有關系歸為兩大類：強關系和弱關系

9. 捷徑：若邊A-B的端點A和B沒有共同的朋友，則稱A-B邊為捷徑。

10. 捷徑和弱關系：若節(jié)點A符合強三元閉包，且至少有兩個強關系鄰居，則與A相連的任何捷徑必定意味著弱關系。

    證明：（反證法）

    已知一社交網絡及一節(jié)點A，滿足強三元閉包性質并至少涉及兩個強聯(lián)系邊，假設A和B直接有一捷徑相連，且該捷徑為強聯(lián)系。由于A、B之間為捷徑，則沒有共同朋友，但根據強三元閉包原則，又必須有共同朋友，因此矛盾，因此預期相連的捷徑均為弱聯(lián)系。

第三章 同質性

1. 同質性：我們和自己的朋友往往會有相同點
   每個人的特質分為兩種——固有特質（性別，種族，母語等自然屬性）和可變特質（外部屬性，比如興趣愛好等）
   社會學一個問題：人們是因為相似才成為朋友還是成為朋友之后變得相似？

2. 同質性的判別基準
   兩種節(jié)點類型占比分別為p和q，對網絡中的任意一條邊，兩端點不同的概率是2pq（均勻情況），如果實際情況端點不同的比例明顯小于2pq，則認為同質性明顯。

3. 同質現象的背后機制
   選擇性：人們傾向于和他們相似的人成為朋友 -> 社團閉包
   社會化：人們也會因為需要和朋友們保持一致而改變自己的行為 ->會員閉包
   

4. 謝林模型——隔離的一種空間模型
   
   隔離現象并不一定是個人刻意選擇的結果。

第四章 正負關系

1. 邊的正負性——支持(+)與反對(-)；朋友(+)與敵人(-)

2. 社會網絡中三角關系的穩(wěn)定性
   

3. 社會網絡圖的結構平衡：若圖中所有三角關系都是平衡的，則該完全圖結構平衡。（用定義來判別不方便）

4. 平衡定理：如果一個完全圖是平衡的，則要么它的所有節(jié)點兩兩都是朋友，要么它的節(jié)點可以被分為兩組，一組內的節(jié)點兩兩都是+關系，另一組內的節(jié)點兩兩也都是+關系，而兩組之間的節(jié)點兩兩之間都是-關系
   

5. 平衡定理的推廣：放松條件 —— 弱平衡網絡
   (1) 弱平衡 —— 只是不允許+±
   (2) 允許邊的缺失 —— 考慮非完全圖的情況
   可以分成若干組，組內均為+關系，組間均為-關系

6. 近似平衡的網絡：允許存在少量三角形不平衡

7. 討論一個非完全圖結構的平衡性
   (1) 可以添加適當的邊形成平衡的完全圖
   (2) 可以分成兩個敵對陣營
   這兩種定義等價

8. 非完全圖結構的平衡性簡單判別
   圖是平衡的，當且僅當它不包含奇數個負關系的邊的圈。（當且僅當廣度優(yōu)先搜索時不存在同層的邊）
   
   
   可以像上圖一樣去抽象成負關系圖
   
   也可以判斷圖中每個方格中負關系邊是否均為偶數

第五章 小世界

1. 六度分隔：人類社會網絡中，任何兩個人之間的最短路徑長度都不超過6

2. 形成社會網絡的兩種基本力量：同質性，弱關系

3. Watts-Strogatz模型（r,k）
   
   其中，r是同質連接的參數，表示某個節(jié)點到那些相距r網格步以內的節(jié)點的連接；k是弱關系連接的參數，表示對某個節(jié)點，在網絡中隨機均勻選擇k個節(jié)點建立弱關系連接。
   疑問：弱連接的概率應該隨距離的冪次遞減，k值確定弱鏈接的方式似乎不能反映真實情況

4. Watts-Strogatz-Kleinberg模型
   在Watts-Strogatz模型基礎上，讓兩個節(jié)點存在隨機邊（弱關系）的概率與距離的某個冪次（q）成反比。
   
   理論結果：q=2時，分散搜索達到最佳效果。

第六章 搜索引擎

1. 搜索引擎的基本問題：對用戶提交的一個查詢，從海量網頁集合中將可能滿足用戶需求的少數結果找出來

2. 網頁的中樞與權威性(一篇網頁可以兼具兩個性質)
   權威性：被很多網頁指向
   中樞性：指向很多網頁

3. HITS算法：計算網頁的權威值(auth)和中樞值(hub)
   計算方法：
   
   示例
   
   
   （上圖是運行4輪）
   但是，auth和hub數值會隨著迭代次數遞增，什么時候收斂？
   數值的意義在于相對大小 —— 在每一輪結束后做歸一化（值/總和）
   歸一化結果隨迭代次數會趨向于一一個極限。

4. PageRank：利用網頁間的鏈接關系計算網頁重要性
   示例
   
   算法描述
   

5. PageRank與HITS算法對比
   PageRank不需要歸一化
   但有可能出現共謀制造垃圾網頁的情況
   
   最后收斂時F和G兩個節(jié)點的PageRank值會達到$\frac{1}{2}$，其他節(jié)點為0

6. 改進 —— PageRank的同比縮減與統(tǒng)一補償
   

7. 隨機游走：PageRank的一種等價理解
   問題：考慮一篇網頁x，問經過k步隨機游走到達x的概率是多少？
   證明：到達x的概率等于運行PageRank基本算法k步得到的值。

第七章 博弈論基礎

1. 收益矩陣
   

2. 嚴格占優(yōu)策略：對一個參與人來說，若存在一個策略，無論另一個參與人選擇何種策略，該策略都是嚴格最佳的選擇，則這個策略稱為是前者的嚴格占優(yōu)策略。（如上圖中“我”的嚴格占有策略是復習考試）

3. 囚徒困境
   
   

4. 營銷戰(zhàn)略
   

5. 嚴格占優(yōu)策略與不嚴格占優(yōu)策略
   嚴格與不嚴格的區(qū)別，看是＞還是≥
   

6. 納什均衡：都不改變策略的策略組（互為最佳應對的策略組）
   

7. 鷹鴿博弈
   總共有6個食物，如果是兩個鴿子分則一人3個，如果是一只鷹和一只鴿子分則鷹5個鴿子一個，如果是兩只鷹分則兩人都為0
   
   其中兩個納什均衡為（鷹，鴿）和（鴿，鷹）
   （為什么沒有鷹鷹，因為如果鷹鷹，兩人都是0，我不如換成鴿，還能拿一個）

8. 零和博弈 —— 不存在納什均衡的博弈
   

9. 混合策略的引入

10. 混合策略均衡求解：對于某個人而言他的兩個策略的收益一致

11. 社會最優(yōu)：兩個人策略收益相加為最大。

12. 社會最優(yōu)和納什均衡可能一致。從社會應用的意義上講，那是均衡和社會最優(yōu)一致的系統(tǒng)是理想系統(tǒng)。

第八章 博弈論應用

1. 公路交通網
   
   假設有4000輛車，如果同時走A-C或者D-B則所需時間為40+45=85分鐘，如果一半司機走A-C-B，一半司機走A-D-B則時間為20+45=65，為納什均衡

2. 布雷斯悖論
   
   多修了一條路可能情況會更糟，在追求個人利益最大化動機的驅使下，解決社會問題不能僅靠增加資源，還要注意調整結構
   均衡狀態(tài)下，每個司機的納什均衡策略都是A-C-D-B，40+40=80>65，增加了一條路情況反倒變得更糟

3. 提高效率的辦法
   
   或者收費
   

4. 拍賣
   （1）英式拍賣——增價拍賣
   買方不斷出價（提高售價），部分買方逐漸退出，直至剩下一個買方，以當前價格獲得商品
   （2）荷蘭式拍賣——降價拍賣
   賣方從最高價逐漸降價，直至有第一個買方接受當前價格，獲得商品
   （3）首價密封拍賣
   買方同時向賣方提交密封報價，出價最高者以其出價獲得商品
   （4）次價密封拍賣
   買方同時向賣方提交密封報價，出價最高者以次價獲得商品

5. 考慮次價密封拍賣問題
   次價拍賣鼓勵人們說真話，我出價的占優(yōu)策略即是真實估價，如果我拿到購買權，我會以低于我出價的價格購買商品，賺；如果我沒拿到購買權，如果此時我想拿到購買權，需要出價比第一人高，這超乎我對商品的估價，收益為負。因此，出真實估價是占優(yōu)策略。

6. 匹配問題——形成社會最優(yōu)
   基于二分圖，左側節(jié)點表示一類資源，右側節(jié)點表示另一類資源
   當二分圖兩邊有數目相同的節(jié)點，一個完美匹配就是左右節(jié)點的配對，使得每個節(jié)點都有邊連接到另一邊節(jié)點且不會出現左邊兩個節(jié)點同時連接到右邊同一個節(jié)點
   引入估值和價格
   
   我們發(fā)現對于賣方x和y，商品a帶來的收益最大，這就存在一種競爭。
   
   可以通過調整價格來實現最優(yōu)匹配（市場清倉價格），經濟學術語為社會最優(yōu)
   推廣：
   
   一樣可以通過調整價格來實現和最大——被競爭商品加價

第九章 廣告

1. 廣告如何定價——互聯(lián)網公司給出每個廣告位的點擊率，供廣告主估計廣告位價值=點擊率$\times$單次點擊估值
   
   價格從0、0、0開始加價形成完美匹配

2. GSP：單品次價拍賣機制的一種自然推廣
   
   與單品次價拍賣中不同的是，在單品次價拍賣中，每個人的占優(yōu)策略都是按照自己的估值出價，但是在GSP中可能出現
   
   

3. VCG——為了保持次價拍賣的優(yōu)良性質
   
   
   
   
   
   

第十章 權力

1. 社交網絡中的權力——一個節(jié)點具有權力是因為，其他節(jié)點對其具有依附性，它具有排他性，飽和性，中心性
   反映在圖上：
   依賴性：對于A和C而言，這種價值的來源完全在于B
   排他性：B有能力排除A和C
   飽和性：B比群體中其它成員能獲得更多的價值，而一旦飽和之后，B維持這些社會關系的興趣會降低，它傾向于不滿足從一個關系中得到于對方均等的價值份額
   介數：B有高介數，B是網絡中多個節(jié)點對之間唯一的途徑點
   

2. 給定一個圖，”結果“是其中的一個匹配（一個點無沖突的邊的子集）

3. 結果的穩(wěn)定與不穩(wěn)定
   不穩(wěn)定：存在一條不在結果中的邊，其兩端的價值之和小于1
   穩(wěn)定：不存在不穩(wěn)定的邊

4. 兩人交互模型——納什議價解
   

假設A，B兩人談判分配1元錢，但A，B各有一個外部選項x和y

對于x，y的關系有如下兩種

（1）x+y<=1
這種情況下，A和B才會有可能達成協(xié)議，因為，她們都有可能拿到比x（y）更大的收益，如果兩人具有同等地位的談判權力時，即表示兩人同意平分剩余的s=1-x-y
則對A來說為x+$\frac{s}{2}$
則對B來說為y+$\frac{s}{2}$
為納什議價解
（2）x+y>1
這種請況，談個毛線

5. 兩人交互模型——最后通牒
   同樣A和B兩人分一元錢，A（通常為具有更高談判權力的人）提出一個方案，多少給B，剩下歸自己；B選擇接受或拒絕；如果B接受，拿到收益，如果B拒絕，兩人均拿不到錢
   如果B是一個完全理性人，那么不管A提出什么樣的方案，都會接受（有總比沒有好）
   實際情況，A不會給B很少很少的收益，相對那種極端情況會很溫和，”金錢至上“不是人類的典型行為
   結論：現實中出現$\frac{1}{6}$和$\frac{5}{6}$類似的分配關系就可以認為達到了理論極端情況

6. 網絡交換實驗——穩(wěn)定結果
   同樣，穩(wěn)定和不穩(wěn)定與上文所述概念類似，沒有一個節(jié)點可以向沒和自己達成協(xié)議的相鄰節(jié)點提出一種比現有收益更大的建議即為穩(wěn)定

7. 網絡交換實驗——平衡結果
   平衡結果：給定網絡其余部分為每個節(jié)點提供的最好外部選項，一個交換結果稱為平衡的條件是，對匹配的每條邊來說，價值的劃分體現了兩個節(jié)點的納什議價結果
   

圖（b）中，對于A和B，其外部選項之和為$0+\frac{1}{3}=\frac{1}{3}$，那么兩人平分剩下的$\frac{2}{3}$，即A為$0+\frac{1}{3}=\frac{1}{3}$，B為$\frac{1}{3}+\frac{1}{3}=\frac{2}{3}$。同理C和D也一樣滿足納什議價解，故圖（b）為一個平衡結果

第十一章 從眾和流行

1. 信息級聯(lián)——當人們放棄了自己的想法與認同別人的看法時，我們認為發(fā)生了群集或信息級聯(lián)

2. 經典問題——判斷藍多罐或紅多罐實驗
   
   計算過程主要運用貝葉斯公式，我們計算當前學生在拿到藍（紅）球以及知道之前學生拿到的球的顏色的條件下藍多罐的條件概率
   
   
   
   對于第三個學生而言，即便他抓到了紅球，也會說是藍多罐，即發(fā)生了信息級聯(lián)

3. 有的時候我們需要避免錯誤的信息級聯(lián)

4. 冪律——人們發(fā)現，擁有k個鏈入數的網頁占比近似地與1/k^2成正比
   

第十二章 新事物擴散

1. 一種經典模型
   
   對網絡中的每一條邊都轉化成一種博弈
   
   對某一確定的節(jié)點v，周圍有d個鄰居，其有占比p的鄰居選A，1-p的鄰居選B
   如何在A和B兩種事物之間進行選擇？
   

2. 聚簇——同質性往往可能成為新事物擴散的障礙，新的事物很難從外部進入緊密聯(lián)系的團體中
   
   密度：計算聚簇中的每個節(jié)點，其朋友出現在一個聚簇中的比例；聚簇的密度為這個比例的最小值
   比如上圖中，a、b、c、d構成一個聚簇，其中a、b、c的比例都是1，而d的比例是$\frac{2}{3}$，所以該聚簇的密度為$\frac{2}{3}$

3. 級聯(lián)定理——描述聚簇和級聯(lián)的關系
   
   A向B擴散，則$q=\frac{b}{a+b}$
   級聯(lián)定理的簡要證明
   

第十三章 信息不對稱

1. 制度追求與個人追求的博弈
   個人——一般會在制度下追求自身利益的最大化（我們所討論的都是“冷血”的理性人，不考慮那些少數利他主義者，我承認是我格局小了）
   制度的設計者——希望達到某種全局最優(yōu)，不希望有個人逐利情況而破壞制度

2. 外生事件和內生事件；外生事件市場和內生事件市場
   外生事件——該事件如何發(fā)生與人們的行為情況無關
   內生事件——該事件如何發(fā)生直接取決于人們的行動情況
   外生事件市場——事件發(fā)生的概率不受行動者參與的行為影響，比如：彩票（無論多少人去購買彩票，彩票中獎的概率不變），選舉（無論多少人投票都會有一個人當選）
   內生事件市場——事件發(fā)生的概率受到行動者參與的行為影響，比如：二手車市場（如果人們相信二手車市場的車質量很好，就會傾向于出高價，這樣就會促使二手車市場真的有高質量車出賣，車主也就會愿意把自己質量不錯的車賣到二手車市場；反之，如果人們不相信二手車市場有好車，那么出價就低，低價就導致車主不愿意將自己的好車賣到二手車市場）
   市場成交與否，在于雙方是否達成成交協(xié)議，但錯誤的估值或者信息之間的不對稱（信息差）導致原本可以存在的議價空間over

3. 賽馬問題——外生事件市場
   
   
   似乎看到——我們會把所有的錢賭在我們直覺中取勝概率大的馬上
   這種非“1”即“0”的事件本身就帶來一種“風險感”

4. 風險意識——擔心壞事出現而帶來的損失，寧可放棄一些好事出現帶來的利益
   損失厭惡——損失1000元的難過程度要高于得到1000元的高興程度
   同理，財富增長帶來的”好的感受“是隨著財富量的增加而減少的
   那我們該如何構建風險意識下的金錢模型呢？

5. 效用函數
   
   $U(w)?U(w?\Delta w)>U(w+\Delta w)?U(w)$
   刻畫出損失厭惡的一般表達
   針對之前提到的金錢模型，我們有
   

6. 賠付率如何設計——假定賽馬場是無賠賺運行（這是一種簡單理想情況，實際上馬場不可能不賺錢）
   
   
   化簡得到
   
   
   每個人對同一局比賽中的勝負情況有自己的判斷，比如：A認為甲馬獲勝概率0.6，乙馬獲勝概率0.4；但B認為甲馬獲勝概率為0.3，乙馬獲勝概率為0.7。我們稱這種判斷為每個人的”信念“
   通過上式可以看出，如果一個人的下注占收到的注的絕大部分，他的信念對狀態(tài)價格的影響就越大，進而對計算賠付率的影響也越大

7. 如何制訂下注策略保證自己肯定不虧本？——若大家都按照自己的信念下注，且賭場按照上述馬場無賠賺方式計算賠付率，一個人有無可能，無論哪匹馬贏，都能拿回自己下注的錢，即不虧本？
   答案是可能，如果一個人按照集體信念下注，即，A馬賠付率$o_A=2.5$，那么我就應該把40%的錢投在A馬上
   

8. 內生事件市場的復雜性——信息不對稱
   

9. 二手車市場
   
   （1）如果買賣雙方信息對稱，那么存在議價空間——好車價格在10-12，壞車價格在4-6之間是可以達成交易的
   （2）但是信息不對稱
   
   我們作為買家該如何出價？
   對市場上出現的好車占比進行預期，設為h；g為市場中真實的好車占比
   那么買家愿意付的價錢是$12h+6（1?h）$
   若$h=0?$
   ——此時買家愿意付6，那些好車（底價10）不會賣，而破車（底價4）全部賣掉，這是出現了一個情況，h真的是0（這個市場一輛好車都沒有，其實是因為一輛好車都沒成交）
   若
   ——如果代入$h$后的公式$12h+6（1?h）$的數值大于等于10，于是所有車都成交，此時$h$真的等于$g$
   ——如果如果代入$h$后的公式$12h+6（1?h）$的數值小于10，于是好車沒成交，破車全部成交，此時的$h$等于0，沒達到預期

10. 阿克羅夫檸檬市場（檸檬比喻質量很差的商品）
    一個小栗子
    

11. 如何減少信息不對稱影響
    

第十四章 表決

1. 表決——通過眾人的投票，形成對事物的群體判斷
   表決的三個重要因素
   （1）投票規(guī)則和制度
   （2）被表決對象
   （3）眾人

2. 偏好關系——討論理性表決的基礎
   
   偏好關系的性質——完備性和傳遞性
   

3. 群體偏好——群體表決者對被表決者形成的一個偏好全序
   
   問題：每位表決者都給出了完備且傳遞的偏好關系，如果組合在一起，一定能形成一個全序嘛？
   反例
   

4. 孔多塞悖論
   合理的個體行為+合理的聚合方式—>不合理的群體結論
   一個小栗子
   
   我們是否可以通過調整聚合方式來尋找合理的群體結論？

5. 逐一勝出
   
   但是好像順序會影響最終的結果

6. 積分制
   
   一個小栗子
   
   但是這樣的積分制真的合理嗎？
   
   
   似乎我們很難找到一種適用于所有場景的聚合方式

7. 對聚合方式的兩個合理要求
   -趨同性：對任意兩個候選項X和Y，如果所有個體都偏好X，那么群體排序中的結果也應該是偏好X
   -獨立于無關項：群體對侯選項X和Y的排序，僅取決于個體對它們的偏好，與個體對其他侯選項的看法無關（X和Y在群體排序中的結果，不能因為某一個體調整了某個候選項Z的相對位置而改變）

8. 阿羅不可能定理
   在三個或更多侯選項的條件下，任何多于2人參與的表決系統(tǒng)，都不可能同時滿足
   （1）趨同性
   （2）IIA（獨立于無關選項）
   （3）非獨裁性

9. 單峰偏好
   
   
   定理：在一個奇數個被表決對象的表決情況中，如果所有選舉人的排序都滿足單峰偏好，那么按照少數服從多數規(guī)則兩兩比較候選項產生的群體偏好是完備且傳遞的
   
   
   一個全是圖的小栗子
   還是剛才候選項為{A,B,C,D,E}的那個例子
   
   
   （1）選擇群體序中最大的——在目前最大的三個里選擇中間項（序列為A,B,C），也就是B，然后將B刪去
   
   （2）選擇群體序次大的——同理選C（這時的序列是A,C,C），然后刪去C
   
   （3）選擇群體序第三大的——同理選A（這時的序列是A,A,D），然后刪去A
   
   然后就一目了然了
   但是，為什么這么做是對的？

10. 中位項定理
    
    認為$X_3$第一的那個人，他的偏好序列中，$X_2$相比于$X_1$，與$X_3$更近，根據單峰偏好知，他認為$X_2>X_1$

證明題匯總

1. 若A節(jié)點滿足強三元閉包，且A至少有兩個強關系鄰居，則與A相連的任何捷徑必定意味著弱關系
   證明：
   強三元閉包：若節(jié)點A與B，A與C都有強關系，那么B與C至少有弱關系
   捷徑：兩節(jié)點A和B沒有共同朋友，稱為A-B邊為捷徑
   已知一社交網絡及一節(jié)點A，滿足強三元閉包性質并至少涉及兩個強聯(lián)系邊，假設A和B直接有一捷徑相連，且該捷徑為強聯(lián)系。由于A、B之間為捷徑，則沒有共同朋友，但根據強三元閉包原則，又必須有共同朋友，因此矛盾，因此預期相連的捷徑均為弱聯(lián)系

2. 證明次價拍賣鼓勵人們真實報價
   證明：
   當人們真實報價時，即按照自己的估值報價時，有兩種情況
   第一種，拿到交易權
   如果報價比真實估價高（增加報價），仍然會拿到交易權，收益都是真實估價減去第二位的出價，收益不變
   如果報價比真實估價低（降低報價），如果比第二位出價高，那么仍然會拿到交易權，收益是真實估價減去第二位的出價，收益不變；如果比第二位出價低，拿不到交易權，收益為0
   第二種，沒拿到交易權
   如果報價比真實估價高（增加報價），如果比第一位出價高，雖然拿到交易權，但是成交價格高于估價，收益為負；如果沒有第一位出價高，拿不到交易權，收益為0
   如果報價比真實估價低（降低報價），仍然拿不到交易權，收益為0
   綜上，次價拍賣中人們真實報價是最佳應對

3. 阿羅不可能定理
   在三個或更多侯選項的條件下，任何多于2人參與的表決系統(tǒng)，都不可能同時滿足
   （1）趨同性
   （2）IIA（獨立于無關選項）
   （3）非獨裁性

4. 解釋同質現象
   
   同質性是指我們和自己的朋友往往會有相同點，我們經常討論的問題是，人們是和與自己相似的人成為朋友還是與自己的朋友變得相似，用中國的古話說，是近朱者赤、近墨者黑還是物以類聚、人以群分。在社交網絡圖中，設不同類型端點的占比為p和q，通過計算邊端點類型不同的概率2pq和真實概率做比較，如果真實概率小于2pq，則可以說明該社交網絡有同質現象。該圖中，白色節(jié)點比例為$\frac{2}{3}$，紅色節(jié)點比例為$\frac{1}{3}$，$2pq=\frac{4}{9}$，而真實的端點類型不同的邊有5條，比例為$\frac{5}{18}$，$\frac{5}{18}<\frac{4}{9}$，故認為該圖可以說明同質現象。

5. 證明網格模式中的每一個小方格都穩(wěn)定，則整體的大結構也穩(wěn)定
   證明：
   考慮一個圈涉及的邊的條數，總是由若干方塊構成，每個方塊四條邊，其中偶數條負關系邊，設為2k。一個圈中涉及的邊有周長邊和內部邊，其中設周長邊中負關系邊數為m，內部邊的負關系邊數為n。那么，由于內部邊為兩個方格共享，于是有$2k=m+2n$，于是m一定是偶數，因此整體一定平衡穩(wěn)定

6. 中位項定理的證明
   證明：
   欲證明中位項定理的正確性，即要說明，每一次相繼取出的中間項，在少數服從多數的原則下，比其他所有還剩下的候選項都要大
   設$L_1,L_2,L_3...L_m$為個體的單峰偏好排序表，設$L_i(1)$為對應個體偏好排序表中第一個也就是最大的元素
   將$L_1(1),L_2(1)...L_m(1)$按照從小到大的特征序排序，不妨設為$X_1...X_i...X_m$，其中$X_i$是序列中的中位項，只需證明$X_i$和其他（m-1）項相比都能以少數服從多數勝出。不失一般性，我們只討論$X_i$和左邊項相比的情況，$X_i$都至少獲得右邊所有項的支持，加上自己的一票，獲得了大于一半人的票數。在取走第一個中間項后的情況同理，于是證明出中位項定理的正確性。

寫在后面：在發(fā)布時，感覺本文總結稍微有些粗，強烈建議眾智平時一定要認真聽課（劃重點），不要臨時抱佛腳，22年考試難度不大，但是考察很細，很多復習時容易忽略的名詞解釋（甚至ppt上也無），本文也只是參考，還是建議學弟學妹要自己總結，好啦，舊事重提，祝學弟學妹眾智95+文章來源地址http://www.zghlxwxcb.cn/news/detail-816726.html

到了這里，關于山東大學眾智科學與網絡化產業(yè)復習筆記的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！