Misplaced Pages

#931068

109-570: Modal logics are formal systems that include unary operators such as ◊ {\displaystyle \Diamond } and ◻ {\displaystyle \Box } , representing possibility and necessity respectively. For instance the modal formula ◊ P {\displaystyle \Diamond P} can be read as "possibly P {\displaystyle P} " while ◻ P {\displaystyle \Box P} can be read as "necessarily P {\displaystyle P} ". In

218-460: A decision procedure for deciding whether a given WFF is a theorem or not. The point of view that generating formal proofs is all there is to mathematics is often called formalism . David Hilbert founded metamathematics as a discipline for discussing formal systems. Any language that one uses to talk about a formal system is called a metalanguage . The metalanguage may be a natural language, or it may be partially formalized itself, but it

327-419: A derivation is merely a logical consequence of the lines that precede it. There should be no element of any interpretation of the language that gets involved with the deductive nature of the system. The logical consequence (or entailment) of the system by its logical foundation is what distinguishes a formal system from others which may have some basis in an abstract model. Often the formal system will be

436-464: A (possibly asymmetric) zero-sum game by adding a dummy player (often called "the board") whose losses compensate the players' net winnings. Simultaneous games are games where both players move simultaneously, or instead the later players are unaware of the earlier players' actions (making them effectively simultaneous). Sequential games (or dynamic games) are games where players do not make decisions simultaneously, and player's earlier actions affect

545-481: A clean notion of analytic proof ). More complex calculi have been applied to modal logic to achieve generality. Analytic tableaux provide the most popular decision method for modal logics. Modalities of necessity and possibility are called alethic modalities. They are also sometimes called special modalities, from the Latin species . Modal logic was first developed to deal with these concepts, and only afterward

654-439: A collection of characteristics relevant to the player such as their preferences and details about them. There must be a state for every set of features that some player believes may exist. For example, where Player 1 is unsure whether Player 2 would rather date her or get away from her, while Player 2 understands Player 1's preferences as before. To be specific, supposing that Player 1 believes that Player 2 wants to date her under

763-579: A combined epistemic-deontic logic could use the formula [ K ] ⟨ D ⟩ P {\displaystyle [K]\langle D\rangle P} read as "I know P is permitted". Systems of modal logic can include infinitely many modal operators distinguished by indices, i.e. ◻ 1 {\displaystyle \Box _{1}} , ◻ 2 {\displaystyle \Box _{2}} , ◻ 3 {\displaystyle \Box _{3}} , and so on. The standard semantics for modal logic

872-412: A discounted differential game over an infinite time interval. Evolutionary game theory studies players who adjust their strategies over time according to rules that are not necessarily rational or farsighted. In general, the evolution of strategies over time according to such rules is modeled as a Markov chain with a state variable such as the current strategy profile or how the game has been played in

981-530: A formula. For instance, consider a model M {\displaystyle {\mathfrak {M}}} whose accessibility relation is reflexive . Because the relation is reflexive, we will have that M , w ⊨ P → ◊ P {\displaystyle {\mathfrak {M}},w\models P\rightarrow \Diamond P} for any w ∈ G {\displaystyle w\in G} regardless of which valuation function

1090-495: A game many times within their lifetime and, consciously or unconsciously, occasionally adjust their strategies. Individual decision problems with stochastic outcomes are sometimes considered "one-player games". They may be modeled using similar tools within the related disciplines of decision theory , operations research , and areas of artificial intelligence , particularly AI planning (with uncertainty) and multi-agent system . Although these fields may have different motivators,

1199-426: A high-level approach as it describes only the structure and payoffs of coalitions, whereas non-cooperative game theory also looks at how strategic interaction will affect the distribution of payoffs. As non-cooperative game theory is more general, cooperative games can be analyzed through the approach of non-cooperative game theory (the converse does not hold) provided that sufficient assumptions are made to encompass all

SECTION 10

#1732776443932

1308-443: A language can be written, and that of analytic grammars (or reductive grammar ), which are sets of rules for how a string can be analyzed to determine whether it is a member of the language. A deductive system , also called a deductive apparatus , consists of the axioms (or axiom schemata ) and rules of inference that can be used to derive theorems of the system. Such deductive systems preserve deductive qualities in

1417-563: A letter attributed to Charles Waldegrave, an active Jacobite and uncle to British diplomat James Waldegrave , analyzed a game called " le her ". Waldegrave provided a minimax mixed strategy solution to a two-person version of the card game, and the problem is now known as the Waldegrave problem . In 1838, Antoine Augustin Cournot provided a model of competition in oligopolies . Though he did not refer to it as such, he presented

1526-532: A logical system is Peano arithmetic . The standard model of arithmetic sets the domain of discourse to be the nonnegative integers and gives the symbols their usual meaning. There are also non-standard models of arithmetic . Early logic systems includes Indian logic of Pāṇini , syllogistic logic of Aristotle, propositional logic of Stoicism, and Chinese logic of Gongsun Long (c. 325–250 BCE) . In more recent times, contributors include George Boole , Augustus De Morgan , and Gottlob Frege . Mathematical logic

