逻辑、计算和博弈 (24).pdf

《逻辑、计算和博弈 (24).pdf》由会员分享，可在线阅读，更多相关《逻辑、计算和博弈 (24).pdf（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、LOGIC,COMPUTATION AND GAMES Logic&Games:Two Directions Historical origins of the study of logic Mathematics?Philosophy?Religion?The Law?Dialectics:argumentation is a game Logic as games:use games to understand logic Logical analysis of games Game theory,Zermelos early result Logic of games;use logic

2、 to understand games See posted entry from Stanford Encyclopedia of Philosophy Mnage a Trois Logic Games Computation The Robbers From a Stanford economics class:Ten robbers want to dive their loot:10000 Euro Algorithm:Robber 1 makes a proposal for division,If accepted by at least half of the robbers

3、,the distribution is carried out.If not accepted by at least one half,then this robber drops out,the rest continue.What is the rational proposal to make for Robber 1?Start with 2 robbers left,then work backwards to 10 Games,Actions,Modal Logic Determined Games and Zermelos Theorem determined game:on

4、e of the players has a winning strategy Zermelos Theorem(1913)Each two-player zero-sum game of perfect information with finite bound on depth of histories is determined Motivation Solving games:Checkers,Chess,etc.simple but important result in logic,set theory,game theory,CS Coloring Algorithm Color

5、 winning end nodes for A black,for E white A o o E o E o winE o A o o o winA o o winE winA winE winA historical ancestor of sophisticated search algorithms Modal Fixed Point Logic inductive definition for winnable positions definable in modal calculus basic logic of general induction and recursion e

6、xtension to first-order fixed-point logic LFP(FO)see posted chapter MLOM textbook More generally:game-theoretic equilibria fixedpoint logics Infinite Games and Temporal Logic can extend temporal forcing logic to include specific actions no Zermelo argument:no induction from bottom level Weak Determi

7、nacy:reverse co-inductive perspective i i j j j ji Current trend Temporal logic reasoning about achieving goals Preference and Modal Logic End of game:pay-offs,utilities preference order for each player s i t t is at least as good as s for i(betterness)pre-order(usually assumed connected)Extensive g

8、ame trees are models for modal preference logic M,s|=iff for some t with s i t:M,t|=Complete logic S4.3:S4+modal connectedness axiom Lifting to Preferences Between Kinds Tea vs.Coffee:lifting to sets of worlds Games:needed when comparing moves(sets of outcomes)Options:types of players diversity Pref

9、erence and Goals Goals Properties of outcomes(or histories)often definable in logical language Priority graph goals ordered by relative importance Fact Each priority graph defines a betterness pre-order.Thm Each pre-order is representable by a priority graph.Complete algebra of priority graphs(with

10、operations;|)Andrka,Ryan&Schobbens Backward Induction Relational Algorithm From functional strategies to relations allowing choices improve formulation Rationality players avoid strictly dominated moves Modal Logic of Best Action BI algorithm defines a relation on the game tree gives best actions fo

11、r the active player high-level description of rational behavior Open problem Axiomatize the modal logic of best BI action Belief Interpretation BI is perhaps better seen as a procedure of deliberation that builds expectations/beliefs about how the game will go more on belief in games on Wednesday In

12、 First-Order Fixed Point Logic Lots of recent results on axiomatizing richer topological structures in extended languages Game Equivalence Revisited Earlier power equivalence now fails !new game equivalence assuming rational players Open problem Axiomatize modal logic of matching optimal powers 0,10

13、0 99,99 1,0 0,100 1,0 99,99 1,0 Strategic Form Game Matrices Hawk vs Dove Best response for player i i cannot improve her outcome by unilaterally changing her strategy Nash equilibrium Best response for both players Prisoners Dilemma Pareto optimal no joint outcome better for both players Matrices a

14、s Epistemic Models Learning to get better Epistemic Preference Logic Three basic relations:epistemic uncertainty(know own action,not that of other)your ignorance of my action is my freedom of choice preferences over outcomes for both players modal definition Best Response for i:freei T (:strict pref

15、erence)modal product logics lot known about epistemic case,open problems of axiomatization with preference added Connection with dependence models?(Wednesday)Rineke Verbrugge Rational Dynamics:Solution Procedures Iterated Removal of Strictly Dominated Strategies Iterated Removal of Strictly Dominate

16、d Strategies various algorithms,Epistemic Game Theory Can be analyzed with PAL-style dynamic logics Stable solution arises in the announcement limit rational zone:not necessarily ending in Nash equilibrium Details:see LiG book,Chapters 12,13 A Beautiful Mind PS When are Two Games the Same?Three pers

17、pectives by now:extensive games (actions,modal logic)strategic form games (modal product logics)Compromise:powers (modal forcing logic)Other levels to be discovered:basic powers,.All natural,but different levels of detail,different logical styles of reasoning Further question:How are the levels rela

18、ted?Transformations of games,Translations between logics Student Question:Computational Complexity Could we use these logic-style analyses to find better representations of extensive games that are computationally more tractable?Answer 1 Most clever simplifications occur in practice,not sure if this

19、 has been looked at from a logic perspective.Issue:which essential properties of the game should be preserved(each coarser representation preserves less).Alternative:GDL(Stanford game description language).Answer 2 Will check more&ask some expert colleagues.Cognitive Experiments Theory of Mind Do people normally play according to Backward Induction?Reasoning epistemic-action logic only up to some level Eye-tracking to see where people pay attention Learning to get better BI performance can improve Rineke Verbrugge AI,Groningen Marble Drop Game Worlds/points=vectors