耶鲁大学公开课 博弈论 原文讲稿仔细整理注释 第3讲.docx

耶鲁大学公开课 博弈论 原文讲稿仔细整理注释 第3讲.docx

《耶鲁大学公开课 博弈论 原文讲稿仔细整理注释 第3讲.docx》由会员分享，可在线阅读，更多相关《耶鲁大学公开课 博弈论 原文讲稿仔细整理注释 第3讲.docx（21页珍藏版）》请在冰点文库上搜索。

耶鲁大学公开课博弈论原文讲稿仔细整理注释第3讲

ECON-159:

GAMETHEORY

Lecture3-IterativeDeletionandtheMedian-VoterTheorem[September12,2007]

Chapter1.IterativeDeletionofDominatedStrategies:

TheMedianVoterTheorem[00:

00:

00]

ProfessorBenPolak:

 Lasttimewetalkedalotabouttheidea--Ididn'tmentionthenamebuthere'ssomejargonforyou--wetalkedabouttheideaofdeletingdominatedstrategies:

lookingatagame;figuringoutwhichstrategiesaredominated;deletingthem;lookingatthegameagain;lookingatwhichstrategiesarenowdominated;deletingthose;andsoonandsoforth.Thisprocessiscalledthe"iterativedeletionofdominatedstrategies."ThisisnotagreattitleforBarry'sbook.Youneedtodobetterthanthattogetthetwohundredandfiftydollars.Thisisaboringtitle,butnevermind.

IterativeDeletionofDominatedStrategies.Theideais--Itembodiestheideaofputtingyourselfinsomeoneelse'sshoesandtryingtofigureoutwhatthey'regoingtodo,andthenthinkaboutthemputtingthemselvesinyourshoes,figuringoutwhatyou'regoingtodo,andsoonandsoforth.Lasttime,wesawalready,thatthisisaverypowerfulidea,inthatgamelasttime.Butwealsosawit'sadangerousideatotaketooliterally:

thatsometimesthiscangetyoutoover-thinktheproblemandactually,asinthatnumbersgamelasttime,thebestchoice,thewinningchoice,mightnotinvolvesomanyrounds.

Wealsosawinthatnumbersgamelasttimethatinsomegames,butbynomeansallgames,insomegamesthisprocessactuallyconvergestoasinglechoice.Inthatnumbersgameitconvergedto1.Soonceagainwhatthisideais--thisideais--youyourselfshouldnotplayadominatedstrategy.Deletethose.Deletethoseforeveryoneelse,becauseeveryoneelseisnotgoingtoplayadominatedstrategy.Deletethose.Lookatthegamewithallthosedominatedstrategiesdeleted.Seeifthereareanystrategiesthatarenowdominated.Deletethose.Lookagain,etc.,etc.Icouldwritethatallup.Wesawitinpracticelasttime.It'sprobablyjusteasiertohavetheideathere.

Onetipaboutthis,trytoidentifyallthedominatedstrategiesofallplayersbeforeyoudelete,thendelete.Thenlookagain.Trytoidentifyallthedominatedstrategiesofallplayersagain,andthendelete.Thatprocesswillpreventyoufromgettingintotrouble.Sotoday,Iwanttobealittlebitlessabstract,ifyoulike,andIwanttolookatanapplication.Iwanttolookatafamousapplicationfrompolitics.

Sowe'regoingtolookatamodelofpolitics.Theideaisgoingtobethis.We'regoingtoimaginethattherearetwocandidates,andwhatthesecandidatesaredoingisthey'rechoosingtheirpoliticalpositionsforanelection.

Sothesearetheplayers,andthestrategiesaregoingtobe-they'regoingtochoosepositionsonaspectrum,onapoliticalspectrum.Tomakelifeeasy,we'regoingtoassumethatthispoliticalspectrumhastenpositions.Soherearethepositions.We'llcallthem1,2,3,4,5,6,7,8,9,and10.Verydifficult.What'stheideahere?

Wehaven'tfinisheddescribingthegame.What'stheidea?

Theideaisthatthesepositionsareleftwingpositionsandthesepositionsarerightwingpositions.（Canpeoplenotseepastthepodium?

Let'sgetitoutoftheway.）

Soyoucouldthinkoftheseextremeleftwingpositions.Thesearepeoplewho,Iguess,theydon'teatanythingexceptforfruitandtheythinkthattreesshouldhavethevote.Theseguysouthere,thesearetheextremerightwingpositions.Sotheythinkthepoorshouldn'thavethevoteandtheyeatimmigrants.I'manimmigrant:

betterbecareful.Thecandidatesherearegoingtotryandchoosepositions.We'regoingtoassume--thisisnotrealistic--we'regoingtoassumefornowthatthereare10%ofthevotersateachofthesepositions.Sothere's10%ofthevotersateachposition.Sotheyareuniformlydistributed.

We'regoingtoassumethatvoterswilleventuallyvotefortheclosestcandidate.Sovotersvotefortheclosestcandidate:

thecandidatewhosepositionisclosesttotheirown.Andwe'llneedatiebreakingassumptionandwe'lldotheobvioustiebreak.Ifthere'satiethenthevoterssplit.Thevotersofthatpositionsplitevenly.Ifthere'satie,halfthevotersatthatpositiongoforoneofthecandidatesandhalfofthemgofortheother.Sohere'sagame,I'vegottheplayers,that'sthecandidates.I'vegotthestrategies,that'sthepoliticalpositions.WhatamImissing?

I'mmissingpayoffs,right?

I'mmissingpayoffs.Itmattersinthisgamealothowwespecifythepayoffsbutwe'regoingtoassumethatthepayoffsarethatthecandidatesaimtomaximizetheirshareofthevote.

