Related Research Articles
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. The principle of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to competing firms choosing outputs.
Pareto efficiency or Pareto optimality is a situation where no action or allocation is available that makes one individual better off without making another worse off. The concept is named after Vilfredo Pareto (1848–1923), Italian civil engineer and economist, who used the concept in his studies of economic efficiency and income distribution. The following three concepts are closely related:
In logic and computer science, specifically automated reasoning, unification is an algorithmic process of solving equations between symbolic expressions, each of the form Left-hand side = Right-hand side. For example, using x,y,z as variables, and taking f to be an uninterpreted function, the singleton equation set { f(1,y) = f(x,2) } is a syntactic first-order unification problem that has the substitution { x ↦ 1, y ↦ 2 } as its only solution.
In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's law of noncontradiction states that "It is impossible that the same thing can at the same time both belong and not belong to the same object and in the same respect."
In game theory, the best response is the strategy which produces the most favorable outcome for a player, taking other players' strategies as given. The concept of a best response is central to John Nash's best-known contribution, the Nash equilibrium, the point at which each player in a game has selected the best response to the other players' strategies.
In mathematics, the axiom of determinacy is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of a certain type is determined; that is, one of the two players has a winning strategy.
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.
In statistical mechanics, the correlation function is a measure of the order in a system, as characterized by a mathematical correlation function. Correlation functions describe how microscopic variables, such as spin and density, at different positions are related. More specifically, correlation functions measure quantitatively the extent to which microscopic variables fluctuate together, on average, across space and/or time. Keep in mind that correlation doesn’t automatically equate to causation. So, even if there’s a non-zero correlation between two points in space or time, it doesn’t mean there is a direct causal link between them. Sometimes, a correlation can exist without any causal relationship. This could be purely coincidental or due to other underlying factors, known as confounding variables, which cause both points to covary (statistically).
In game theory, a Bayesian game is a strategic decision-making model which assumes players have incomplete information. Players hold private information relevant to the game, meaning that the payoffs are not common knowledge. Bayesian games model the outcome of player interactions using aspects of Bayesian probability. They are notable because they allowed, for the first time in game theory, for the specification of the solutions to games with incomplete information.
Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and similarly, "determinacy" is the property of a game whereby such a strategy exists. Determinacy was introduced by Gale and Stewart in 1950, under the name "determinateness".
In game theory, folk theorems are a class of theorems describing an abundance of Nash equilibrium payoff profiles in repeated games. The original Folk Theorem concerned the payoffs of all the Nash equilibria of an infinitely repeated game. This result was called the Folk Theorem because it was widely known among game theorists in the 1950s, even though no one had published it. Friedman's (1971) Theorem concerns the payoffs of certain subgame-perfect Nash equilibria (SPE) of an infinitely repeated game, and so strengthens the original Folk Theorem by using a stronger equilibrium concept: subgame-perfect Nash equilibria rather than Nash equilibria.
In game theory, the war of attrition is a dynamic timing game in which players choose a time to stop, and fundamentally trade off the strategic gains from outlasting other players and the real costs expended with the passage of time. Its precise opposite is the pre-emption game, in which players elect a time to stop, and fundamentally trade off the strategic costs from outlasting other players and the real gains occasioned by the passage of time. The model was originally formulated by John Maynard Smith; a mixed evolutionarily stable strategy (ESS) was determined by Bishop & Cannings. An example is a second price all-pay auction, in which the prize goes to the player with the highest bid and each player pays the loser's low bid.
In game theory, a stochastic game, introduced by Lloyd Shapley in the early 1950s, is a repeated game with probabilistic transitions played by one or more players. The game is played in a sequence of stages. At the beginning of each stage the game is in some state. The players select actions and each player receives a payoff that depends on the current state and the chosen actions. The game then moves to a new random state whose distribution depends on the previous state and the actions chosen by the players. The procedure is repeated at the new state and play continues for a finite or infinite number of stages. The total payoff to a player is often taken to be the discounted sum of the stage payoffs or the limit inferior of the averages of the stage payoffs.
In game theory, a strong Nash equilibrium(SNE) is a combination of actions of the different players, in which no coalition of players can cooperatively deviate in a way that strictly benefits all of its members, given that the actions of the other players remain fixed. This is in contrast to simple Nash equilibrium, which considers only deviations by individual players. The concept was introduced by Israel Aumann in 1959. SNE is particularly useful in areas such as the study of voting systems, in which there are typically many more players than possible outcomes, and so plain Nash equilibria are far too abundant.
The Price of Anarchy (PoA) is a concept in economics and game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of efficiency. For example, consider the system of transportation of a city and many agents trying to go from some initial location to a destination. Here, efficiency means the average time for an agent to reach the destination. In the 'centralized' solution, a central authority can tell each agent which path to take in order to minimize the average travel time. In the 'decentralized' version, each agent chooses its own path. The Price of Anarchy measures the ratio between average travel time in the two cases.
A continuous game is a mathematical concept, used in game theory, that generalizes the idea of an ordinary game like tic-tac-toe or checkers (draughts). In other words, it extends the notion of a discrete game, where the players choose from a finite set of pure strategies. The continuous game concepts allows games to include more general sets of pure strategies, which may be uncountably infinite.
Congestion games (CG) are a class of games in game theory. They represent situations which commonly occur in roads, communication networks, oligopoly markets and natural habitats. There is a set of resources ; there are several players who need resources ; each player chooses a subset of these resources ; the delay in each resource is determined by the number of players choosing a subset that contains this resource. The cost of each player is the sum of delays among all resources he chooses. Naturally, each player wants to minimize his own delay; however, each player's choices impose a negative externality on the other players, which may lead to inefficient outcomes.
In game theory a max-dominated strategy is a strategy which is not a best response to any strategy profile of the other players. This is an extension to the notion of strictly dominated strategies, which are max-dominated as well.
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.
Program equilibrium is a game-theoretic solution concept for a scenario in which players submit computer programs to play the game on their behalf and the programs can read each other's source code. The term was introduced by Moshe Tennenholtz in 2004. The same setting had previously been studied by R. Preston McAfee, J. V. Howard and Ariel Rubinstein.
References
- ↑ Hedges, Jm (2016-10-03). Towards compositional game theory (Thesis).
- 1 2 Ghani, Neil; Hedges, Jules; Winschel, Viktor; Zahn, Philipp (2018-07-09). "Compositional Game Theory". Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. LICS '18. New York, NY, US: Association for Computing Machinery. pp. 472–481. arXiv: 1603.04641 . doi:10.1145/3209108.3209165. ISBN 978-1-4503-5583-4.
- ↑ Atkey, Robert; Gavranović, Bruno; Ghani, Neil; Kupke, Clemens; Ledent, Jérémy; Nordvall Forsberg, Fredrik (July 2020). "Compositional Game Theory, Compositionally". Electronic Proceedings in Theoretical Computer Science. 333. Online, United States: 198–214. doi:10.4204/eptcs.333.14.
- ↑ Hedges, Jules; Oliva, Paulo; Sprits, Evguenia; Winschel, Viktor; Zahn, Philipp (2015-06-03). "Higher-Order Game Theory". arXiv: 1506.01002 [cs.GT].
- ↑ Bolt, Joe; Hedges, Jules; Zahn, Philipp (2023-10-04). "Bayesian open games". Compositionality. 5: 9. arXiv: 1910.03656 . doi:10.32408/compositionality-5-9.