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

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

2、規(guī)則？少數(shù)服從多數(shù)若干個人意見 集體意見尋找真相尋求主流意見2為什么會有“一票否決”？假設(shè)（你、我、他）三人要對甲、乙、丙三人投票選優(yōu)你認(rèn)為甲比乙好，乙比丙好，自然也就有甲比丙好我認(rèn)為乙比丙好，丙比甲好，自然也就有乙比甲好他認(rèn)為丙比甲好，甲比乙好，自然也就有丙比乙好甲乙乙丙丙甲?!?!個體理性不一定能導(dǎo)致群體的理性甲乙丙乙丙甲丙甲乙每一個局部都正確不一定全局就正確！關(guān)于偏好關(guān)系（選項(xiàng)3）A,B,C,DR1:AB,BC,CDR2:AB,DC,BAR3:AB,BD,ADR4:AB,AC,AD,BC,BD,CDR5: ABCD非對稱完備傳遞R4傳遞性：對任意不相同的元素A, B, C，若有AB且BC

3、，則要有AC對與錯？（鄰座討論）定義：如果存在 A, B, , X，有關(guān)系A(chǔ)B, B, , X, XA，則稱該關(guān)系中存在一個“環(huán)”（回路）。給定一個偏好關(guān)系，假設(shè)它是非對稱的、完備的，那么，該關(guān)系要么是傳遞的，要么存在一個環(huán)。假設(shè)有m（奇數(shù)）個表決者，n個候選項(xiàng)每人給出候選項(xiàng)集合上的一個完備且傳遞的偏好關(guān)系問題這些關(guān)系總共包含多少候選項(xiàng)對？按少數(shù)服從多數(shù)原則形成的集體偏好關(guān)系中一共包含多少候選項(xiàng)對？它是否一定完備？是否一定傳遞？進(jìn)一步“體會個體意見群體意見”假設(shè)有4個候選項(xiàng)A, B, C, D，三個人要對它們進(jìn)行表決，分別給出了下面的意見。按照少數(shù)服從多數(shù)原則（孔多塞原則），試判斷其中是否存在

4、孔多塞悖論如果沒有，則給出群體排序（第一個也稱為孔多塞勝者，Condorcet winner）ABCD; DCBA; ACBD關(guān)于表決機(jī)制我們已經(jīng)知道每個個體給出完備且傳遞的關(guān)系（全序），采用少數(shù)服從多數(shù)聚合方式，有可能（但不一定）出現(xiàn)孔多塞悖論還知道根據(jù)每個個體給出的全序，為回避孔多塞悖論，采用不同的議程設(shè)置兩兩比較（少數(shù)服從多數(shù)方式），有可能導(dǎo)致不同的集體排序結(jié)果如果個體給出的關(guān)系中不隱含有孔多塞悖論，是否也可能出現(xiàn)議程設(shè)置顯現(xiàn)的矛盾？波達(dá)計(jì)數(shù)法的結(jié)果可能與孔多塞原則（Condorcet principle）的結(jié)果矛盾例如，三個選項(xiàng)，A, B, C，7人參加表決3人認(rèn)為：A B C2人認(rèn)為

5、：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理解單峰偏好候選項(xiàng)集合：A, B, C, D, E設(shè)在某屬性下的序?yàn)?ACEBD 下面哪些候選項(xiàng)排序滿足單峰偏好要求最愛第二第三第四第五ABCDEBCADEEDCBABCDAECBDEA但是不難驗(yàn)證B C D A E最愛第二第三第四第五ABCDEBCADEEDCBABCDAECBDEA這是為什么？這5個排序在屬性序（A-B-C-D-E）下都是單峰偏好！進(jìn)一步的問題就是：若沒有孔多塞悖論，是否一定存在某種屬性序，其下所有個體

6、排序都滿足單峰性課堂作業(yè)： 計(jì)算集體排序ABCDEFACDBEFCDEFABDCAEBFBACDEFEFDCABDECAFB屬性序：B，A，C，D，E，F(xiàn)問題這個方法（算法），針對滿足單峰偏好性質(zhì)的個體排序，給出了一個滿足少數(shù)服從多數(shù)原則的群體排序。當(dāng)然，如果不用這樣一種辦法，而是采用基本的兩兩比較、按少數(shù)服從多數(shù)原則確定群體偏好的方法，也可以得到相同排序結(jié)果。這種方法有什么優(yōu)勢呢？為什么這方法是對的即要說明，相繼取出的那些“中間項(xiàng)”，在少數(shù)服從多數(shù)原則下，比其他所有還剩下的選項(xiàng)都要“大”。大于所有出現(xiàn)在排序表頭的選項(xiàng)也大于沒出現(xiàn)在排序表頭的選項(xiàng)中間項(xiàng)勝出的一般圖示每條線代表一個人此人將Xm排

7、第一選項(xiàng)按屬性序排列排序?給定一組（許多）個體排序如果不知道它們是否“單峰”，有什么好一點(diǎn)的辦法看（1）是否存在孔多塞悖論；（2）如果不存在，群體序該如何？辦法之一兩兩比較，將結(jié)果表達(dá)為一個有向完全圖無有向環(huán)存在出度和入度為0的節(jié)點(diǎn)從入度為0的節(jié)點(diǎn)開始，一個個刪除如果刪不下去了，就出現(xiàn)了孔多塞悖論；否則刪除的順序就是群體序其他表決方式例子假設(shè)13個人要對3件事進(jìn)行組合投票：給定所有可能的支持（Y）或反對（N）組合，要求每人選一個。他們的選擇如左（沒人覺得應(yīng)該是NNN）：Y N N Y N N Y N N N Y N N Y N N Y N N N Y N N Y N N Y Y Y N Y N

8、 Y N Y YY Y Y 但如果從這結(jié)果看人們的態(tài)度，恰好應(yīng)該是NNN！Paradox of multiple electionsSocial Choice TheoryComputational social choice選擇方式問題計(jì)算復(fù)雜性問題應(yīng)用問題搜索排序，推薦，評級， ，凡需要從大量個體認(rèn)識形成群體認(rèn)識，即群體決策的場合有些大學(xué)（例如University of Amsterdam）開有專門的課程（Ulle Endriss教授）6天前設(shè)定的教學(xué)目標(biāo)得到一些具體體會對社會科學(xué)與計(jì)算思維交叉的課程掌握部分教學(xué)內(nèi)容網(wǎng)絡(luò)、群體與市場熟悉一種教學(xué)方式基于慕課的混合式教學(xué)30%的人有興趣且初步

9、有信心回校開課完整一門新課，或部分融入現(xiàn)有課程6. Communicates High Expectations Expect more and you will get more. High expectations are important for every one for the poorly prepared, for those unwilling to exert themselves, and for the bright and well motivated. Expecting students to perform well becomes a self-fulfilling property when teachers and institutions hold high expectations of themselves and make ext