Butthat'snottheonlythingwecouldhaveassumed.Wecouldhaveassumedthatalltheyreallycareaboutiswinningandthatwinninggavethemahighpayoffandthatlosinggavethemnothing.I'mgoingtoassumealittlebitmoreandI'mgoingtoassumethat--Ihaven'tspelledmaximizedright,maxwilldo--theywanttomaxtheirshareofthevote.Thereasonthisisn'taterribleassumptionisyoucouldthinkthatgettingahighershareofthevotegivesyouamandate.Or,ifthisisaprimaryelection,alargershareofthevotegivesyouabiggerpushforthenextprimaryorwhatever.Sowe'llassumethatthey'retryingtomaximizetheirshareofthevote.

Sowewanttoknowwhat'sgoingtohappeninthisgame.Itseemslikeaprettynatural,prettyimportantgame.Okay,sogivenwhatwe'velearnedsofarintheclass,anaturalfirstquestiontoaskis:

areanyofthestrategieshere?

Therearetenstrategies1,2,3,4,5,6,7,8,9,10,areanyofthestrategiesdominated?

Areanystrategiesdominated?

Let'sgetsome--Letmegetmymicrophonesupandreadyalittlebit.Soanystrategiesdominated?

Howaboutthisgentlemaninblue?

Sostandupandshout,yeah.

Student:

 Okay,1and10arebothdominated.

ProfessorBenPolak:

 Sothisgentlemanwhosenameis?

Student:

 Steven.

ProfessorBenPolak:

 Stevensays1and10.We'llcomebackto10.You'reright.We'llcomebackto10.Sohesaysthatposition1,strategy1,choosingthemostextremeleftwingpositionisadominatedstrategy.Whatdominatesitbytheway?

Steven,youwanttoshoutitout?

Student:

 2.

ProfessorBenPolak:

 2.Soforexample--Soourconjecturehereisthat2dominates1.That'stheclaim.Let'sjustbecarefulhere,whatdoesitmeantosaythat2dominates1?

Itmeansthatchoosingposition2alwaysgivesmeahighershareofthevotethanchoosingposition1,nomatterwheretheothercandidatepositionsherself.Itdoesnotmean2beats1.

Solet'stakeSteven'sconjectureandseeifit'strue.So,inparticular,let'sstartworkingoutwhatshareofthevotesyou'dgetifyouchoseposition1orposition2,againstdifferentpositionstheotherguycanchoose.So,forexample,whatwe'regoingtodoiswe'regoingtotestdoes2dominate1?

Whilewe'redoingthiswe'llfigureouthowthesepayoffsworkaswell.Well,howaboutversus1.Sosupposetheothercandidatehaschosenposition1.Sotheothercandidatehaschosenposition1.Thenwe'regoingtocomparemypayofffromchoosing1againsttheothercandidate'spayofffromchoosing1.We'regoingtocomparethiswithmypayofffromchoosing2againsttheothercandidatechoosing1.

Let'sfigureoutwhatthatis.Sowhat'smy--somebodycanshoutthisout--what'smyshareofthevoteifIchoose1andtheothercandidatechooses1?

50%.Thatwasprettyeasy,right?

Itmustbeatieforeverybody,soI'llget50%ofthevote.What'smyshareofthevoteifIchoose2andtheothercandidatechooses1?

90%.Hewillgetorshewillgetallthevotersat1.I'llgeteveryoneelse.SoIget90%.Sointhiscasechoosing2isbetterthanchoosing1.Butofcoursewe'renotdoneyet.Wehavetoconsiderotherpossiblepositionsofmyopponent.

Sosupposemyopponentchooses2.Sonowwe'recomparingmychoosing1,whenmyopponentchooses2,andthepayoffIwouldgetifIchoose2whenmyopponentchooses2.Sowhat'smypayoffifIchoose1andmyopponentchooses2?

Igetallthevotersrightontopofmeatposition1andshegetseveryoneelse,isthatright?

SoIget10%.Andwhataboutifwebothchoose2?

50%,everybodyhappywiththat?

So50%inthiscase,andonceagain,2didbetterthan1.Everyonehappywiththat?

Soweshowedthischoicewasbetterandthischoicewasbetter,andwe'regoingtokeepongoing.

Against3:

sonowwe'recomparingmychoosing1versus3andmychoosing2versus3.IfIchoose1against3,whatshareofthevotedoIget?

I'mgoingtogetallthepeopleatposition1andhalfthepeopleatposition2foratotalof15.AndifIchose2against3,whatdoIget?

Iget20,Igetallthepeopleat1andIgetallthepeople2,soIget20%,sowe'reokayagain.Let'sdoonemorejusttoseeapatternhere.SoifIchoose1against4,andcomparingmychoosing2against4.IntheformercaseifIchoose1against4,howmanyvotesdoIget?

Igetallthepeopleat1,andallthepeopleat2,soIget20%ofthevotes,shegetseveryoneelse.AndhereifIchoose2against4,Igetallthepeopleat1,allthepeopleat2,andwhat?

Halfthepeopleat3,sothatcomesoutas25%andonceagainandsoon.

Now,Icouldgoonrightthewaythroughhere,butI'mgoingtostopbecauseitgetstobeabitboringafterawhile.I'mguessingyoucanseeapatternemerginghere.What'sthepatternhere?

What'sthepatternhere?

Somebody?

Where'sthat?

Somebodyraisetheirhandsowecangetamikeoutthere.Canwegetamikeonthisguyinwhite?

Standup,standup,yep,standupandshout.

Student:

 2isalwaysbetterthan1.

ProfessorBenPolak:

 2isalwaysbetterthan1,butwecanseemorethanthatinthepattern.That'sright