(original) (raw)
��ࡱ�>�� �������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������*c�(���� J��/� 0����DArialngs�����.�����0�:A 0��DComic Sans MS�.�����0�:A 0�B �DWingdings MS�.�����0�:A 0�� �A��� .� @�n��?" d�d@������� @@``�� ����p��� #;>[:\ �������������������������C��� �0���A���A�0� ��33�@�33�������3����ʚ;���ʚ;�g��4IdId �:A 0P�������p�pp�@ <�4ddddL��$ 0���.�� �8�0�___PPT10� ��?� � %�EV��P��Introduction to Game Theory�$����8Networked Life CSE 112 Spring 2005 Prof. Michael Kearns �9Z9��=�� Game Theory� (�����A mathematical theory designed to model: how rational individuals should behave when individual outcomes are determined by collective behavior strategic behavior Rational usually means selfish --- but not always Rich history, flourished during the Cold War Traditionally viewed as a subject of economics Subsequently applied by many fields evolutionary biology, social psychology Perhaps the branch of pure math most widely examined outside of the hard sciences �V)y�(U)�����:� ��� � ��� ������(�U�����Q��$Prisoner s Dilemma�(����dCooperate = deny the crime; defect = confess guilt of both Claim that (defect, defect) is an equilibrium: if I am definitely going to defect, you choose between -10 and -8 so you will also defect same logic applies to me Note unilateral nature of equilibrium: I fix a behavior or strategy for you, then choose my best response Claim: no other pair of strategies is an equilibrium But we would have been so much better off cooperating& �8js'ClG��������� ��������������������������� ��������� ����C�_� �����R��Penny Matching�(����eWhat are the equilibrium strategies now? There are none! if I play heads then you will of course play tails but that makes me want to play tails too which in turn makes you want to play heads etc. etc. etc. But what if we can each (privately) flip coins? the strategy pair (1/2, 1/2) is an equilibrium Such randomized strategies are called mixed strategies�*9�0079����������������������������������$� ������������&������S��The World According to Nash�(����4If > 2 actions, mixed strategy is a distribution on them e.g. 1/3 rock, 1/3 paper, 1/3 scissors Might also have > 2 players A general mixed strategy is a vector P = (P[1], P[2],& P[n]): P[i] is a distribution over the actions for player i assume everyone knows all the distributions P[j] but the coin flips used to select from P[i] known only to i P is an equilibrium if: for every i, P[i] is a best response to all the other P[j] Nash 1950: every game has a mixed strategy equilibrium no matter how many rows and columns there are in fact, no matter how many players there are Thus known as a Nash equilibrium A major reason for Nash s Nobel Prize in economics �69'Z�;7\T$� ��� �'�Z�<����� ���#����������;�7 � \ � ����3����t�^+7&���T��Facts about Nash Equilibria�(��� ��ZWhile there is always at least one, there might be many zero-sum games: all equilibria give the same payoffs to each player non zero-sum: different equilibria may give different payoffs! Equilibrium is a static notion does not suggest how players might learn to play equilibrium does not suggest how we might choose among multiple equilibria Nash equilibrium is a strictly competitive notion players cannot have pre-play communication bargains, side payments, threats, collusions, etc. not allowed Computing Nash equilibria for large games is difficult ��8�|2l7���������������#����2����������l� � ��. � � � �PL > � � !��U��Hawks and Doves�(�����Two parties confront over a resource of value V May simply display aggression, or actually have a fight Cost of losing a fight: C > V Assume parties are equally likely to win or lose There are three Nash equilibria: (hawk, dove), (dove, hawk) and (V/C hawk, V/C hawk) Alternative interpretation for C >> V: the Kansas Cornfield Intersection game (a.k.a. Chicken) hawk = speed through intersection, dove = yield���4'h���������������������������'���������2��� ���V��Board Games and Game Theory�(����zWhat does game theory say about richer games? tic-tac-toe, checkers, backgammon, go,& these are all games of complete information with state incomplete information: poker Imagine an absurdly large game matrix for chess: each row/column represents a complete strategy for playing strategy = a mapping from every possible board configuration to the next move for the player number of rows or columns is huge --- but finite! Thus, a Nash equilibrium for chess exists! it s just completely infeasible to compute it note: can often push randomization inside the strategy �j.}3�+i.�?���������3�U�"���S�+�#����?����W��Repeated Games�(�����Nash equilibrium analyzes one-shot games we meet for the first time, play once, and separate forever Natural extension: repeated games we play the same game (e.g. Prisoner s Dilemma) many times in a row like a board game, where the state is the history of play so far strategy = a mapping from the history so far to your next move So repeated games also have a Nash equilibrium may be different from the one-shot equilibrium! depends on the game and details of the setting We are approaching learning in games natural to adapt your behavior (strategy) based on play so far �Z+<"�/_%?+�<��������/�_� � � �� � ? � � ��X��6Repeated Prisoner s Dilemma�(�����If we play for R rounds, and both know R: (always defect, always defect) still the only Nash equilibrium argue by backwards induction If uncertainty about R is introduced (e.g. random stopping): cooperation and tit-for-tat can become equilibria If computational restrictions are placed on our strategies: as long as we re too feeble to count, cooperative equilibria arise formally: < log(R) states in a finite automaton a form of bounded rationality ��*\=3<�*������ ���?�=� ���� ����<�����Y�������>� p A��Y��The Folk Theorem�(�����Take any one-shot, two-player game Suppose that (u,v) are the (expected) payoffs under some mixed strategy pair (P[1],P[2]) for the two players (P[1], P[2]) not necessarily a Nash equilibrium but (u,v) gives better payoffs than the security levels security level: what a player can get no matter what the other does example: sec. level is (-8, -8) in Prisoner s Dilemma; (-1,-1) is better Then there is always a Nash equilibrium for the infinite repeated game giving payoffs (u,v) makes use of the concept of threats Partial resolution of the difficulties of Nash equilibria& �8�hDI\$;�� ����H����D����������������� �0����$� � � �� � ��4 � ���P1�U ��Z��Correlated Equilibrium�(����<In a Nash equilibrium (P[1],P[2]): player 2 knows the distribution P[1] but doesn t know the random bits player 1 uses to select from P[1] equilibrium relies on private randomization Suppose now we also allow public (shared) randomization so strategy might say things like if private bits = 100110 and shared bits = 110100110, then play hawk Then two strategies are in correlated equilibrium if: knowing only your strategy and the shared bits, my strategy is a best response, and vice-versa Nash is the special case of no shared bits ��#�8i6_.#�� ���a���������i���������� ����6�.���[��Hawks and Doves Revisited�(�����There are three Nash equilibria: (hawk, dove), (dove, hawk) and (V/C hawk, V/C hawk) Alternative interpretation for C >> V: the Kansas Cornfield Intersection game (a.k.a. Chicken) hawk = speed through intersection, dove = yield Correlated equilibrium: the traffic signal if the shared bit is green to me, I am playing hawk if the shared bit is red to me, I will play dove you play the symmetric strategy splits waiting time between us --- a different outcome than Nash�!4'h+�!��������������������������'���������2������ � � �� � � ���\��Correlated Equilibrium Facts�(����6Always exists all Nash equilibria are correlated equilibria all probability distributions over Nash equilibria are C.E. and some more things are C.E. as well a broader concept than Nash Technical advantages of correlated equilibria: often easier to compute than Nash Conceptual advantages: correlated behavior is a fact of the real world model a limited form of cooperation more general cooperation becomes extremely complex and messy Breaking news (late 90s now): CE is the natural convergence notion for rational learning in games! ��Z�Z/Z"ZZ�Z ZGZZ�������/����� ��8����R� � G � � �P ) o 5��_��Next Up�(����bHave so far examined simple games between two players Strategic interaction on the smallest network : two vertices with a single link between them much richer interaction than just info transmission, messages, etc. Classical game theory generalizes to many players e.g. Nash equilibria always exist in multi-player matrix games but this fails to capture/exploit/examine structured interaction We need specific models for networked games: games on networks: local interaction shared information: economies, financial markets voting systems evolutionary games ��gq2�-zg�q�2�i� ��� �-�z��� /������'��(��)��*��+��,��-��.��/��0��1��2��5��� � `� ���������33�����`� ��������S��f�3�f`� ������������33��g�`� ������������f��`� ���www���3���PP��`� �����ZX���dbmo����`� ����\�ғ�3�y`���Ӣ`� ����3f���3f��f����`� ���3f����3�F�Kf����`� hk]���www�����������f�ܹ`� ff����>>\���`Y{ff�������`� R>&���- ����{p�_/̴����>��?" d�d@�������,�|��?" d�d�@������� � � �" �@� �`��� �n��?" d�d@������� @@``��P�R @ ` �`� p�>��> �����f�( � ��� � � �6��������� �� `}�� � �T�� Click to edit Master title style�!� !� � � �0��������� �� `�� � ���RClick to edit Master text styles Second level Third level Fourth level Fifth level�! � S� � � �0�,������� �^ `��� � �>��*��� � � �0�L������� �^����� � �@��*��� � � �0�p������� �^ `��� � �@��*���H � � �0�������h�� ?� ���������33������8�0�___PPT10��.f���6�� �Default Design���� 0 z�r0�,� �( � �,�� �, � �0���A����� �P �� A �P��*� �� �� �, � �0���A����� �� � �� A �R��*� �� �d �, c �$��� ?��� �� A� �, � �0�P�A����� �� �0��� A ���RClick to edit Master text styles Second level Third level Fourth level Fifth level�! � S�� �, � �6��A������ �_P�� A �P��*� �� �� �, � �6�l�A������ �_� ��� A �R��*� �� �H �, � �0���h������ ?� ���������33������8�0�___PPT10��.-��I�<���� �����0�( � ���x �� c �$��_F�������� F � ��x �� c �$�ķ������P`� �� F � ��H �� � �0�������h�� ?� ���������33����������___PPT10�i�.f��P���+D�='� �����=� @B� +��� � �����9 �\�( � � �x � c �$� �F����`��p�� F � �� � c �$��F����@0�P�<$� 0� F � ��H � � �0�������h�� ?� ���������33����������___PPT10���.f����b�+�F��D� '� �����=� @B� D��'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* )%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* )P%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* P�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* ��%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* ��%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* �%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* 0%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* 0T%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* T|%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��* |�%�(�+8+0+ � +�� � �' � � �� �( � ��x � c �$��������`��p�� � � �� � c �$�\�������0���<$� 0� � � ��4 �l �@`� � �#"����#�p0���� � � �<���F������?�� �� �j��-8, -8�2������ @`��� � � �<�d�F������?���� � �n�� -0.25, -10�2 ������ @`��� � � �<�t�F������?�@��� �R��defect����� @`��� � � �<�H�F������?�� �� �n�� -10, -0.25�2 ������ @`��� � � �<�(�F������?���� � �j��-1, -1�2������ @`��� � � �<�h�F������?�@��� �U�� cooperate� ���� @`��� � � �<�m������?�� `� �R��defect����� @`��� � � �<�� m������?��`� � �U�� cooperate� ���� @`�� � � �<��m������?�@`�� �>���� @`��`B � � �0����o�� ?��@``�ZB � s �*����1� ?��@���ZB � s �*����1� ?��@���`B � � �0����o�� ?��@���`B � � �0����o�� ?��@`@��ZB � s �*����1� ?���`���ZB � s �*����1� ?��� `� ��`B � � �0����o�� ?��`��H � � �0�������h�� ?� ���������33������c�[�___PPT10�;�.f����b�+�[W_D��'� �����=� @B� D�'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*;%�(�D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*;j%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*j�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*��%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*G%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*G|%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*|�%�(�+8+0+m +��� �( � �� � ��� �( � ��x � c �$�0m����`��p�� m � �� � c �$��m�����0���<$� 0� m � �� �r �@`� �# � �#"����#�p0���� � � �<�<bm������������������������?���������� ������������ �h������������������1,="" 0���2������������������������������������������������������="" @`��������="" �����="" ���� �<���������<om������������������������?���������������� ������="" �h������������������0,="" 1���2������������������������������������������������������="" �����="" ���� �<���������0vm������������������������?���������@������������="" �q������������������tails���������������������������������������="" �����="" ���� �<���������txm������������������������?���������� ������������="" ����="" �="" ���� �<���������hjm������������������������?���������������� ������="" ���� �<���������tdm������������������������?���������@������������="" �q������������������heads���������������������������������������="" ���� �="" ���� �<���������x|m������������������������?���������� ��`���������="" ���� �<���������@�m������������������������?������������`��� ������="" @`�������="" ���� �<�����������m������������������������?���������@��`���������="" �="">���� @`��`B � � �0����o�� ?��@``�ZB � s �*����1� ?��@���ZB � s �*����1� ?��@���`B � � �0����o�� ?��@���`B � � �0����o�� ?��@`@��ZB � s �*����1� ?���`���ZB � s �*����1� ?��� `� ��`B � � �0����o�� ?��`��H � � �0�������h�� ?� ���������33����������___PPT10���.f����b�+�[W_D�''� �����=� @B� D��'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*)%�(�D�'� �=�%�(�����D�M'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*)9%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*9l%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*l�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*��%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�/%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*/f%�(�+8+0+m +��� �) ��� �$�\�( � �$�x �$ c �$���m����`��p�� m � �� �$ c �$��km�����0���<$� 0� m � ��H �$ � �0�������h�� ?� ���������33����������___PPT10���.f����b�+�F��D�4'� �����=� @B� D��'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$9%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$9`%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$`|%�(�D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$|�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$� %�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$ ^%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$^v%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$v�%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$D%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$De%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*$e�%�(�+8+0+$m +�p� �* ���0 �,�\�( � �,�x �, c �$���m����`��p�� m � �� �, c �$���m����@0�P�<$� 0� m � ��H �, � �0�������h�� ?� ���������33������L�D�___PPT10�$�.f����b�+�F��D��'� �����=� @B� D�{'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*,8%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*,8|%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*,|�%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*,��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*,�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*,V%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*,V�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*,��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*,��%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*,�+%�(�+8+0+,m +�e!� �+ � �� P �4�� �( � �4�x �4 c �$�4�m����`��p�� m � �� �4 c �$�0�m�����0���<$� 0� m � ��& �l �0p�� �4 �#"����#�pp��� �4 � �<���m������?�0��� �l��V/2, V/2�2 ������ @`��� �4 � �<�D�m������?�� �0� �h��0, V�2������ @`��� �4 � �<���m������?�0�� � �P��dove����� @`��� �4 � �<�:������?�0��� �h��V, 0�2������ @`��� � 4 � �<� :������?�� �0� �t��(V-C)/2, (V-C)/2�2������ @`��� � 4 � �<��:������?�0�� � �P��hawk����� @`��� � 4 � �<�t#:������?�0p�� �P��dove����� @`��� � 4 � �<��,:������?�� p0� �P��hawk����� @`�� � 4 � �<��4:������?�0p� � �>���� @`��`B �4 � �0����o�� ?��0p�p�ZB �4 s �*����1� ?��0����ZB �4 s �*����1� ?��0����`B �4 � �0����o�� ?��0����`B �4 � �0����o�� ?��0p0��ZB �4 s �*����1� ?��� p� ��ZB �4 s �*����1� ?��0p0��`B �4 � �0����o�� ?���p���H �4 � �0�������h�� ?� ���������33������� �___PPT10���.f����b�+�[W_D�'� �����=� @B� D�B'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*40%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*40h%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*4h�%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*4��%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*4��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*4� %�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*4 3%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*43k%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*4k�%�(�+8+0+4: +�Y� �, ���p �<�\�( � �<�x �< c �$��K:����`��p�� : � �� �< c �$��W:����@0�P�<$� 0� : � ��H �< � �0�������h�� ?� ���������33������5�-�___PPT10� �.f����b�+�F��D�'� �����=� @B� D�d'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*<.%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*<.V%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*<V�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*<��%�(�D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*<��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*<�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*<v%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*<v�%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*<��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*<�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*<<%�(�+8+0+<m +� � �- ���� �D�\�( � �D�x �D c �$��h:����`��p�� : � �� �D c �$��i:����0�0�<$� 0� : � ��H �D � �0�������h�� ?� ���������33����������___PPT10���.f����b�+�F��D�Y'� �����=� @B� D�'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*D+%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*D+g%�(�D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*Dg�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*D��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*D�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*DO%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*DO~%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*D~�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*D��%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*D�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*DA%�(�+8+0+D: +�'� �. ���� �L�\�( � �L�x �L c �$�`�:����`��p�� : � �� �L c �$�\�:����0�0�<$� 0� : � ��H �L � �0�������h�� ?� ���������33���������___PPT10���.f����b�+�F��D�w'� �����=� @B� D�2'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*L*%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*L*i%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*Li�%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*L��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*L��%�(�D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*L�2%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*L2u%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*Lu�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*L��%�(�+8+0+L: +��� �/ ���� �T�\�( � �T�x �T c �$��A����`��p�� A � �� �T c �$��A����0�0�<$� 0� A � ��H �T � �0�������h�� ?� ���������33����������___PPT10���.f����b�+�[W_D�''� �����=� @B� D��'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*T#%�(�D�'� �=�%�(�����D�M'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*T#�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*T��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*T��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*T�<%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*T<�%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*T��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*T�%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*T@%�(�+8+0+Tm +��� �0 ���� �\�\�( � �\�x �\ c �$��+A����`��p�� A � �� �\ c �$��,A����0�0�<$� 0� A � ��H �\ � �0�������h�� ?� ���������33����������___PPT10���.f����b�+�F��D�''� �����=� @B� D��'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*\#%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*\#J%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*\J�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*\��%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*\��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*\�\%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*\\�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*\��%�(�D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*\�%�(�+8+0+\A +�� � �1 �� �d� �( � �d�x �d c �$�,KA����`��p�� A � �� �d c �$�LA�����0���<$� 0� A � ��, �r �0p�� �d# � �#"����#�pp��� �d � �<�XWA������?�0��� �l��V/2, V/2�2 ������ @`��� �d � �<�bA������?�� �0� �h��0, V�2������ @`��� �d � �<�kA������?�0�� � �P��dove����� @`��� �d � �<��tA������?�0��� �h��V, 0�2������ @`��� � d � �<�`A������?�� �0� �t��(V-C)/2, (V-C)/2�2������ @`��� � d � �<���A������?�0�� � �P��hawk����� @`��� � d � �<��yA������?�0p�� �P��dove����� @`��� � d � �<���A������?�� p0� �P��hawk����� @`�� � d � �<�P�A������?�0p� � �>���� @`��`B �d � �0����o�� ?��0p�p�ZB �d s �*����1� ?��0����ZB �d s �*����1� ?��0����`B �d � �0����o�� ?��0����`B �d � �0����o�� ?��0p0��ZB �d s �*����1� ?��� p� ��ZB �d s �*����1� ?��0p0��`B �d � �0����o�� ?���p���H �d � �0�������h�� ?� ���������33����������___PPT10�t�.f����b�+�F��D�'� �����=� @B� D��'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*d!%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*d!U%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*dU|%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*d|�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*d��%�(�D�'� �=�%�(�����D�M'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*d�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*dC%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*dCt%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*dt�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*d��%�(�+8+0+dA +�;� �2 ���0 �l�\�( � �l�x �l c �$��.F����`��p�� F � �� �l c �$�|/F����0�0�<$� 0� F � ��H �l � �0�������h�� ?� ���������33��������___PPT10���.f����b�+�F��D�'� �����=� @B� D�F'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�'� �=�%�(�����D�M'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*l%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*l<%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*l<x%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*lx�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*l��%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*l��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*l� %�(�D� '� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*l "%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*l"R%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*lRv%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*lv�%�(�D��'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*l��%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*l�%�(�+8+0+lF +��� �5 ���� ���\�( � ���x �� c �$� �A����`��p�� A � �� �� c �$��A����0�0�<$� 0� A � ��H �� � �0�������h�� ?� ���������33������~�v�___PPT10�V�.f����b�+�[W_D��'� �����=� @B� D�'� ����=� @B�A�?%�,(� <� +O%�,(� <� +D�A'� �=�%�(�����D��'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�6%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�6g%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�g�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�D�s'� �=�%�(�����D�'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�� %�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*� I%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�I�%�(�D�'� �=�%�(�����D�M'� =�%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*���%�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�� %�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*� %�(�D�'� =�A@B��B��B��B�0B�%�(�D��'� =�1�:�B�visible*�o3�>�+B�#style.visibility<��*�/%�(�+8+0+�A +��= 0 �����(�( � ��^ � S ���,���� �� A�� � c �$���A��,��� �0��� A ��� �H � � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��Q 0 ��� ��(�( � ��^ � S ���,���� �� A�� � c �$�e��,��� �0��� A ��� �H � � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��R 0 �� � �(�( � � �^ � S ���,���� �� e�� � c �$��e��,��� �0��� e ��� �H � � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��S 0 �� �(�(�( � �(�^ �( S ���,���� �� e�� �( c �$�, e��,��� �0��� e ��� �H �( � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��T 0 ��@ �0�(�( � �0�^ �0 S ���,���� �� A�� �0 c �$��e��,��� �0��� A ��� �H �0 � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��U 0 ��` �8�(�( � �8�^ �8 S ���,���� �� e�� �8 c �$�he��,��� �0��� e ��� �H �8 � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��V 0 ��� �@�(�( � �@�^ �@ S ���,���� �� e�� �@ c �$��e��,��� �0��� e ��� �H �@ � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��W 0 ��� �H�(�( � �H�^ �H S ���,���� �� e�� �H c �$�X!e��,��� �0��� e ��� �H �H � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��X 0 ��� �P�(�( � �P�^ �P S ���,���� �� e�� �P c �$��&e��,��� �0��� e ��� �H �P � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��Y 0 ��� �X�(�( � �X�^ �X S ���,���� �� e�� �X c �$�p,e��,��� �0��� e ��� �H �X � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��Z 0 �� �`�(�( � �`�^ �` S ���,���� �� e�� �` c �$��1e��,��� �0��� e ��� �H �` � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��[ 0 �� �h�(�( � �h�^ �h S ���,���� �� e�� �h c �$��7e��,��� �0��� e ��� �H �h � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��\ 0 ��@ �p�(�( � �p�^ �p S ���,���� �� e�� �p c �$�=e��,��� �0��� e ��� �H �p � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8��_ 0 ��� ���(�( � ���^ �� S ���,���� �� e�� �� c �$��Be��,��� �0��� e ��� �H �� � �0���h������ ?� ���������33������8�0�___PPT10��.���`�8r� 2cJ�l� qu4���r�pI�T���t���������$��M<�^T4��hT�l}t�K���G���� ����Qm��_�������Oh��+'��0� `h�� �� � � ����Networked Nature of SocietyCISCIS125Microsoft PowerPointoci@���V@P��g��@�����0��G������g h0 ������-����- @ !��������--'������@BComic Sans MS-. �02 ��Introduction to Game Theory"'#.��"System���-�����@BComic Sans MS-. 33�2 �dNetworked Life .-�����@BComic Sans MS-. 33�2 ��CSE 112.-�����@BComic Sans MS-. 33�2 ��Spring .-�����@BComic Sans MS-. 33� 2 � 2005.-�����@BComic Sans MS-. 33�%2 1Prof. Michael Kearns" .-�����՜.��+,��0@������� � �� � ��On-screen ShowUniversity of PAu��{ ArialComic Sans MS WingdingsDefault DesignIntroduction to Game Theory Game TheoryPrisoner�s DilemmaPenny MatchingThe World According to NashFacts about Nash EquilibriaHawks and DovesBoard Games and Game TheoryRepeated GamesRepeated Prisoner�s DilemmaThe Folk TheoremCorrelated EquilibriumHawks and Doves RevisitedCorrelated Equilibrium FactsNext Up Fonts UsedDesign Template Slide Titles�_�����CISCIS !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~������������������������������������������������������������������������������������������������������������������������������������ ���� �������������������� ������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������Root Entry����������d�O�����)�����Current User������������SummaryInformation(��������PowerPoint Document(�����DocumentSummaryInformation8������������ ������������������������������������</bm������������������������?���������� ������������>