1635-447: A model M {\displaystyle {\mathfrak {M}}} : According to this semantics, a formula is necessary with respect to a world w {\displaystyle w} if it holds at every world that is accessible from w {\displaystyle w} . It is possible if it holds at some world that is accessible from w {\displaystyle w} . Possibility thereby depends upon

1744-420: A person would not somehow be prevented from doing so on account of their height and name), but not alethically true unless you match that description, and not epistemically true if it is known that fourteen-foot-tall human beings have never existed. From the other direction, Jones might say, (3) "It is possible that Goldbach's conjecture is true; but also possible that it is false", and also (4) "if it

1853-416: A player benefits only at the equal expense of others). Poker exemplifies a zero-sum game (ignoring the possibility of the house's cut), because one wins exactly the amount one's opponents lose. Other zero-sum games include matching pennies and most classical board games including Go and chess . Many games studied by game theorists (including the famed prisoner's dilemma) are non-zero-sum games, because

1962-526: A prefixed "box" (□ p ) whose scope is established by parentheses. Likewise, a prefixed "diamond" (◇ p ) denotes "possibly p ". Similar to the quantifiers in first-order logic , "necessarily p " (□ p ) does not assume the range of quantification (the set of accessible possible worlds in Kripke semantics ) to be non-empty, whereas "possibly p " (◇ p ) often implicitly assumes ◊ ⊤ {\displaystyle \Diamond \top } (viz.

2071-466: A probability of 1/2 and get away from her under a probability of 1/2 (this evaluation comes from Player 1's experience probably: she faces players who want to date her half of the time in such a case and players who want to avoid her half of the time). Due to the probability involved, the analysis of this situation requires to understand the player's preference for the draw, even though people are only interested in pure strategic equilibrium. Games in which

2180-436: A set of inference rules . In 1921, David Hilbert proposed to use formal systems as the foundation of knowledge in mathematics . The term formalism is sometimes a rough synonym for formal system , but it also refers to a given style of notation , for example, Paul Dirac 's bra–ket notation . A formal system has the following: A formal system is said to be recursive (i.e. effective) or recursively enumerable if

2289-722: A solution that is the Nash equilibrium of the game in his Recherches sur les principes mathématiques de la théorie des richesses ( Researches into the Mathematical Principles of the Theory of Wealth ). In 1883, Joseph Bertrand critiqued Cournot's model as unrealistic, providing an alternative model of price competition which would later be formalized by Francis Ysidro Edgeworth . In 1913, Ernst Zermelo published Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels ( On an Application of Set Theory to

SECTION 20

#1732776443932

2398-416: A standard method in game theory and mathematical economics . Von Neumann's work in game theory culminated in his 1944 book Theory of Games and Economic Behavior , co-authored with Oskar Morgenstern . The second edition of this book provided an axiomatic theory of utility , which reincarnated Daniel Bernoulli's old theory of utility (of money) as an independent discipline. This foundational work contains

2507-466: A transparent way of modeling certain concepts such as the evidence or justification one has for one's beliefs. Topological semantics is widely used in recent work in formal epistemology and has antecedents in earlier work such as David Lewis and Angelika Kratzer 's logics for counterfactuals . The first formalizations of modal logic were axiomatic . Numerous variations with very different properties have been proposed since C. I. Lewis began working in

2616-427: A wider variety of games than the criterion proposed by von Neumann and Morgenstern. Nash proved that every finite n-player, non-zero-sum (not just two-player zero-sum) non-cooperative game has what is now known as a Nash equilibrium in mixed strategies. Game theory experienced a flurry of activity in the 1950s, during which the concepts of the core , the extensive form game , fictitious play , repeated games , and

2725-677: Is Hex . A related field of study, drawing from computational complexity theory , is game complexity , which is concerned with estimating the computational difficulty of finding optimal strategies. Research in artificial intelligence has addressed both perfect and imperfect information games that have very complex combinatorial structures (like chess, go, or backgammon) for which no provable optimal strategies have been found. The practical solutions involve computational heuristics, like alpha–beta pruning or use of artificial neural networks trained by reinforcement learning , which make games more tractable in computing practice. Much of game theory

2834-547: Is non-cooperative if players cannot form alliances or if all agreements need to be self-enforcing (e.g. through credible threats ). Cooperative games are often analyzed through the framework of cooperative game theory , which focuses on predicting which coalitions will form, the joint actions that groups take, and the resulting collective payoffs. It is different from non-cooperative game theory which focuses on predicting individual players' actions and payoffs by analyzing Nash equilibria . Cooperative game theory provides

2943-458: Is possible that it is raining outside" – in the sense of epistemic possibility – then that would weigh on whether or not I take the umbrella. But if you just tell me that "it is possible for it to rain outside" – in the sense of metaphysical possibility – then I am no better off for this bit of modal enlightenment. Some features of epistemic modal logic are in debate. For example, if x knows that p , does x know that it knows that p ? That

3052-442: Is true, then it is necessarily true, and not possibly false". Here Jones means that it is epistemically possible that it is true or false, for all he knows (Goldbach's conjecture has not been proven either true or false), but if there is a proof (heretofore undiscovered), then it would show that it is not logically possible for Goldbach's conjecture to be false—there could be no set of numbers that violated it. Logical possibility

3161-401: Is a topological space and V {\displaystyle V} is a valuation function which maps each atomic formula to some subset of X {\displaystyle X} . The basic interior semantics interprets formulas of modal logic as follows: Topological approaches subsume relational ones, allowing non-normal modal logics . The extra structure they provide also allows

3270-458: Is a deductive system (most commonly first order logic ) together with additional non-logical axioms . According to model theory , a logical system may be given interpretations which describe whether a given structure - the mapping of formulas to a particular meaning - satisfies a well-formed formula. A structure that satisfies all the axioms of the formal system is known as a model of the logical system. A logical system is: An example of

3379-468: Is a form of alethic possibility; (4) makes a claim about whether it is possible (i.e., logically speaking) that a mathematical truth to have been false, but (3) only makes a claim about whether it is possible, for all Jones knows, (i.e., speaking of certitude) that the mathematical claim is specifically either true or false, and so again Jones does not contradict himself. It is worthwhile to observe that Jones

Modal logic - Misplaced Pages Continue

3488-604: Is a matter of dispute. Philosophers also disagree over whether metaphysical truths are necessary merely "by definition", or whether they reflect some underlying deep facts about the world, or something else entirely. Epistemic modalities (from the Greek episteme , knowledge), deal with the certainty of sentences. The □ operator is translated as "x is certain that…", and the ◇ operator is translated as "For all x knows, it may be true that…" In ordinary speech both metaphysical and epistemic modalities are often expressed in similar words;

3597-446: Is also used to refer to a practical approach developed by Nigel Howard, whereby a situation is framed as a strategic game in which stakeholders try to realize their objectives by means of the options available to them. Subsequent developments have led to the formulation of confrontation analysis . Mean field game theory is the study of strategic decision making in very large populations of small interacting agents. This class of problems

3706-424: Is called the relational semantics . In this approach, the truth of a formula is determined relative to a point which is often called a possible world . For a formula that contains a modal operator, its truth value can depend on what is true at other accessible worlds. Thus, the relational semantics interprets formulas of modal logic using models defined as follows. The set W {\displaystyle W}

3815-475: Is captured in the different representations discussed above. Often, normal form is used to represent simultaneous games, while extensive form is used to represent sequential ones. The transformation of extensive to normal form is one way, meaning that multiple extensive form games correspond to the same normal form. Consequently, notions of equilibrium for simultaneous games are insufficient for reasoning about sequential games; see subgame perfection . In short,

3924-413: Is concerned with finite, discrete games that have a finite number of players, moves, events, outcomes, etc. Many concepts can be extended, however. Continuous games allow players to choose a strategy from a continuous strategy set. For instance, Cournot competition is typically modeled with players' strategies being any non-negative quantities, including fractional quantities. Differential games such as

4033-481: Is considered to be partially observable stochastic game (POSG), but few realistic problems are computationally feasible in POSG representation. These are games the play of which is the development of the rules for another game, the target or subject game. Metagames seek to maximize the utility value of the rule set developed. The theory of metagames is related to mechanism design theory. The term metagame analysis

4142-866: Is conventionally read aloud as "necessarily", and can be used to represent notions such as moral or legal obligation , knowledge , historical inevitability , among others. The latter is typically read as "possibly" and can be used to represent notions including permission , ability , compatibility with evidence . While well-formed formulas of modal logic include non-modal formulas such as P ∧ Q {\displaystyle P\land Q} , it also contains modal ones such as ◻ ( P ∧ Q ) {\displaystyle \Box (P\land Q)} , P ∧ ◻ Q {\displaystyle P\land \Box Q} , ◻ ( ◊ P ∧ ◊ Q ) {\displaystyle \Box (\Diamond P\land \Diamond Q)} , and so on. Thus,

4251-401: Is generally less completely formalized than the formal language component of the formal system under examination, which is then called the object language , that is, the object of the discussion in question. The notion of theorem just defined should not be confused with theorems about the formal system , which, in order to avoid confusion, are usually called metatheorems . A logical system

4360-421: Is logically possible to accelerate beyond the speed of light , modern science stipulates that it is not physically possible for material particles or information. Philosophers debate if objects have properties independent of those dictated by scientific laws. For example, it might be metaphysically necessary, as some who advocate physicalism have thought, that all thinking beings have bodies and can experience

4469-439: Is not a great one. In any case, different answers to such questions yield different systems of modal logic. Adding axioms to K gives rise to other well-known modal systems. One cannot prove in K that if " p is necessary" then p is true. The axiom T remedies this defect: T holds in most but not all modal logics. Zeman (1973) describes a few exceptions, such as S1 . Other well-known elementary axioms are: These yield

Modal logic - Misplaced Pages Continue

4578-484: Is not necessarily correct: It is possible (epistemically) that Goldbach's conjecture is both true and unprovable. Epistemic possibilities also bear on the actual world in a way that metaphysical possibilities do not. Metaphysical possibilities bear on ways the world might have been, but epistemic possibilities bear on the way the world may be (for all we know). Suppose, for example, that I want to know whether or not to take an umbrella before I leave. If you tell me "it

4687-443: Is often called the universe . The binary relation R {\displaystyle R} is called an accessibility relation , and it controls which worlds can "see" each other for the sake of determining what is true. For example, w R u {\displaystyle wRu} means that the world u {\displaystyle u} is accessible from world w {\displaystyle w} . That

4796-458: Is permitted that p ) seems appropriate, but we should probably not include that p → ◻ ◊ p {\displaystyle p\to \Box \Diamond p} . In fact, to do so is to commit the naturalistic fallacy (i.e. to state that what is natural is also good, by saying that if p is the case, p ought to be permitted). The commonly employed system S5 simply makes all modal truths necessary. For example, if p

4905-597: Is possible, then it is "necessary" that p is possible. Also, if p is necessary, then it is necessary that p is necessary. Other systems of modal logic have been formulated, in part because S5 does not describe every kind of modality of interest. Sequent calculi and systems of natural deduction have been developed for several modal logics, but it has proven hard to combine generality with other features expected of good structural proof theories , such as purity (the proof theory does not introduce extra-logical notions such as labels) and analyticity (the logical rules support

5014-416: Is said to be In classical modal logic, therefore, the notion of either possibility or necessity may be taken to be basic, where these other notions are defined in terms of it in the manner of De Morgan duality . Intuitionistic modal logic treats possibility and necessity as not perfectly symmetric. For example, suppose that while walking to the convenience store we pass Friedrich's house, and observe that

5123-408: Is simply the propositional calculus augmented by □, the rule N , and the axiom K . K is weak in that it fails to determine whether a proposition can be necessary but only contingently necessary. That is, it is not a theorem of K that if □ p is true then □□ p is true, i.e., that necessary truths are "necessarily necessary". If such perplexities are deemed forced and artificial, this defect of K

5232-489: Is sound and complete if one requires the accessibility relation to be serial . While the intuition behind modal logic dates back to antiquity, the first modal axiomatic systems were developed by C. I. Lewis in 1912. The now-standard relational semantics emerged in the mid twentieth century from work by Arthur Prior , Jaakko Hintikka , and Saul Kripke . Recent developments include alternative topological semantics such as neighborhood semantics as well as applications of

5341-404: Is the study of mathematical models of strategic interactions. It has applications in many fields of social science , and is used extensively in economics , logic , systems science and computer science . Initially, game theory addressed two-person zero-sum games , in which a participant's gains or losses are exactly balanced by the losses and gains of the other participant. In the 1950s, it

5450-478: Is to say, should □ P → □□ P be an axiom in these systems? While the answer to this question is unclear, there is at least one axiom that is generally included in epistemic modal logic, because it is minimally true of all normal modal logics (see the section on axiomatic systems ): Formal system A formal system is an abstract structure and formalization of an axiomatic system used for deducing , using rules of inference , theorems from axioms by

5559-441: Is to say, the state of affairs known as u {\displaystyle u} is a live possibility for w {\displaystyle w} . Finally, the function V {\displaystyle V} is known as a valuation function . It determines which atomic formulas are true at which worlds. Then we recursively define the truth of a formula at a world w {\displaystyle w} in

SECTION 50

#1732776443932

5668-413: Is true at some accessible possible world, while ◻ P {\displaystyle \Box P} is true at a world if P {\displaystyle P} is true at every accessible possible world. A variety of proof systems exist which are sound and complete with respect to the semantics one gets by restricting the accessibility relation. For instance, the deontic modal logic D

5777-476: Is used. For this reason, modal logicians sometimes talk about frames , which are the portion of a relational model excluding the valuation function. The different systems of modal logic are defined using frame conditions . A frame is called: The logics that stem from these frame conditions are: The Euclidean property along with reflexivity yields symmetry and transitivity. (The Euclidean property can be obtained, as well, from symmetry and transitivity.) Hence if

5886-450: The payoffs for each outcome. (Eric Rasmusen refers to these four "essential elements" by the acronym "PAPI".) A game theorist typically uses these elements, along with a solution concept of their choosing, to deduce a set of equilibrium strategies for each player such that, when these strategies are employed, no player can profit by unilaterally deviating from their strategy. These equilibrium strategies determine an equilibrium to

5995-573: The Brouwer fixed-point theorem on continuous mappings into compact convex sets , which became a standard method in game theory and mathematical economics . His paper was followed by Theory of Games and Economic Behavior (1944), co-written with Oskar Morgenstern , which considered cooperative games of several players. The second edition provided an axiomatic theory of expected utility , which allowed mathematical statisticians and economists to treat decision-making under uncertainty. Game theory

6104-748: The Shapley value were developed. The 1950s also saw the first applications of game theory to philosophy and political science . The first mathematical discussion of the prisoner's dilemma appeared, and an experiment was undertaken by mathematicians Merrill M. Flood and Melvin Dresher , as part of the RAND Corporation 's investigations into game theory. RAND pursued the studies because of possible applications to global nuclear strategy . In 1965, Reinhard Selten introduced his solution concept of subgame perfect equilibria , which further refined

6213-413: The formulas that are expressed in the system. Usually the quality we are concerned with is truth as opposed to falsehood. However, other modalities , such as justification or belief may be preserved instead. In order to sustain its deductive integrity, a deductive apparatus must be definable without reference to any intended interpretation of the language. The aim is to ensure that each line of

6322-871: The language L {\displaystyle {\mathcal {L}}} of basic propositional logic can be defined recursively as follows. Modal operators can be added to other kinds of logic by introducing rules analogous to #4 and #5 above. Modal predicate logic is one widely used variant which includes formulas such as ∀ x ◊ P ( x ) {\displaystyle \forall x\Diamond P(x)} . In systems of modal logic where ◻ {\displaystyle \Box } and ◊ {\displaystyle \Diamond } are duals , ◻ ϕ {\displaystyle \Box \phi } can be taken as an abbreviation for ¬ ◊ ¬ ϕ {\displaystyle \neg \Diamond \neg \phi } , thus eliminating

6431-420: The metaphysical claim that it is possible for Bigfoot to exist, even though he does not : there is no physical or biological reason that large, featherless, bipedal creatures with thick hair could not exist in the forests of North America (regardless of whether or not they do). Similarly, "it is possible for the person reading this sentence to be fourteen feet tall and named Chad" is metaphysically true (such

6540-404: The outcome has net results greater or less than zero. Informally, in non-zero-sum games, a gain by one player does not necessarily correspond with a loss by another. Furthermore, constant-sum games correspond to activities like theft and gambling, but not to the fundamental economic situation in which there are potential gains from trade . It is possible to transform any constant-sum game into

6649-445: The propositional calculus to create a usable system of modal logic is a matter of philosophical opinion, often driven by the theorems one wishes to prove; or, in computer science, it is a matter of what sort of computational or deductive system one wishes to model. Many modal logics, known collectively as normal modal logics , include the following rule and axiom: The weakest normal modal logic , named " K " in honor of Saul Kripke ,

SECTION 60

#1732776443932

6758-576: The Nash equilibrium. Later he would introduce trembling hand perfection as well. In 1994 Nash, Selten and Harsanyi became Economics Nobel Laureates for their contributions to economic game theory. In the 1970s, game theory was extensively applied in biology , largely as a result of the work of John Maynard Smith and his evolutionarily stable strategy . In addition, the concepts of correlated equilibrium , trembling hand perfection and common knowledge were introduced and analyzed. In 1994, John Nash

6867-495: The Theory of the Game of Chess ), which proved that the optimal chess strategy is strictly determined . The work of John von Neumann established game theory as its own independent field in the early-to-mid 20th century, with von Neumann publishing his paper On the Theory of Games of Strategy in 1928. Von Neumann's original proof used Brouwer's fixed-point theorem on continuous mappings into compact convex sets , which became

6976-426: The accessibility relation R {\displaystyle R} , which allows us to express the relative nature of possibility. For example, we might say that given our laws of physics it is not possible for humans to travel faster than the speed of light, but that given other circumstances it could have been possible to do so. Using the accessibility relation we can translate this scenario as follows: At all of

7085-415: The accessibility relation R is reflexive and Euclidean, R is provably symmetric and transitive as well. Hence for models of S5, R is an equivalence relation , because R is reflexive, symmetric and transitive. We can prove that these frames produce the same set of valid sentences as do the frames where all worlds can see all other worlds of W ( i.e. , where R is a "total" relation). This gives

7194-436: The actions of the other players. However, there are many situations in game theory where participants do not fully understand the characteristics of their opponents. Negotiators may be unaware of their opponent's valuation of the object of negotiation, companies may be unaware of their opponent's cost functions, combatants may be unaware of their opponent's strengths, and jurors may be unaware of their colleague's interpretation of

7303-425: The area in 1912. Hughes and Cresswell (1996), for example, describe 42 normal and 25 non-normal modal logics. Zeman (1973) describes some systems Hughes and Cresswell omit. Modern treatments of modal logic begin by augmenting the propositional calculus with two unary operations, one denoting "necessity" and the other "possibility". The notation of C. I. Lewis , much employed since, denotes "necessarily p " by

7412-489: The basis for or even identified with a larger theory or field (e.g. Euclidean geometry ) consistent with the usage in modern mathematics such as model theory . An example of a deductive system would be the rules of inference and axioms regarding equality used in first order logic . The two main types of deductive systems are proof systems and formal semantics. Formal proofs are sequences of well-formed formulas (or WFF for short) that might either be an axiom or be

7521-825: The case in all S5 frames, which can still consist of multiple parts that are fully connected among themselves but still disconnected from each other. All of these logical systems can also be defined axiomatically, as is shown in the next section. For example, in S5, the axioms P ⟹ ◻ ◊ P {\displaystyle P\implies \Box \Diamond P} , ◻ P ⟹ ◻ ◻ P {\displaystyle \Box P\implies \Box \Box P} and ◻ P ⟹ P {\displaystyle \Box P\implies P} (corresponding to symmetry , transitivity and reflexivity , respectively) hold, whereas at least one of these axioms does not hold in each of

7630-433: The closed-loop strategies are found using Bellman's Dynamic Programming method. A particular case of differential games are the games with a random time horizon . In such games, the terminal time is a random variable with a given probability distribution function. Therefore, the players maximize the mathematical expectation of the cost function. It was shown that the modified optimization problem can be reformulated as

7739-568: The concept of incentive compatibility . In 2012, Alvin E. Roth and Lloyd S. Shapley were awarded the Nobel Prize in Economics "for the theory of stable allocations and the practice of market design". In 2014, the Nobel went to game theorist Jean Tirole . A game is cooperative if the players are able to form binding commitments externally enforced (e.g. through contract law ). A game

7848-463: The continuous pursuit and evasion game are continuous games where the evolution of the players' state variables is governed by differential equations . The problem of finding an optimal strategy in a differential game is closely related to the optimal control theory. In particular, there are two types of strategies: the open-loop strategies are found using the Pontryagin maximum principle while

7957-416: The corresponding modal graph which is total complete ( i.e. , no more edges (relations) can be added). For example, in any modal logic based on frame conditions: If we consider frames based on the total relation we can just say that We can drop the accessibility clause from the latter stipulation because in such total frames it is trivially true of all w and u that w R u . But this does not have to be

8066-425: The differences between sequential and simultaneous games are as follows: An important subset of sequential games consists of games of perfect information. A game with perfect information means that all players, at every move in the game, know the previous history of the game and the moves previously made by all other players. An imperfect information game is played when the players do not know all moves already made by

8175-1000: The difficulty of finding an optimal strategy stems from the multiplicity of possible moves are called combinatorial games. Examples include chess and Go . Games that involve imperfect information may also have a strong combinatorial character, for instance backgammon . There is no unified theory addressing combinatorial elements in games. There are, however, mathematical tools that can solve some particular problems and answer some general questions. Games of perfect information have been studied in combinatorial game theory , which has developed novel representations, e.g. surreal numbers , as well as combinatorial and algebraic (and sometimes non-constructive ) proof methods to solve games of certain types, including "loopy" games that may result in infinitely long sequences of moves. These methods address games with higher combinatorial complexity than those usually considered in traditional (or "economic") game theory. A typical game that has been solved this way

8284-534: The equilibrium school, introducing equilibrium coarsening and correlated equilibria, and developing an extensive formal analysis of the assumption of common knowledge and of its consequences. In 2007, Leonid Hurwicz , Eric Maskin , and Roger Myerson were awarded the Nobel Prize in Economics "for having laid the foundations of mechanism design theory". Myerson's contributions include the notion of proper equilibrium , and an important graduate text: Game Theory, Analysis of Conflict . Hurwicz introduced and formalized

8393-443: The evidence at trial. In some cases, participants may know the character of their opponent well, but may not know how well their opponent knows his or her own character. Bayesian game means a strategic game with incomplete information. For a strategic game, decision makers are players, and every player has a group of actions. A core part of the imperfect information specification is the set of states. Every state completely describes

8502-400: The following contrasts may help: A person, Jones, might reasonably say both : (1) "No, it is not possible that Bigfoot exists; I am quite certain of that"; and , (2) "Sure, it's possible that Bigfoots could exist". What Jones means by (1) is that, given all the available information, there is no question remaining as to whether Bigfoot exists. This is an epistemic claim. By (2) he makes

8611-412: The game pictured in this section's graphic is asymmetric despite having identical strategy sets for both players. Zero-sum games (more generally, constant-sum games) are games in which choices by players can neither increase nor decrease the available resources. In zero-sum games, the total benefit goes to all players in a game, for every combination of strategies, and always adds to zero (more informally,

8720-559: The game. For some problems, different approaches to modeling stochastic outcomes may lead to different solutions. For example, the difference in approach between MDPs and the minimax solution is that the latter considers the worst-case over a set of adversarial moves, rather than reasoning in expectation about these moves given a fixed probability distribution. The minimax approach may be advantageous where stochastic models of uncertainty are not available, but may also be overestimating extremely unlikely (but costly) events, dramatically swaying

8829-417: The lights are off. On the way back, we observe that they have been turned on. (Of course, this analogy does not apply alethic modality in a truly rigorous fashion; for it to do so, it would have to axiomatically make such statements as "human beings cannot rise from the dead", "Socrates was a human being and not an immortal vampire", and "we did not take hallucinogenic drugs which caused us to falsely believe

8938-437: The lights were on", ad infinitum . Absolute certainty of truth or falsehood exists only in the sense of logically constructed abstract concepts such as "it is impossible to draw a triangle with four sides" and "all bachelors are unmarried".) For those having difficulty with the concept of something being possible but not true, the meaning of these terms may be made more comprehensible by thinking of multiple "possible worlds" (in

9047-410: The mathematics involved are substantially the same, e.g. using Markov decision processes (MDP). Stochastic outcomes can also be modeled in terms of game theory by adding a randomly acting player who makes "chance moves" (" moves by nature "). This player is not typically considered a third player in what is otherwise a two-player game, but merely serves to provide a roll of the dice where required by

9156-454: The method for finding mutually consistent solutions for two-person zero-sum games. Subsequent work focused primarily on cooperative game theory, which analyzes optimal strategies for groups of individuals, presuming that they can enforce agreements between them about proper strategies. In his 1938 book Applications aux Jeux de Hasard and earlier notes, Émile Borel proved a minimax theorem for two-person zero-sum matrix games only when

9265-724: The need for a separate syntactic rule to introduce it. However, separate syntactic rules are necessary in systems where the two operators are not interdefinable. Common notational variants include symbols such as [ K ] {\displaystyle [K]} and ⟨ K ⟩ {\displaystyle \langle K\rangle } in systems of modal logic used to represent knowledge and [ B ] {\displaystyle [B]} and ⟨ B ⟩ {\displaystyle \langle B\rangle } in those used to represent belief. These notations are particularly common in systems which use multiple modal operators simultaneously. For instance,

9374-482: The opponent such as a simultaneous move game. Examples of perfect-information games include tic-tac-toe , checkers , chess , and Go . Many card games are games of imperfect information, such as poker and bridge . Perfect information is often confused with complete information , which is a similar concept pertaining to the common knowledge of each player's sequence, strategies, and payoffs throughout gameplay. Complete information requires that every player know

9483-545: The other, weaker logics. Modal logic has also been interpreted using topological structures. For instance, the Interior Semantics interprets formulas of modal logic as follows. A topological model is a tuple X = ⟨ X , τ , V ⟩ {\displaystyle \mathrm {X} =\langle X,\tau ,V\rangle } where ⟨ X , τ ⟩ {\displaystyle \langle X,\tau \rangle }

9592-407: The outcome and decisions of other players. This need not be perfect information about every action of earlier players; it might be very little knowledge. For instance, a player may know that an earlier player did not perform one particular action, while they do not know which of the other available actions the first player actually performed. The difference between simultaneous and sequential games

9701-431: The passage of time . Saul Kripke has argued that every person necessarily has the parents they do have: anyone with different parents would not be the same person. Metaphysical possibility has been thought to be more restricting than bare logical possibility (i.e., fewer things are metaphysically possible than are logically possible). However, its exact relation (if any) to logical possibility or to physical possibility

9810-472: The pay-off matrix is symmetric and provided a solution to a non-trivial infinite game (known in English as Blotto game ). Borel conjectured the non-existence of mixed-strategy equilibria in finite two-person zero-sum games , a conjecture that was proved false by von Neumann. In 1950, John Nash developed a criterion for mutual consistency of players' strategies known as the Nash equilibrium , applicable to

9919-406: The possible strategies available to players due to the possibility of external enforcement of cooperation. A symmetric game is a game where each player earns the same payoff when making the same choice. In other words, the identity of the player does not change the resulting game facing the other player. Many of the commonly studied 2×2 games are symmetric. The standard representations of chicken ,

10028-412: The prisoner's dilemma, and the stag hunt are all symmetric games. The most commonly studied asymmetric games are games where there are not identical strategy sets for both players. For instance, the ultimatum game and similarly the dictator game have different strategies for each player. It is possible, however, for a game to have identical strategies for both players, yet be asymmetric. For example,

10137-423: The product of applying an inference rule on previous WFFs in the proof sequence. The last WFF in the sequence is recognized as a theorem . Once a formal system is given, one can define the set of theorems which can be proved inside the formal system. This set consists of all WFFs for which there is a proof. Thus all axioms are considered theorems. Unlike the grammar for WFFs, there is no guarantee that there will be

10246-416: The recent past. Such rules may feature imitation, optimization, or survival of the fittest. In biology, such models can represent evolution , in which offspring adopt their parents' strategies and parents who play more successful strategies (i.e. corresponding to higher payoffs) have a greater number of offspring. In the social sciences, such models typically represent strategic adjustment by players who play

10355-437: The relational semantics beyond its original philosophical motivation. Such applications include game theory , moral and legal theory , web design , multiverse-based set theory , and social epistemology . Modal logic differs from other kinds of logic in that it uses modal operators such as ◻ {\displaystyle \Box } and ◊ {\displaystyle \Diamond } . The former

10464-434: The sense of Leibniz ) or "alternate universes"; something "necessary" is true in all possible worlds, something "possible" is true in at least one possible world. Something is physically, or nomically, possible if it is permitted by the laws of physics . For example, current theory is thought to allow for there to be an atom with an atomic number of 126, even if there are no such atoms in existence. In contrast, while it

10573-403: The set of accessible possible worlds is non-empty). Regardless of notation, each of these operators is definable in terms of the other in classical modal logic: Hence □ and ◇ form a dual pair of operators. In many modal logics, the necessity and possibility operators satisfy the following analogues of de Morgan's laws from Boolean algebra : Precisely what axioms and rules must be added to

10682-479: The set of axioms and the set of inference rules are decidable sets or semidecidable sets , respectively. A formal language is a language that is defined by a formal system. Like languages in linguistics , formal languages generally have two aspects: Usually only the syntax of a formal language is considered via the notion of a formal grammar . The two main categories of formal grammar are that of generative grammars , which are sets of rules for how strings in

10791-402: The standard relational semantics for modal logic, formulas are assigned truth values relative to a possible world . A formula's truth value at one possible world can depend on the truth values of other formulas at other accessible possible worlds . In particular, ◊ P {\displaystyle \Diamond P} is true at a world if P {\displaystyle P}

10900-404: The strategies and payoffs available to the other players but not necessarily the actions taken, whereas perfect information is knowledge of all aspects of the game and players. Games of incomplete information can be reduced, however, to games of imperfect information by introducing " moves by nature ". One of the assumptions of the Nash equilibrium is that every player has correct beliefs about

11009-452: The strategy in such scenarios if it is assumed that an adversary can force such an event to happen. (See Black swan theory for more discussion on this kind of modeling issue, particularly as it relates to predicting and limiting losses in investment banking.) General models that include all elements of stochastic outcomes, adversaries, and partial or noisy observability (of moves by other players) have also been studied. The " gold standard "

11118-404: The systems (axioms in bold, systems in italics): K through S5 form a nested hierarchy of systems, making up the core of normal modal logic . But specific rules or sets of rules may be appropriate for specific systems. For example, in deontic logic , ◻ p → ◊ p {\displaystyle \Box p\to \Diamond p} (If it ought to be that p , then it

11227-408: The worlds accessible to our own world, it is not the case that humans can travel faster than the speed of light, but at one of these accessible worlds there is another world accessible from those worlds but not accessible from our own at which humans can travel faster than the speed of light. The choice of accessibility relation alone can sometimes be sufficient to guarantee the truth or falsity of

11336-762: Was awarded the Nobel Memorial Prize in the Economic Sciences for his contribution to game theory. Nash's most famous contribution to game theory is the concept of the Nash equilibrium, which is a solution concept for non-cooperative games . A Nash equilibrium is a set of strategies, one for each player, such that no player can improve their payoff by unilaterally changing their strategy. In 2005, game theorists Thomas Schelling and Robert Aumann followed Nash, Selten, and Harsanyi as Nobel Laureates. Schelling worked on dynamic models, early examples of evolutionary game theory . Aumann contributed more to

11445-459: Was considered in the economics literature by Boyan Jovanovic and Robert W. Rosenthal , in the engineering literature by Peter E. Caines , and by mathematicians Pierre-Louis Lions and Jean-Michel Lasry. The games studied in game theory are well-defined mathematical objects. To be fully defined, a game must specify the following elements: the players of the game, the information and actions available to each player at each decision point, and

11554-627: Was developed extensively in the 1950s, and was explicitly applied to evolution in the 1970s, although similar developments go back at least as far as the 1930s. Game theory has been widely recognized as an important tool in many fields. John Maynard Smith was awarded the Crafoord Prize for his application of evolutionary game theory in 1999, and fifteen game theorists have won the Nobel Prize in economics as of 2020, including most recently Paul Milgrom and Robert B. Wilson . In 1713,

11663-407: Was developed in 19th century Europe . David Hilbert instigated a formalist movement called Hilbert’s program as a proposed solution to the foundational crisis of mathematics , that was eventually tempered by Gödel's incompleteness theorems . The QED manifesto represented a subsequent, as yet unsuccessful, effort at formalization of known mathematics. Game theory Game theory

11772-410: Was extended to others. For this reason, or perhaps for their familiarity and simplicity, necessity and possibility are often casually treated as the subject matter of modal logic. Moreover, it is easier to make sense of relativizing necessity, e.g. to legal, physical, nomological , epistemic , and so on, than it is to make sense of relativizing other notions. In classical modal logic , a proposition

11881-400: Was extended to the study of non zero-sum games, and was eventually applied to a wide range of behavioral relations . It is now an umbrella term for the science of rational decision making in humans, animals, and computers. Modern game theory began with the idea of mixed-strategy equilibria in two-person zero-sum games and its proof by John von Neumann . Von Neumann's original proof used

#931068