《社會科學中的計算思維方法》《網絡、群體與市場》教學課件-012(表決)

關于第十二周學習內容的延伸討論表決模型、困惑、思路人群與網絡

社會網絡中的計算思維方法關于第十二周學習內容的延伸討論表決模型、困惑、思路人群與網絡1本周線上內容表決在社會中的作用及其多種形式偏好關系：討論表決制度的基礎少數服從多數：形成群體決策的基礎孔多塞悖論議程設置波達計數法阿羅不可能定理單峰偏好單峰偏好下的表決結果中位項定理結果驅動的表決本周線上內容表決在社會中的作用及其多種形式不久前的一個真事參加某校校內的一個學科評估要從6個申請的學科中評出3個學校領導有傾向性，但校內自己難擺平，于是請若干外校人士一起組成9人委員會規(guī)則：每人投3票，達到2/3票數的學科算通過我們一次投出了：8，6，6，4，3，0而且前面三個正好是學校領導希望的！不久前的一個真事參加某校校內的一個學科評估而且前面三個正好是關于表決的初始問題人們?yōu)槭裁匆頉Q？表決選項至少需要幾個？黃金規(guī)則？少數服從多數若干個人意見

集體意見尋找真相尋求主流意見≥2為什么會有“一票否決”？關于表決的初始問題人們?yōu)槭裁匆頉Q？若干個人意見集體意假設（你、我、他）三人要

對甲、乙、丙三人投票選優(yōu)你認為甲比乙好，乙比丙好，自然也就有甲比丙好我認為乙比丙好，丙比甲好，自然也就有乙比甲好他認為丙比甲好，甲比乙好，自然也就有丙比乙好

甲>乙乙>丙丙>甲?!?!個體理性不一定能導致群體的理性甲乙丙乙丙甲丙甲乙每一個局部都正確不一定全局就正確！假設（你、我、他）三人要

對甲、乙、丙三人投票選優(yōu)你認為甲>關于偏好關系（選項≥3）{A,B,C,D}R1:{A>B,B>C,C>D}R2:{A>B,D>C,B>A}R3:{A>B,B>D,A>D}R4:{A>B,A>C,A>D,B>C,B>D,C>D}R5:A>B>C>D非對稱完備傳遞＝R4傳遞性：對任意不相同的元素A,B,C，若有A>B且B>C，則要有A>C關于偏好關系（選項≥3）{A,B,C,D}非對稱完備傳遞＝R對與錯？（鄰座討論）定義：如果存在A,B,…,X，有關系｛A>B,B>,…,>X,X>A｝，則稱該關系中存在一個“環(huán)”（回路）。給定一個偏好關系，假設它是非對稱的、完備的，那么，該關系要么是傳遞的，要么存在一個環(huán)。對與錯？（鄰座討論）定義：如果存在A,B,…,X，有假設有m（奇數）個表決者，n個候選項每人給出候選項集合上的一個完備且傳遞的偏好關系問題這些關系總共包含多少候選項對？按少數服從多數原則形成的集體偏好關系中一共包含多少候選項對？它是否一定完備？是否一定傳遞？假設進一步“體會個體意見群體意見”假設有4個候選項A,B,C,D，三個人要對它們進行表決，分別給出了下面的意見。按照少數服從多數原則（孔多塞原則），試判斷其中是否存在孔多塞悖論如果沒有，則給出群體排序（第一個也稱為孔多塞勝者，Condorcetwinner）A>B>C>D;D>C>B>A;A>C>B>D進一步“體會個體意見群體意見”假設有4個候選項A,B,關于表決機制我們已經知道每個個體給出完備且傳遞的關系（全序），采用少數服從多數聚合方式，有可能（但不一定）出現孔多塞悖論還知道根據每個個體給出的全序，為回避孔多塞悖論，采用不同的議程設置兩兩比較（少數服從多數方式），有可能導致不同的集體排序結果如果個體給出的關系中不隱含有孔多塞悖論，是否也可能出現議程設置顯現的矛盾？關于表決機制我們已經知道如果個體給出的關系中不隱含有孔多塞悖波達計數法的結果可能與孔多塞原則（Condorcetprinciple）的結果矛盾例如，三個選項，A,B,C，7人參加表決3人認為：A>B>C2人認為：B>C>A1人認為：B>A>C1人認為：C>A>B按孔多塞原則A是勝者按波達計數法A=3*2+2*1+2*0=8B=3*2+3*1+1*0=9C=1*2+2*1+4*0=4波達計數法的結果可能與孔多塞原則（Condorcetpri理解單峰偏好候選項集合：｛A,B,C,D,E｝設在某屬性下的序為A－C－E－B－D下面哪些候選項排序滿足單峰偏好要求最愛第二第三第四第五ABCDEBCADEEDCBABCDAECBDEA?????理解單峰偏好候選項集合：｛A,B,C,D,E｝最愛第但是

