[博弈论书籍].computational.game.theory,yishay mansour,2003

《[博弈论书籍].computational.game.theory,yishay mansour,2003》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ComputationalLearningTheorySpringSemester,2003/4Lecture1:March2Lecturer:YishayMansourScribe:GurYaari,IdanSzpektor1.1IntroductionSeveralfieldsincomputerscienceandeconomicsarefocusedontheanalysisofGametheory.UsuallytheyobserveGameTheoryasawaytosolveoptimizatio

2、nproblemsinsystemswheretheparticipantsactindependentlyandtheirdecisionsaffectthewholesystem.FollowingisalistofresearchfieldsthatutilizeGameTheory:•ArtificialIntelligence(AI)-MultipleAgentssettingswheretheproblemisusuallyacooperationproblemratherthanacompetitio

3、nproblem.•CommunicationNetworks-Distributionofworkwhereeachagentworksindepen-dantly.•ComputerScienceTheory-ThereareseveralsubfieldsthatuseGameTheory:–Maximizingprofitinbidding–Minimumpenaltywhenusingdistributionalenvironment–Complexity–Behavioroflargesystems1

4、.2CourseSyllabus•BasicdefinitionsinGameTheory,concentratingonNashEquilibrium•CoordinationRatio–ComparisonbetweenglobaloptimumandNashEquilibrium–LoadBalancingModels•ComputationofNashEquilibrium–ZeroSumgames(LinearProgramming)–ExistenceofNashEquilibriumingener

5、algames12Lecture1:March2•Regret-playingan“unknown”game.Optimizingaplayer’smoveswhentheplayercanonlyviewherownpayoff•VectorPayoff-thePayofffunctionisavectorandthetargetistoreachaspecifictargetset•CongestionandPotentialgames-gamesthatmodelastateofload•Convergence

6、intoEquilibrium•Other...1.3StrategicGamesAstrategicgameisamodelfordecisionmakingwherethereareNplayers,eachonechoosinganaction.Aplayer’sactionischosenjustonceandcannotbechangedafterwards.EachplayericanchooseanactionaifromasetofactionsAi.letAbethesetofallposs

7、ibleactionvectors×j∈NAj.Thus,theoutcomeofthegameisanactionvector~a∈A.Allthepossibleoutcomesofthegameareknowntoalltheplayersandeachplayerihasapreferencerelationoverthedifferentoutcomesofthegame:~ai~bforevery~a,~b∈A.Therelationstandsiftheplayerprefers~bover~a

8、,orhasequalpreferenceforeither.DefinitionAStrategicGameisatriplethN,(Ai),(i)iwhereNisthenumberofplayers,Aiisthefinitesetofactionsforplayeriandiisthepreferencerelationofplayeri.Wewilluseaslightlydifferen