Sequential game
In game theory, a sequential game is a game where one player chooses their action before the others choose theirs. The players must have some information of the first's choice, otherwise the difference in time would have no strategic effect. Sequential games hence are governed by the time axis, represented in the form of decision trees. Unlike sequential games, simultaneous games do not have a time axis as players choose their moves without being sure of the other's, are represented in the form of payoff matrices. Extensive form representations are used for sequential games, since they explicitly illustrate the sequential aspects of a game. Combinatorial games are sequential games. Games such as chess, infinite chess, tic-tac-toe and Go are examples of sequential games; the size of the decision trees can vary according to game complexity, ranging from the small game tree of tic-tac-toe, to an immensely complex game tree of chess so large that computers cannot map it completely. In sequential games with perfect information, a subgame perfect equilibrium can be found by backward induction.
Simultaneous game Subgame perfection Sequential auction
Preference (economics)
In economics and other social sciences, preference is the ordering of alternatives based on their relative utility, a process which results in an optimal "choice". The character of the individual preferences is determined purely by taste factors, independent of considerations of prices, income, or availability of goods. With the help of the scientific method many practical decisions of life can be modelled, resulting in testable predictions about human behavior. Although economists are not interested in the underlying causes of the preferences in themselves, they are interested in the theory of choice because it serves as a background for empirical demand analysis. In 1926 Ragnar Frisch developed for the first time a mathematical model of preferences in the context of economic demand and utility functions. Up to economists had developed an elaborated theory of demand that omitted primitive characteristics of people; this omission ceased when, at the end of the 19th and the beginning of the 20th century, logical positivism predicated the need of theoretical concepts to be related with observables.
Whereas economists in the 18th and 19th centuries felt comfortable theorizing about utility, with the advent of logical positivism in the 20th century, they felt that it needed more of an empirical structure. Because binary choices are directly observable, it appealed to economists; the search for observables in microeconomics is taken further by revealed preference theory. Since the pioneer efforts of Frisch in the 1920s, one of the major issues which has pervaded the theory of preferences is the representability of a preference structure with a real-valued function; this has been achieved by mapping it to the mathematical index called utility. Von Neumann and Morgenstern 1944 book "Games and Economic Behaviour" treated preferences as a formal relation whose properties can be stated axiomatically; these type of axiomatic handling of preferences soon began to influence other economists: Marschak adopted it by 1950, Houthakker employed it in a 1950 paper, Kenneth Arrow perfected it in his 1951 book "Social Choice and Individual Values".
Gérard Debreu, influenced by the ideas of the Bourbaki group, championed the axiomatization of consumer theory in the 1950s, the tools he borrowed from the mathematical field of binary relations have become mainstream since then. Though the economics of choice can be examined either at the level of utility functions or at the level of preferences, to move from one to the other can be useful. For example, shifting the conceptual basis from an abstract preference relation to an abstract utility scale results in a new mathematical framework, allowing new kinds of conditions on the structure of preference to be formulated and investigated. Another historical turnpoint can be traced back to 1895, when Georg Cantor proved in a theorem that if a binary relation is linearly ordered it is isomorphically embeddable in the ordered real numbers; this notion would become influential for the theory of preferences in economics: by the 1940s prominent authors such as Paul Samuelson, would theorize about people having weakly ordered preferences.
Suppose the set of all states of the world is X and an agent has a preference relation on X. It is common to mark the weak preference relation by ⪯, so that x ⪯ y means "the agent wants y at least as much as x" or "the agent weakly prefers y to x"; the symbol ∼ is used as a shorthand to the indifference relation: x ∼ y ⟺, which reads "the agent is indifferent between y and x". The symbol ≺ is used as a shorthand to the strong preference relation: x ≺ y ⟺, which reads "the agent prefers y to x". In everyday speech, the statement "x is preferred to y" is understood to mean that someone chooses x over y. However, decision theory rests on more precise definitions of preferences given that there are many experimental conditions influencing people's choices in many directions. Suppose a person is confronted with a mental experiment that she must solve with the aid of introspection, she is offered apples and oranges, is asked to verbally choose one of the two. A decision scientist observing this single event would be inclined to say that whichever is chosen is the preferred alternative.
Under several repetitions of this experiment, if the scientist observes that apples are chosen 51% of the time it would mean that x ≻ y. If half of the time oranges are chosen x ∼ y. If 51% of the time she chooses oranges it means that y ≻ x. Preference is here being identified with a greater frequency of choice; this experiment implicitly assumes. Otherwise, out of 100 repetitions, some of them will give as a result that neither apples, oranges or ties are chosen; these few cases of uncertainty will ruin any preference information resulting from the frequency attributes of the other valid cases. However, this example was used
Vijay Vazirani
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. Vazirani received his Bachelor's degree from MIT in 1979 and his Ph. D. from the University of California, Berkeley in 1983. His dissertation, Maximum Matchings without Blossoms, was supervised by Manuel Blum. After postdoctoral research with Michael O. Rabin and Leslie Valiant at Harvard University, he joined the faculty at Cornell University in 1984, he moved to the Indian Institute of Technology, Delhi as a full professor in 1990, moved again to the Georgia Institute of Technology in 1995. He was a McKay Visiting Professor at the University of California, a Distinguished SISL Visitor at the Social and Information Sciences Laboratory at the California Institute of Technology. In 2017 he moved to the University of Irvine as Distinguished Professor. Vazirani's research career has been centered around the design of algorithms, together with work on computational complexity theory and algorithmic game theory.
During the 1980s, he made seminal contributions to the classical maximum matching problem, some key contributions to computational complexity theory, e.g. the isolation lemma and the Valiant-Vazirani theorem. During the 1990s he worked on approximation algorithms, championing the primal-dual schema, which he applied to problems arising in network design, facility location and web caching, clustering. In July 2001 he published what is regarded as the definitive book on approximation algorithms. Since 2002, he has been at the forefront of the effort to understand the computability of market equilibria, with an extensive body of work on the topic, his research results include proving, along with Leslie Valiant, that if UNIQUE-SAT is in P NP = RP, obtaining in 1980, along with Silvio Micali, an algorithm for finding maximum matchings in general graphs. With Mehta and Umesh Vazirani, he showed in 2007 how to formulate the problem of choosing advertisements for AdWords as an online matching problem, found a solution to this problem with optimal competitive ratio.
In 2005 both Vazirani and his brother Umesh Vazirani were inducted as Fellows of the Association for Computing Machinery. In 2011, he was awarded a Guggenheim Fellowship. List of Indian mathematicians Home page at UC Irvine Vijay Vazirani publications indexed by Google Scholar
Game theory
Game theory is the study of mathematical models of strategic interaction between rational decision-makers. It has applications in all fields of social science, as well as in computer science, it addressed zero-sum games, in which one person's gains result in losses for the other participants. Today, game theory applies to a wide range of behavioral relations, is now an umbrella term for the science of logical decision making in humans and computers. Modern game theory began with the idea regarding the existence of mixed-strategy equilibria in two-person zero-sum games and its proof by John von Neumann. Von Neumann's original proof used 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 the 1944 book Theory of Games and Economic Behavior, co-written with Oskar Morgenstern, which considered cooperative games of several players. The second edition of this book provided an axiomatic theory of expected utility, which allowed mathematical statisticians and economists to treat decision-making under uncertainty.
Game theory was developed extensively in the 1950s by many scholars. It was explicitly applied to biology in the 1970s, although similar developments go back at least as far as the 1930s. Game theory has been recognized as an important tool in many fields; as of 2014, with the Nobel Memorial Prize in Economic Sciences going to game theorist Jean Tirole, eleven game theorists have won the economics Nobel Prize. John Maynard Smith was awarded the Crafoord Prize for his application of game theory to biology. Early discussions of examples of two-person games occurred long before the rise of modern, mathematical game theory; the first known discussion of game theory occurred in a letter written by Charles Waldegrave, an active Jacobite, uncle to James Waldegrave, a British diplomat, in 1713. In this letter, Waldegrave provides a minimax mixed strategy solution to a two-person version of the card game le Her, the problem is now known as Waldegrave problem. In his 1838 Recherches sur les principes mathématiques de la théorie des richesses, Antoine Augustin Cournot considered a duopoly and presents a solution, a restricted version of the Nash equilibrium.
In 1913, Ernst Zermelo published Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. It proved that the optimal chess strategy is determined; this paved the way for more general theorems. In 1938, the Danish mathematical economist Frederik Zeuthen proved that the mathematical model had a winning strategy by using Brouwer's fixed point theorem. 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 the pay-off matrix was symmetric. Borel conjectured that non-existence of mixed-strategy equilibria in two-person zero-sum games would occur, a conjecture, proved false. Game theory did not exist as a unique field until John von Neumann published the 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 a standard method in game theory and mathematical economics, his paper was followed by 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 as an independent discipline. Von Neumann's work in game theory culminated in this 1944 book; this foundational work contains the method for finding mutually consistent solutions for two-person zero-sum games. During the following time period, work on game theory was focused on cooperative game theory, which analyzes optimal strategies for groups of individuals, presuming that they can enforce agreements between them about proper strategies. In 1950, the first mathematical discussion of the prisoner's dilemma appeared, an experiment was undertaken by notable 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. Around this same time, John Nash developed a criterion for mutual consistency of players' strategies, known as Nash equilibrium, applicable to a wider variety of games than the criterion proposed by von Neumann and Morgenstern.
Nash proved that every n-player, non-zero-sum non-cooperative game has what is now known as a Nash equilibrium. Game theory experienced a flurry of activity in the 1950s, during which time the concepts of the core, the extensive form game, fictitious play, repeated games, the Shapley value were developed. In addition, the first applications of game theory to philosophy and political science occurred during this time. In 1979 Robert Axelrod tried setting up computer programs as players and found that in tournaments between them the winner was a simple "tit-for-tat" program that cooperates on the first step on subsequent steps just does whatever its opponent did on the previous step; the same winner was often obtained by natural selection. In 1965, Reinhard Selten introduced his solution concept of subgame perfect equilibria, which further refined the Nash equilibrium. In 1994 Nash and Harsanyi became Economics Nobel Laureates for their contributi
Externality
In economics, an externality is the cost or benefit that affects a party who did not choose to incur that cost or benefit. Externalities occurs when a product or service’s price equilibrium cannot reflect the true costs and benefits of that product or service. Externalities can be both negative. Governments and institutions take actions to internalize externalities, thus market-priced transactions can incorporate all the benefits and costs associated with transactions between economic agents. For example, manufacturing activities that cause air pollution impose health and clean-up costs on the whole society, whereas the neighbors of individuals who choose to fire-proof their homes may benefit from a reduced risk of a fire spreading to their own houses. If external costs exist, such as pollution, the producer may choose to produce more of the product than would be produced if the producer were required to pay all associated environmental costs; because responsibility or consequence for self-directed action lies outside the self, an element of externalization is involved.
If there are external benefits, such as in public safety, less of the good may be produced than would be the case if the producer were to receive payment for the external benefits to others. For the purpose of these statements, overall cost and benefit to society is defined as the sum of the imputed monetary value of benefits and costs to all parties involved. Two British economists are credited with having initiated the formal study of externalities, or "spillover effects": Henry Sidgwick is credited with first articulating, Arthur C. Pigou is credited with formalizing the concept of externalities. A negative externality is any difference between the private cost of an action or decision to an economic agent and the social cost. In simple terms, a negative externality is anything. An example is the toxic gases that are released from industries or mines, these gases cause harm to individuals within the surrounding area and have to bear a cost to get rid of that harm. Conversely, a positive externality is any difference between the private benefit of an action or decision to an economic agent and the social benefit.
Suppose that there are K different possible allocations and N different agents, where K, N < ∞ and N ≥ 2. Suppose that each agent has a type θ i ∼ F i and that each agent gets payoff v i + t i, where t i is the transfer paid by the i -th agent. A map f = is a social choice function if ∑ i = 1 N t i ≤ 0 for all θ ∈ N. An allocation κ: N → K is ex-post efficient if ∑ i = 1 N v i ≥ ∑ i = 1 N v i for all θ = ∈ N and all k ∈ K. Let κ ∗ denote an ex-post efficient allocation and let κ ~ i denote an ex-post efficient allocation without agent i; the externality imposed by agent i on the other agents is ∑ j ≠ i v j − ∑ j ≠ i v j, where θ − i is the type vector θ without its i {\displaysty
Tit for tat
Tit for tat is an English saying meaning "equivalent retaliation". It is a effective strategy in game theory for the iterated prisoner's dilemma; the strategy was first introduced by Anatol Rapoport in Robert Axelrod's two tournaments, held around 1980. Notably, it was both the most successful in direct competition; the phrase came from another phrase "tip for tap", first used in 1558. An agent using this strategy will first cooperate subsequently replicate an opponent's previous action. If the opponent was cooperative, the agent is cooperative. If not, the agent is not; this is similar to reciprocal altruism in biology. The success of the tit-for-tat strategy, cooperative despite that its name emphasizes an adversarial nature, took many by surprise. Arrayed against strategies produced by various teams it won in two competitions. After the first competition, new strategies formulated to combat tit-for-tat failed due to their negative interactions with each other; this result may give insight into how groups of animals have come to live in cooperative societies, rather than the individualistic "red in tooth and claw" way that might be expected from individuals engaged in a Hobbesian state of nature.
This, its application to human society and politics, is the subject of Robert Axelrod's book The Evolution of Cooperation. Moreover, the tit-for-tat strategy has been of beneficial use to social psychologists and sociologists in studying effective techniques to reduce conflict. Research has indicated that when individuals who have been in competition for a period of time no longer trust one another, the most effective competition reverser is the use of the tit-for-tat strategy. Individuals engage in behavioral assimilation, a process in which they tend to match their own behaviors to those displayed by cooperating or competing group members. Therefore, if the tit-for-tat strategy begins with cooperation cooperation ensues. On the other hand, if the other party competes the tit-for-tat strategy will lead the alternate party to compete as well; each action by the other member is countered with a matching response, competition with competition and cooperation with cooperation. In the case of conflict resolution, the tit-for-tat strategy is effective for several reasons: the technique is recognized as clear, nice and forgiving.
Firstly, It is a recognizable strategy. Those using it recognize its contingencies and adjust their behavior accordingly. Moreover, it is considered to be nice as it begins with cooperation and only defects in following competitive move; the strategy is provocable because it provides immediate retaliation for those who compete. It is forgiving as it produces cooperation should the competitor make a cooperative move; the implications of the tit-for-tat strategy have been of relevance to conflict research and many aspects of applied social science. Take for example the following infinitely repeated prisoners dilemma game: The Tit for Tat strategy copies what the other player choose. If player's cooperate by playing strategy they cooperate forever. Cooperation gives the following payoff: 6 + 6 δ + 6 δ 2 + 6 δ 3... Which can be further simplified using the geometric sum rule: 6 + 6 δ + 6 δ 2 + 6 δ 3... 6 6 1 − δ If a player deviates to defecting the next round they get punished. Alternate between outcomes where p1 cooperates and p2 deviates, vice versa.
Deviation gives the following payoff: 9 + 2 δ + 9 δ 2 + 2 δ 3 + 9 δ 4 + 2 δ 5... This equation can be split in the following way 9 + 9 δ 2 + 9 δ 4... 2 δ + 2 δ 3 + 2 δ 5... Simplify the 2 equations using the geometric sum rule: 9 + 9 δ 2 + 9 δ 4... 9 9 ∗ 1 1 − δ 2 {\d
Simultaneous game
In game theory, a simultaneous game is a game where each player chooses his action without knowledge of the actions chosen by other players. Simultaneous games contrast with sequential games, which are played by the players taking turns. Normal form representations are used for simultaneous games. Rock-paper-scissors, a played hand game, is an example of a simultaneous game. Both players make a decision without knowledge of the opponent's decision, reveal their hands at the same time. There are two players in this game and each of them has three different strategies to make their decision. We will display Player 1's strategies as Player 2's strategies as columns. In the table, the numbers in red represent the payoff to Player 1, the numbers in blue represent the payoff to Player 2. Hence, the pay off for a 2 player game in rock-paper-scissors will look like this: The prisoner's dilemma is an example of a simultaneous game; some variants of chess that belong to this class of games include Synchronous chess and Parity chess.
Sequential game Simultaneous action selection Bibliography Pritchard, D. B.. Beasley, John, ed; the Classified Encyclopedia of Chess Variants. John Beasley. ISBN 978-0-9555168-0-1