不難驗證B>C>D>A>E最愛第二第三第四第五ABCDEBCADEEDCBABCDAECBDEA這是為什么？這5個排序在屬性序（A-B-C-D-E）下都是單峰偏好！進一步的問題就是：若沒有孔多塞悖論，是否一定存在某種屬性序，其下所有個體排序都滿足單峰性?????但是

不難驗證B>C>D>A>E最愛第二第三課堂作業(yè)：

計算集體排序ABCDEFACDBEFCDEFABDCAEBFBACDEFEFDCABDECAFB屬性序：B，A，C，D，E，F課堂作業(yè)：計算集體排序ABCDEFACDBEFCDEFAB問題這個方法（算法），針對滿足單峰偏好性質的個體排序，給出了一個滿足少數服從多數原則的群體排序。當然，如果不用這樣一種辦法，而是采用基本的兩兩比較、按少數服從多數原則確定群體偏好的方法，也可以得到相同排序結果。這種方法有什么優(yōu)勢呢？問題這個方法（算法），針對滿足單峰偏好性質的個體排序，給出了為什么這方法是對的即要說明，相繼取出的那些“中間項”，在少數服從多數原則下，比其他所有還剩下的選項都要“大”。大于所有出現在排序表頭的選項也大于沒出現在排序表頭的選項為什么這方法是對的即要說明，相繼取出的那些“中間項”，在少數中間項勝出的一般圖示每條線代表一個人此人將Xm排第一選項按屬性序排列排序>?中間項勝出的一般圖示每條線代表一個人此人將Xm排第一選項按屬給定一組（許多）個體排序如果不知道它們是否“單峰”，有什么好一點的辦法看（1）是否存在孔多塞悖論；（2）如果不存在，群體序該如何？辦法之一兩兩比較，將結果表達為一個有向完全圖無有向環(huán)存在出度和入度為0的節(jié)點從入度為0的節(jié)點開始，一個個刪除如果刪不下去了，就出現了孔多塞悖論；否則刪除的順序就是群體序給定一組（許多）個體排序如果不知道它們是否“單峰”，有什么好《社會科學中的計算思維方法》《網絡、群體與市場》教學課件-012(表決)其他表決方式例子假設13個人要對3件事進行組合投票：給定所有可能的支持（Y）或反對（N）組合，要求每人選一個。他們的選擇如左（沒人覺得應該是NNN）：YNNYNNYNNNYNNYNNYNNNYNNYNNYYYNYNYNYYYYY但如果從這結果看人們的態(tài)度，恰好應該是NNN！Paradoxofmultipleelections其他表決方式例子假設13個人要對3件事進行組合投票：給定所有SocialChoiceTheoryComputationalsocialchoice選擇方式問題計算復雜性問題應用問題搜索排序，推薦，評級，…，凡需要從大量個體認識形成群體認識，即群體決策的場合有些大學（例如UniversityofAmsterdam）開有專門的課程（UlleEndriss教授）SocialChoiceTheoryComputatio《社會科學中的計算思維方法》《網絡、群體與市場》教學課件-012(表決)6天前設定的教學目標得到一些具體體會對社會科學與計算思維交叉的課程掌握部分教學內容《網絡、群體與市場》熟悉一種教學方式基于慕課的混合式教學30%的人有興趣且初步有信心回校開課完整一門新課，或部分融入現有課程6天前設定的教學目標得到一些具體體會6.CommunicatesHighExpectations

Expectmoreandyouwillgetmore.Highexpectationsareimportantforeveryone–forthepoorlyprepared,forthoseunwillingtoexertthemselves,andforthebrightandwellmotivated.Expectingstudentstoperformwellbecomesaself-fulfillingpropertywhenteachersandinstitutionsholdhighexpectationsofthemselvesandmakeextraefforts.

