|
Nucleolus (game Theory)
In cooperative game theory, the nucleolus of a cooperative game is the solution (i.e., allocation of payments to players) that maximizes the smallest excess of a coalition (where the excess is the difference between the payment given to the coalition and the value the coalition could get by deviating). Subject to that, the nucleolus satisfies the second-smallest excess; and so on, in the leximin order. The nucleolus was introduced by David Schmeidler in 1969. Background In a cooperative game, there is a set ''N'' of ''players'', who can cooperate and form ''coalitions''. Each coalition ''S'' (subset of players) has a ''value'', which is the profit that ''S'' can make if they coopereate on their own, ignoring the other players in ''N''. The players opt to form the ''grand coalition'' - a coalition containing all players in ''N''. The question then arises, how should the value of the grand coalition be allocated among the players? Each such allocation of value is called a ''soluti ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cooperative Game Theory
In game theory, a cooperative game (or coalitional game) is a game with groups of players who form binding “coalitions” with external enforcement of cooperative behavior (e.g. through contract law). This is different from non-cooperative games in which there is either no possibility to forge alliances or all agreements need to be self-enforcing (e.g. through credible threats). Cooperative games are analysed by focusing on coalitions that can be formed, and the joint actions that groups can take and the resulting collective payoffs. Mathematical definition A cooperative game is given by specifying a value for every coalition. Formally, the coalitional game consists of a finite set of players N , called the ''grand coalition'', and a ''characteristic function'' v : 2^N \to \mathbb from the set of all possible coalitions of players to a set of payments that satisfies v( \emptyset ) = 0 . The function describes how much collective payoff a set of players can gain by ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Minimum-cost Spanning Tree Game
A minimum-cost spanning-tree game (MCST game) is a kind of a Cooperative game theory, cooperative game. In an MCST game, each player is a node in a complete graph. The graph contains an additional node - the ''supply node'' - denoted by ''s''. The goal of the players is that all of them will be connected by a path to ''s''. To this end, they need to construct a spanning tree. Each edge in the graph has a cost, and the players build the minimum cost spanning tree. The question then arises, how to allocate the cost of this MCST among the players? The solution offered by cooperative game theory is to consider the cost of each potential coalition - each subset of the players. The cost of each coalition ''S'' is the minimum cost of a spanning tree connecting only the nodes in ''S'' to the supply node ''s''. The ''value'' of ''S'' is minus the cost of ''S''. Using these definitions, various solution concepts from cooperative game theory can be applied. MCST games were introduced by Bird in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Contested Garment Rule
The contested garment (CG) rule, also called concede-and-divide, is a division rule for solving problems of conflicting claims (also called "bankruptcy problems"). The idea is that, if one claimant's claim is less than 100% of the estate to divide, then he effectively ''concedes'' the unclaimed estate to the other claimant. Therefore, we first give to each claimant, the amount conceded to him/her by the other claimant. The remaining amount is then divided equally among the two claimants. The CG rule first appeared in the Mishnah, exemplified by a case of conflict over a garment, hence the name. In the Mishnah, it was described only for two-people problems. But in 1985, Robert Aumann and Michael Maschler have proved that, in every bankruptcy problem, there is a unique division that is consistent with the CG rule for each pair of claimants. They call the rule, that selects this unique division, the CG-consistent rule (it is also called the Talmud rule). Problem description There i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ellipsoid Method
In mathematical optimization, the ellipsoid method is an iterative method for convex optimization, minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm which finds an optimal solution in a number of steps that is polynomial in the input size. History The ellipsoid method has a long history. As an iterative method, a preliminary version was introduced by Naum Z. Shor. In 1972, an approximation algorithm for real convex optimization, convex minimization was studied by Arkadi Nemirovski and David B. Yudin (Judin). As an algorithm for solving linear programming problems with rational data, the ellipsoid algorithm was studied by Leonid Khachiyan; Khachiyan's achievement was to prove the Polynomial time, polynomial-time ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Simplex Algorithm
In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial ''cones'', and these become proper simplices with an additional constraint. The simplicial cones in question are the corners (i.e., the neighborhoods of the vertices) of a geometric object called a polytope. The shape of this polytope is defined by the constraints applied to the objective function. History George Dantzig worked on planning methods for the US Army Air Force during World War II using a desk calculator. During 1946, his colleague challenged him to mechanize the planning process to distract him from taking another job. Dantzig formulated the problem as linear inequalities inspired by the work of Wassily Leontief, however, at tha ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Constraint Generation
Constraint may refer to: * Constraint (computer-aided design), a demarcation of geometrical characteristics between two or more entities or solid modeling bodies * Constraint (mathematics), a condition of an optimization problem that the solution must satisfy * Constraint (mechanics), a relation between coordinates and momenta * Constraint (computational chemistry) * Constraint (information theory), the degree of statistical dependence between or among variables * ''Constraints'' (journal), a scientific journal * Constraint (database), a concept in relational database Particular types of constraint * Biological constraints, factors which make populations resistant to evolutionary change * Carrier's constraint on lung function in long thin animals * Finite domain constraint, in mathematical solution-finding * Integrity constraints in databases ** Check constraint ** Foreign key constraint * Specific types of mechanical constraints: ** First-class constraint and second-class const ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics Of Operations Research
''Mathematics of Operations Research'' is a quarterly peer-reviewed scientific journal established in February 1976. It focuses on areas of mathematics relevant to the field of operations research such as continuous optimization, discrete optimization, game theory, machine learning, simulation methodology, and stochastic models. The journal is published by INFORMS (Institute for Operations Research and the Management Sciences). the journal has a 2017 impact factor of 1.078. History The journal was established in 1976. The founding editor-in-chief was Arthur F. Veinott Jr. (Stanford University). He served until 1980, when the position was taken over by Stephen M. Robinson, who held the position until 1986. Erhan Cinlar served from 1987 to 1992, and was followed by Jan Karel Lenstra (1993-1998). Next was Gérard Cornuéjols (1999-2003) and Nimrod Megiddo (2004-2009). Finally came Uri Rothblum (2009-2012), Jim Dai (2012-2018), and the current editor-in-chief Katya Scheinberg (20 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Minimum Spanning Tree
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components. There are many use cases for minimum spanning trees. One example is a telecommunications company trying to lay cable in a new neighborhood. If it is constrained to bury the cable only along certain paths (e.g. roads), then there would be a graph containing the points (e.g. houses) connected by those paths. Some of the paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weight ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction). Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete graphs, with their vertices placed on the points of a regular polygon, had already appeared in the 13th century, in the work of Ramon Llull. Such a drawing is sometimes referred to as a mystic rose. Properties The complete graph on vertices is denoted by . Some sources claim that the letter in this notation stands for the German word , but the German name for a complete graph, , does not contain the letter , and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory. has edg ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Separation Oracle
A separation oracle (also called a cutting-plane oracle) is a concept in the mathematical theory of convex optimization. It is a method to describe a convex set that is given as an input to an optimization algorithm. Separation oracles are used as input to ellipsoid methods. Definition Let ''K'' be a convex and compact set in R''n''. A strong separation oracle for ''K'' is an oracle (black box) that, given a vector ''y'' in R''n'', returns one of the following: *Assert that ''y'' is in ''K''. * Find a hyperplane that separates ''y'' from ''K'': a vector a in R''n'', such that a\cdot y > a\cdot x for all ''x'' in ''K''. A strong separation oracle is completely accurate, and thus may be hard to construct. For practical reasons, a weaker version is considered, which allows for small errors in the boundary of ''K'' and the inequalities. Given a small error tolerance ''d''>0, we say that: * A vector ''y'' is ''d-near K'' if its Euclidean distance from ''K'' is at most ''d''; ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Solution Concept
In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium. Many solution concepts, for many games, will result in more than one solution. This puts any one of the solutions in doubt, so a game theorist may apply a refinement to narrow down the solutions. Each successive solution concept presented in the following improves on its predecessor by eliminating implausible equilibria in richer games. Formal definition Let \Gamma be the class of all games and, for each game G \in \Gamma, let S_G be the set of strategy profiles of G. A ''solution concept'' is an element of the direct product \Pi_2^; ''i.e''., a function F: \Gamma \rightarrow \bigcup\nolimits_ 2^ such that F(G) \subseteq S_G for all G \in \Gamma. Rati ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
