(payoffs)"},"2L":{"wt":"+1"},"2R":{"wt":"–1"},"1U":{"wt":"+1"},"UL":{"wt":"5, 2"},"UR":{"wt":"–1, –2"},"1D":{"wt":"–1"},"DL":{"wt":"–5, –4"},"DR":{"wt":"1, 4"}},"i":0}}]}" id="mwdw">
+1 | –1 | |
+1 | 5, 2 | –1, –2 |
–1 | –5, –4 | 1, 4 |
Fig. 2: Battle of the sexes (payoffs) |
+1 | –1 | |
+1 | 4 | 0 |
–1 | –6 | 2 |
Fig. 3: Battle of the sexes (potentials) |
A 2-player, 2-strategy game cannot be a potential game unless
The proof of Gödel's completeness theorem given by Kurt Gödel in his doctoral dissertation of 1929 is not easy to read today; it uses concepts and formalism that are no longer used and terminology that is often obscure. The version given below attempts to represent all the steps in the proof and all the important ideas faithfully, while restating the proof in the modern language of mathematical logic. This outline should not be considered a rigorous proof of the theorem.
In set theory, the axiom schema of replacement is a schema of axioms in Zermelo–Fraenkel set theory (ZF) that asserts that the image of any set under any definable mapping is also a set. It is necessary for the construction of certain infinite sets in ZF.
In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.
In mathematical analysis, a function of bounded variation, also known as BV function, is a real-valued function whose total variation is bounded (finite): the graph of a function having this property is well behaved in a precise sense. For a continuous function of a single variable, being of bounded variation means that the distance along the direction of the y-axis, neglecting the contribution of motion along x-axis, traveled by a point moving along the graph has a finite value. For a continuous function of several variables, the meaning of the definition is the same, except for the fact that the continuous path to be considered cannot be the whole graph of the given function, but can be every intersection of the graph itself with a hyperplane parallel to a fixed x-axis and to the y-axis.
A formula of the predicate calculus is in prenex normal form if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix.
In game theory, a cooperative game is a game with competition between groups of players ("coalitions") due to the possibility of external enforcement of cooperative behavior. Those are opposed to non-cooperative games in which there is either no possibility to forge alliances or all agreements need to be self-enforcing.
Mechanism design is a field in economics and game theory that takes an engineering approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally. Because it starts at the end of the game, then goes backwards, it is also called reverse game theory. It has broad applications, from economics and politics to networked-systems.
Game theory is the branch of mathematics in which games are studied: that is, models describing human behaviour. This is a glossary of some terms of the subject.
The Kripke–Platek set theory with urelements (KPU) is an axiom system for set theory with urelements, based on the traditional (urelement-free) Kripke–Platek set theory. It is considerably weaker than the (relatively) familiar system ZFU. The purpose of allowing urelements is to allow large or high-complexity objects to be included in the theory's transitive models without disrupting the usual well-ordering and recursion-theoretic properties of the constructible universe; KP is so weak that this is hard to do by traditional means.
In game theory, a Bayesian game is a game in which the players have incomplete information about the other players. For example, a player may not know the exact payoff functions of the other players, but instead have beliefs about these payoff functions. These beliefs are represented by a probability distribution over the possible payoff functions.
Independence-friendly logic, proposed by Jaakko Hintikka and Gabriel Sandu in 1989, is an extension of classical first-order logic (FOL) by means of slashed quantifiers of the form and . The intended reading of is "there is a which is functionally independent from the variables in ". IF logic allows one to express more general patterns of dependence between variables than those which are implicit in first-order logic. This greater level of generality leads to an actual increase in expressive power; the set of IF sentences can characterize the same classes of structures as existential second-order logic. For example, it can express branching quantifier sentences, such as the formula which expresses infinity in the empty signature; this cannot be done in FOL. Therefore, first-order logic cannot, in general, express this pattern of dependency, in which depends only on and , and depends only on and . IF logic is more general than branching quantifiers, for example in that it can express dependencies that are not transitive, such as in the quantifier prefix .
In game theory, a symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. If one can change the identities of the players without changing the payoff to the strategies, then a game is symmetric. Symmetry can come in different varieties. Ordinally symmetric games are games that are symmetric with respect to the ordinal structure of the payoffs. A game is quantitatively symmetric if and only if it is symmetric with respect to the exact payoffs. A partnership game is a symmetric game where both players receive identical payoffs for any strategy set. That is, the payoff for playing strategy a against strategy b receives the same payoff as playing strategy b against strategy a.
In game theory, a correlated equilibrium is a solution concept that is more general than the well known Nash equilibrium. It was first discussed by mathematician Robert Aumann in 1974. The idea is that each player chooses their action according to their observation of the value of the same public signal. A strategy assigns an action to every possible observation a player can make. If no player would want to deviate from the recommended strategy, the distribution is called a correlated equilibrium.
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics.
In mathematics and theoretical physics, an invariant differential operator is a kind of mathematical map from some objects to an object of similar type. These objects are typically functions on , functions on a manifold, vector valued functions, vector fields, or, more generally, sections of a vector bundle.
In applied mathematics, discontinuous Galerkin methods form a class of numerical methods for solving differential equations. They combine features of the finite element and the finite volume framework and have been successfully applied to hyperbolic, elliptic, parabolic and mixed form problems arising from a wide range of applications. DG methods have in particular received considerable interest for problems with a dominant first-order part, e.g. in electrodynamics, fluid mechanics and plasma physics.
In the mathematical analysis, and especially in real and harmonic analysis, a Birnbaum–Orlicz space is a type of function space which generalizes the L^{p} spaces. Like the L^{p} spaces, they are Banach spaces. The spaces are named for Władysław Orlicz and Zygmunt William Birnbaum, who first defined them in 1931.
In computability theory, a semicomputable function is a partial function that can be approximated either from above or from below by a computable function.
Congestion games are a class of games in game theory first proposed by Rosenthal in 1973. In a Congestion game we define players and resources, where the payoff of each player depends on the resources it chooses and the number of players choosing the same resource. Congestion games are a special case of potential games. Rosenthal proved that any congestion game is a potential game and Monderer and Shapley (1996) proved the converse: for any potential game, there is a congestion game with the same potential function.
In game theory, an aggregative game is a game in which every player’s payoff is a function of the player’s own strategy and the aggregate of all players’ strategies. The concept was first proposed by Nobel laureate Reinhard Selten in 1970 who considered the case where the aggregate is the sum of the players' strategies.
Vijay Virkumar Vazirani is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine.
Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.
Timothy Avelin Roughgarden is a professor of Computer Science at Columbia University. Roughgarden received his Ph.D. at Cornell University in 2002, under the supervision of Éva Tardos.