好的本科教育實踐七原則之一：設立并傳達較高的預期6.CommunicatesHighExpectati《社會科學中的計算思維方法》《網絡、群體與市場》教學課件-012(表決)對與錯？定義：如果存在A,B,…,X，有關系｛A>B,B>,…,>X,X>A｝，則稱該關系中存在一個“環(huán)”（回路），其中涉及到的項數稱為該環(huán)的長度。判斷：在一個完備的偏好關系中，如果存在一個環(huán)，當且僅當存在長度為3的環(huán)。對與錯？定義：如果存在A,B,…,X，有關系｛A>B關于第十二周學習內容的延伸討論表決模型、困惑、思路人群與網絡

社會網絡中的計算思維方法關于第十二周學習內容的延伸討論表決模型、困惑、思路人群與網絡27本周線上內容表決在社會中的作用及其多種形式偏好關系：討論表決制度的基礎少數服從多數：形成群體決策的基礎孔多塞悖論議程設置波達計數法阿羅不可能定理單峰偏好單峰偏好下的表決結果中位項定理結果驅動的表決本周線上內容表決在社會中的作用及其多種形式不久前的一個真事參加某校校內的一個學科評估要從6個申請的學科中評出3個學校領導有傾向性，但校內自己難擺平，于是請若干外校人士一起組成9人委員會規(guī)則：每人投3票，達到2/3票數的學科算通過我們一次投出了：8，6，6，4，3，0而且前面三個正好是學校領導希望的！不久前的一個真事參加某校校內的一個學科評估而且前面三個正好是關于表決的初始問題人們?yōu)槭裁匆頉Q？表決選項至少需要幾個？黃金規(guī)則？少數服從多數若干個人意見

集體意見尋找真相尋求主流意見≥2為什么會有“一票否決”？關于表決的初始問題人們?yōu)槭裁匆頉Q？若干個人意見集體意假設（你、我、他）三人要

對甲、乙、丙三人投票選優(yōu)你認為甲比乙好，乙比丙好，自然也就有甲比丙好我認為乙比丙好，丙比甲好，自然也就有乙比甲好他認為丙比甲好，甲比乙好，自然也就有丙比乙好

甲>乙乙>丙丙>甲?!?!個體理性不一定能導致群體的理性甲乙丙乙丙甲丙甲乙每一個局部都正確不一定全局就正確！假設（你、我、他）三人要

對甲、乙、丙三人投票選優(yōu)你認為甲>關于偏好關系（選項≥3）{A,B,C,D}R1:{A>B,B>C,C>D}R2:{A>B,D>C,B>A}R3:{A>B,B>D,A>D}R4:{A>B,A>C,A>D,B>C,B>D,C>D}R5:A>B>C>D非對稱完備傳遞＝R4傳遞性：對任意不相同的元素A,B,C，若有A>B且B>C，則要有A>C關于偏好關系（選項≥3）{A,B,C,D}非對稱完備傳遞＝R對與錯？（鄰座討論）定義：如果存在A,B,…,X，有關系｛A>B,B>,…,>X,X>A｝，則稱該關系中存在一個“環(huán)”（回路）。給定一個偏好關系，假設它是非對稱的、完備的，那么，該關系要么是傳遞的，要么存在一個環(huán)。對與錯？（鄰座討論）定義：如果存在A,B,…,X，有假設有m（奇數）個表決者，n個候選項每人給出候選項集合上的一個完備且傳遞的偏好關系問題這些關系總共包含多少候選項對？按少數服從多數原則形成的集體偏好關系中一共包含多少候選項對？它是否一定完備？是否一定傳遞？假設進一步“體會個體意見群體意見”假設有4個候選項A,B,C,D，三個人要對它們進行表決，分別給出了下面的意見。按照少數服從多數原則（孔多塞原則），試判斷其中是否存在孔多塞悖論如果沒有，則給出群體排序（第一個也稱為孔多塞勝者，Condorcetwinner）A>B>C>D;D>C>B>A;A>C>B>D進一步“體會個體意見群體意見”假設有4個候選項A,B,關于表決機制我們已經知道每個個體給出完備且傳遞的關系（全序），采用少數服從多數聚合方式，有可能（但不一定）出現孔多塞悖論還知道根據每個個體給出的全序，為回避孔多塞悖論，采用不同的議程設置兩兩比較（少數服從多數方式），有可能導致不同的集體排序結果如果個體給出的關系中不隱含有孔多塞悖論，是否也可能出現議程設置顯現的矛盾？關于表決機制我們已經知道如果個體給出的關系中不隱含有孔多塞悖波達計數法的結果可能與孔多塞原則（Condorcetprinciple）的結果矛盾例如，三個選項，A,B,C，7人參加表決3人認為：A>B>C2人認為：B>C>A1人認為：B>A>C1人認為：C>A>B按孔多塞原則A是勝者按波達計數法A=3*2+2*1+2*0=8B=3*2+3*1+1*0=9C=1*2+2*1+4*0=4波達計數法的結果可能與孔多塞原則（Condorcetpri理解單峰偏好候選項集合：｛A,B,C,D,E｝設在某屬性下的序為A－C－E－B－D下面哪些候選項排序滿足單峰偏好要求最愛第二第三第四第五ABCDEBCADEEDCBABCDAECBDEA?????理解單峰偏好候選項集合：｛A,B,C,D,E｝最愛第但是

