|
Market Equilibrium Computation
Market equilibrium computation (also called competitive equilibrium computation or clearing-prices computation) is a computational problem in the intersection of economics and computer science. The input to this problem is a ''market'', consisting of a set of ''resources'' and a set of ''agents''. There are various kinds of markets, such as Fisher market and Arrow–Debreu market, with divisible or indivisible resources. The required output is a ''competitive equilibrium'', consisting of a ''price-vector'' (a price for each resource), and an ''allocation'' (a resource-bundle for each agent), such that each agent gets the best bundle possible (for him) given the budget, and the market ''clears'' (all resources are allocated). Market equilibrium computation is interesting due to the fact that a competitive equilibrium is always Pareto efficient. The special case of a Fisher market, in which all buyers have equal incomes, is particularly interesting, since in this setting a competiti ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computational Problem
In theoretical computer science, a computational problem is one that asks for a solution in terms of an algorithm. For example, the problem of factoring :"Given a positive integer ''n'', find a nontrivial prime factor of ''n''." is a computational problem that has a solution, as there are many known integer factorization algorithms. A computational problem can be viewed as a set of ''instances'' or ''cases'' together with a, possibly empty, set of ''solutions'' for every instance/case. The question then is, whether there exists an algorithm that maps instances to solutions. For example, in the factoring problem, the instances are the integers ''n'', and solutions are prime numbers ''p'' that are the nontrivial prime factors of ''n''. An example of a computational problem without a solution is the Halting problem. Computational problems are one of the main objects of study in theoretical computer science. One is often interested not only in mere existence of an algorithm, b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Leontief Utilities
In economics, especially in consumer theory, a Leontief utility function is a function of the form: u(x_1,\ldots,x_m)=\min\left\ . where: * m is the number of different goods in the economy. * x_i (for i\in 1,\dots,m) is the amount of good i in the bundle. * w_i (for i\in 1,\dots,m) is the weight of good i for the consumer. This form of utility function was first conceptualized by Wassily Leontief. Examples Leontief utility functions represent complementary goods. For example: * Suppose x_1 is the number of left shoes and x_2 the number of right shoes. A consumer can only use pairs of shoes. Hence, his utility is \min(x_1,x_2). * In a cloud computing environment, there is a large server that runs many different tasks. Suppose a certain type of a task requires 2 CPUs, 3 gigabytes of memory and 4 gigabytes of disk-space to complete. The utility of the user is equal to the number of completed tasks. Hence, it can be represented by: \min(, , ). Properties A consumer with a Leont ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Flow Network
In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A flow network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes. As such, efficient algorithms for solving network flows can also be applied to solve problems that can be reduced to a flow network, including survey design, airline scheduling, image segmentation, and the matching prob ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Utility
In economics and consumer theory, a linear utility function is a function of the form: ::u(x_1,x_2,\dots,x_m) = w_1 x_1 + w_2 x_2 + \dots w_m x_m or, in vector form: ::u(\overrightarrow) = \overrightarrow \cdot \overrightarrow where: * m is the number of different goods in the economy. * \overrightarrow is a vector of size m that represents a bundle. The element x_i represents the amount of good i in the bundle. * \overrightarrow is a vector of size m that represents the subjective preferences of the consumer. The element w_i represents the relative value that the consumer assigns to good i. If w_i=0, this means that the consumer thinks that product i is totally worthless. The higher w_i is, the more valuable a unit of this product is for the consumer. A consumer with a linear utility function has the following properties: * The preferences are strictly monotone: having a larger quantity of even a single good strictly increases the utility. * The preferences are weakly convex, b ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Karush–Kuhn–Tucker Conditions
In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests (sometimes called first-order necessary conditions) for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied. Allowing inequality constraints, the KKT approach to nonlinear programming generalizes the method of Lagrange multipliers, which allows only equality constraints. Similar to the Lagrange approach, the constrained maximization (minimization) problem is rewritten as a Lagrange function whose optimal point is a global maximum or minimum over the domain of the choice variables and a global minimum (maximum) over the multipliers. The Karush–Kuhn–Tucker theorem is sometimes referred to as the saddle-point theorem. The KKT conditions were originally named after Harold W. Kuhn and Albert W. Tucker, who first published the conditions in 1951. Later scholars discovered that the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Geometric Mean
In mathematics, the geometric mean is a mean or average which indicates a central tendency of a finite collection of positive real numbers by using the product of their values (as opposed to the arithmetic mean which uses their sum). The geometric mean of numbers is the Nth root, th root of their product (mathematics), product, i.e., for a collection of numbers , the geometric mean is defined as : \sqrt[n]. When the collection of numbers and their geometric mean are plotted in logarithmic scale, the geometric mean is transformed into an arithmetic mean, so the geometric mean can equivalently be calculated by taking the natural logarithm of each number, finding the arithmetic mean of the logarithms, and then returning the result to linear scale using the exponential function , :\sqrt[n] = \exp \left( \frac \right). The geometric mean of two numbers is the square root of their product, for example with numbers and the geometric mean is \textstyle \sqrt = The geometric mean o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convex Optimization
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard. Definition Abstract form A convex optimization problem is defined by two ingredients: * The ''objective function'', which is a real-valued convex function of ''n'' variables, f :\mathcal D \subseteq \mathbb^n \to \mathbb; * The ''feasible set'', which is a convex subset C\subseteq \mathbb^n. The goal of the problem is to find some \mathbf \in C attaining :\inf \. In general, there are three options regarding the existence of a solution: * If such a point ''x''* exists, it is referred to as an ''optimal point'' or ''solution''; the set of all optimal points is called the ''optimal set''; and the problem is called ''solvable''. * If f is unbou ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Semialgebraic Set
In mathematics, a basic semialgebraic set is a set defined by polynomial equalities and polynomial inequalities, and a semialgebraic set is a finite union of basic semialgebraic sets. A semialgebraic function is a function with a semialgebraic graph. Such sets and functions are mainly studied in real algebraic geometry which is the appropriate framework for algebraic geometry over the real numbers. Definition Let \mathbb be a real closed field (For example \mathbb could be the field of real numbers \mathbb). A subset S of \mathbb^n is a ''semialgebraic set'' if it is a finite union of sets defined by polynomial equalities of the form \ and of sets defined by polynomial inequalities of the form \. Properties Similarly to algebraic subvarieties, finite unions and intersections of semialgebraic sets are still semialgebraic sets. Furthermore, unlike subvarieties, the complement of a semialgebraic set is again semialgebraic. Finally, and most importantly, the Tarski–Seide ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hyperplane
In geometry, a hyperplane is a generalization of a two-dimensional plane in three-dimensional space to mathematical spaces of arbitrary dimension. Like a plane in space, a hyperplane is a flat hypersurface, a subspace whose dimension is one less than that of the ambient space. Two lower-dimensional examples of hyperplanes are one-dimensional lines in a plane and zero-dimensional points on a line. Most commonly, the ambient space is -dimensional Euclidean space, in which case the hyperplanes are the -dimensional "flats", each of which separates the space into two half spaces. A reflection across a hyperplane is a kind of motion ( geometric transformation preserving distance between points), and the group of all motions is generated by the reflections. A convex polytope is the intersection of half-spaces. In non-Euclidean geometry, the ambient space might be the -dimensional sphere or hyperbolic space, or more generally a pseudo-Riemannian space form, and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Maximum Flow Problem
In Optimization (mathematics), optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow (i.e., flow from Glossary of graph theory#Direction, source s to Glossary of graph theory#Direction, sink t) is equal to the minimum capacity of an Cut (graph theory), s-t cut (i.e., cut severing s from t) in the network, as stated in the max-flow min-cut theorem. History The maximum flow problem was first formulated in 1954 by Ted Harris (mathematician), T. E. Harris and F. S. Ross as a simplified model of Soviet railway traffic flow. In 1955, Lester R. Ford, Jr. and D. R. Fulkerson, Delbert R. Fulkerson created the first known algorithm, the Ford–Fulkerson algorithm.Ford, L.R., Jr.; Fulkerson, D.R., ''Flows in Networks'', Princeton University Press ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Constant Elasticity Of Substitution
Constant elasticity of substitution (CES) is a common specification of many production functions and utility function In economics, utility is a measure of a certain person's satisfaction from a certain state of the world. Over time, the term has been used with at least two meanings. * In a Normative economics, normative context, utility refers to a goal or ob ...s in neoclassical economics. CES holds that the ability to substitute one input factor with another (for example labour with capital) to maintain the same level of production stays constant over different production levels. For utility functions, CES means the consumer has constant preferences of how they would like to substitute different goods (for example labour with consumption) while keeping the same level of utility, for all levels of utility. What this means is that both producers and consumers have similar input structures and preferences no matter the level of output or utility. The vital economic element o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
