《社會科學(xué)中的計(jì)算思維方法》《網(wǎng)絡(luò)、群體與市場》教學(xué)課件-012(表決)

關(guān)于第十二周學(xué)習(xí)內(nèi)容的延伸討論表決模型、困惑、思路人群與網(wǎng)絡(luò)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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