不難驗證B>C>D>A>E最愛第二第三第四第五ABCDEBCADEEDCBABCDAECBDEA這是為什么？這5個排序在屬性序（A-B-C-D-E）下都是單峰偏好！進一步的問題就是：若沒有孔多塞悖論，是否一定存在某種屬性序，其下所有個體排序都滿足單峰性?????但是

不難驗證B>C>D>A>E最愛第二第三課堂作業(yè)：

計算集體排序ABCDEFACDBEFCDEFABDCAEBFBACDEFEFDCABDECAFB屬性序：B，A，C，D，E，F課堂作業(yè)：計算集體排序ABCDEFACDBEFCDEFAB問題這個方法（算法），針對滿足單峰偏好性質的個體排序，給出了一個滿足少數服從多數原則的群體排序。當然，如果不用這樣一種辦法，而是采用基本的兩兩比較、按少數服從多數原則確定群體偏好的方法，也可以得到相同排序結果。這種方法有什么優(yōu)勢呢？問題這個方法（算法），針對滿足單峰偏好性質的個體排序，給出了為什么這方法是對的即要說明，相繼取出的那些“中間項”，在少數服從多數原則下，比其他所有還剩下的選項都要“大”。大于所有出現在排序表頭的選項也大于沒出現在排序表頭的選項為什么這方法是對的即要說明，相繼取出的那些“中間項”，在少數中間項勝出的一般圖示每條線代表一個人此人將Xm排第一選項按屬性序排列排序>?中間項勝出的一般圖示每條線代表一個人此人將Xm排第一選項按屬給定一組（許多）個體排序如果不知道它們是否“單峰”，有什么好一點的辦法看（1）是否存在孔多塞悖論；（2）如果不存在，群體序該如何？辦法之一兩兩比較，將結果表達為一個有向完全圖無有向環(huán)存在出度和入度為0的節(jié)點從入度為0的節(jié)點開始，一個個刪除如果刪不下去了，就出現了孔多塞悖論；否則刪除的順序就是群體序給定一組（許多）個體排序如果不知道它們是否“單峰”，有什么好《社會科學中的計算思維方法》《網絡、群體與市場》教學課件-012(表決)其他表決方式例子假設13個人要對3件事進行組合投票：給定所有可能的支持（Y）或反對（N）組合，要求每人選一個。他們的選擇如左（沒人覺得應該是NNN）：YNNYNNYNNNYNNYNNYNNNYNNYNNYYYNYNYNYYYYY但如果從這結果看人們的態(tài)度，恰好應該是NNN！Paradoxofmultipleelections其他表決方式例子假設13個人要對3件事進行組合投票：給定所有SocialChoiceTheoryComputationalsocialchoice選擇方式問題計算復雜性問題應用問題搜索排序，推薦，評級，…，凡需要從大量個體認識形成群體認識，即群體決策的場合有些大學（例如UniversityofAmsterdam）開有專門的課程（Ull