|
Fractional Pareto Efficiency
In economics and computer science, Fractional Pareto efficiency or Fractional Pareto optimality (fPO) is a variant of Pareto efficiency used in the setting of fair allocation of discrete objects. An allocation of objects is called ''discrete'' if each item is wholly allocated to a single agent; it is called ''fractional'' if some objects are split among two or more agents. A discrete allocation is called Pareto-efficient (PO) if it is not Pareto-dominated by any discrete allocation; it is called fractionally Pareto-efficient (fPO) if it is not Pareto-dominated by any discrete ''or fractional'' allocation.Barman, S., Krishnamurthy, S. K., & Vaish, R., "Finding Fair and Efficient Allocations", ''EC '18: Proceedings of the 2018 ACM Conference on Economics and Computation'', June 2018. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO. Formal definitions There is a set of ''n'' agents and a set of ''m'' objects. An ''allocatio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Economics
Economics () is the social science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services. Economics focuses on the behaviour and interactions of Agent (economics), economic agents and how economy, economies work. Microeconomics analyzes what's viewed as basic elements in the economy, including individual agents and market (economics), markets, their interactions, and the outcomes of interactions. Individual agents may include, for example, households, firms, buyers, and sellers. Macroeconomics analyzes the economy as a system where production, consumption, saving, and investment interact, and factors affecting it: employment of the resources of labour, capital, and land, currency inflation, economic growth, and public policies that have impact on glossary of economics, these elements. Other broad distinctions within economics include those between positive economics, desc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bellman–Ford Algorithm
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers. The algorithm was first proposed by , but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively. Edward F. Moore also published a variation of the algorithm in 1959, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm. Negative edge weights are found in various applications of graphs, hence the usefulness of this algorithm. If a graph contains a "negative cycle" (i.e. a cycle whose edges sum to a negative value) that is reachable from the source, then there is no ''cheapest'' path: any path that has a point on the negative cycle can be made cheaper by one more walk ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sperner's Lemma
In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring (described below) of a triangulation of an simplex contains a cell whose vertices all have different colors. The initial result of this kind was proved by Emanuel Sperner, in relation with proofs of invariance of domain. Sperner colorings have been used for effective computation of fixed points and in root-finding algorithms, and are applied in fair division (cake cutting) algorithms. Finding a Sperner coloring or equivalently a Brouwer fixed point is now believed to be an intractable computational problem, even in the plane, in the general case. The problem is PPAD-complete, a complexity class invented by Christos Papadimitriou. According to the Soviet ''Mathematical Encyclopaedia'' (ed. I.M. Vinogradov), a related 1929 theorem (of Knaster, Borsuk and Mazurkiewicz) had als ... [...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 that t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Basic Feasible Solution
In the theory of linear programming, a basic feasible solution (BFS) is a solution with a minimal set of non-zero variables. Geometrically, each BFS corresponds to a corner of the polyhedron of feasible solutions. If there exists an optimal solution, then there exists an optimal BFS. Hence, to find an optimal solution, it is sufficient to consider the BFS-s. This fact is used by the simplex algorithm, which essentially travels from some BFS to another until an optimal one is found. Definitions Preliminaries: equational form with linearly-independent rows For the definitions below, we first present the linear program in the so-called ''equational form'': :maximize \mathbf \mathbf :subject to A\mathbf = \mathbf and \mathbf \ge 0 where: * \mathbf and \mathbf are vectors of size ''n'' (the number of variables); * \mathbf is a vector of size ''m'' (the number of constraints); * A is an ''m''-by-''n'' matrix; * \mathbf \ge 0 means that all variables are non-negative. Any linear pro ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the mathematical optimization, optimization of a linear objective function, subject to linear equality and linear inequality Constraint (mathematics), constraints. Its feasible region is a convex polytope, which is a set defined as the intersection (mathematics), intersection of finitely many Half-space (geometry), half spaces, each of which is defined by a linear inequality. Its objective function is a real number, real-valued affine function, affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polytope where ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Serial Dictatorship
In social choice theory, a dictatorship mechanism is a rule by which, among all possible alternatives, the results of voting mirror a single pre-determined person's preferences, without consideration of the other voters. Dictatorship by itself is not considered a good mechanism in practice, but it is theoretically important: by Arrow's impossibility theorem, when there are at least three alternatives, dictatorship is the only ranked voting electoral system that satisfies ''unrestricted domain'', ''Pareto efficiency'', and ''independence of irrelevant alternatives''. Similarly, by Gibbard's theorem, when there are at least three alternatives, dictatorship is the only ''strategyproof'' rule. Non-dictatorship is a property of more common voting rules, in which the results are influenced by the preferences of all individuals. This property is satisfied if there is no single voter ''i'' with the individual preference order P, such that P is always the societal ("winning") preference ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
CoNP-complete
In complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-complete problem with only polynomial overhead. If P is different from co-NP, then all of the co-NP-complete problems are not solvable in polynomial time. If there exists a way to solve a co-NP-complete problem quickly, then that algorithm can be used to solve all co-NP problems quickly. Each co-NP-complete problem is the complement of an NP-complete problem. There are some problems in both NP and co-NP, for example all problems in P or integer factorization. However, it is not known if the sets are equal, although inequality is thought more likely. See co-NP and NP-complete for more details. Fortune showed in 1979 that if any sparse language is co-NP-complete (or even just co-NP-hard), then , a critical foundation for Mahaney's theorem. Formal definition A decision prob ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Program
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (also known as mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polytope, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polytope where this function has the smallest (or largest) value if such a point exists. Linear programs are problems that can be expressed in canonical form as : \begin & \text && \ma ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
First Welfare Theorem
There are two fundamental theorems of welfare economics. The first states that in economic equilibrium, a set of complete markets, with complete information, and in perfect competition, will be Pareto optimal (in the sense that no further exchange would make one person better off without making another worse off). The requirements for perfect competition are these: # There are no externalities and each actor has perfect information. # Firms and consumers take prices as given (no economic actor or group of actors has market power). The theorem is sometimes seen as an analytical confirmation of Adam Smith's "invisible hand" principle, namely that ''competitive markets ensure an efficient allocation of resources''. However, there is no guarantee that the Pareto optimal market outcome is socially desirable, as there are many possible Pareto efficient allocations of resources differing in their desirability (e.g. one person may own everything and everyone else nothing). The second ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical disciplines (including the design and implementation of Computer architecture, hardware and Computer programming, software). Computer science is generally considered an area of research, academic research and distinct from computer programming. Algorithms and data structures are central to computer science. The theory of computation concerns abstract models of computation and general classes of computational problem, problems that can be solved using them. The fields of cryptography and computer security involve studying the means for secure communication and for preventing Vulnerability (computing), security vulnerabilities. Computer graphics (computer science), Computer graphics and computational geometry address the generation of images. Progr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Fisher Market
Fisher market is an economic model attributed to Irving Fisher. It has the following ingredients: * A set of m divisible products with pre-specified supplies (usually normalized such that the supply of each good is 1). * A set of n buyers. * For each buyer i=1,\dots,n, there is a pre-specified monetary budget B_i. Each product j has a price p_j; the prices are determined by methods described below. The price of a ''bundle'' of products is the sum of the prices of the products in the bundle. A bundle is represented by a vector x = x_1,\dots,x_m, where x_j is the quantity of product j. So the price of a bundle x is p(x)=\sum_^m p_j\cdot x_j. A bundle is ''affordable'' for a buyer if the price of that bundle is at most the buyer's budget. I.e, a bundle x is affordable for buyer i if p(x)\leq B_i. Each buyer has a preference relation over bundles, which can be represented by a utility function. The utility function of buyer i is denoted by u_i. The ''demand set'' of a buyer is the s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
