|
Weller's Theorem
Weller's theorem is a theorem in economics. It says that a heterogeneous resource ("cake") can be divided among ''n'' partners with different valuations in a way that is both Pareto-efficient (PE) and envy-free (EF). Thus, it is possible to divide a cake fairly without compromising on economic efficiency. Moreover, Weller's theorem says that there exists a price such that the allocation and the price are a competitive equilibrium (CE) with equal incomes (EI). Thus, it connects two research fields which were previously unrelated: fair cake-cutting and general equilibrium. Background Fair cake-cutting has been studied since the 1940s. There is a heterogeneous divisible resource, such as a cake or a land-estate. There are ''n'' partners, each of whom has a personal value-density function over the cake. The value of a piece to a partner is the integral of his value-density over that piece (this means that the value is a nonatomic measure over the cake). The envy-free cake-cutting prob ... [...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] |
Utilitarian Cake-cutting
Utilitarian cake-cutting (also called maxsum cake-cutting) is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the ''sum'' of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting. Example Consider a cake with two parts: chocolate and vanilla, and two partners: Alice and George, with the following valuations: The utilitarian rule gives each part to the partner with the highest utility. In this case, the utilitarian rule gives the entire chocolate to Alice and the entire Vanilla to George. The maxsum is 13. The utilitarian division is not fair: it is not proportional since George receives less than half the total cake value, and it is not envy-free since George envies Alice. Notation The cake is calle ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pareto-efficient Envy-free Division
Efficiency and fairness are two major goals of welfare economics. Given a set of resources and a set of agents, the goal is to divide the resources among the agents in a way that is both Pareto efficient (PE) and envy-free (EF). The goal was first defined by David Schmeidler and Menahem Yaari. Later, the existence of such allocations has been proved under various conditions. Existence of PEEF allocations We assume that each agent has a preference-relation on the set of all bundles of commodities. The preferences are complete, transitive, and closed. Equivalently, each preference relation can be represented by a continuous utility function. Weakly-convex preferences ''Theorem 1 (Varian):'' ''If the preferences of all agents are convex and strongly monotone, then PEEF allocations exist.'' ''Proof'': The proof relies on the existence of a competitive equilibrium with equal incomes. Assume that all resources in an economy are divided equally between the agents. I.e, if the total e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lipschitz Continuous
In mathematical analysis, Lipschitz continuity, named after German mathematician Rudolf Lipschitz, is a strong form of uniform continuity for functions. Intuitively, a Lipschitz continuous function is limited in how fast it can change: there exists a real number such that, for every pair of points on the graph of this function, the absolute value of the slope of the line connecting them is not greater than this real number; the smallest such bound is called the ''Lipschitz constant'' of the function (or '' modulus of uniform continuity''). For instance, every function that has bounded first derivatives is Lipschitz continuous. In the theory of differential equations, Lipschitz continuity is the central condition of the Picard–Lindelöf theorem which guarantees the existence and uniqueness of the solution to an initial value problem. A special type of Lipschitz continuity, called contraction, is used in the Banach fixed-point theorem. We have the following chain of strict inclus ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Equitable Division
Equitable (EQ) cake-cutting is a kind of a fair cake-cutting problem, in which the fairness criterion is equitability. It is a cake-allocation in which the subjective value of all partners is the same, i.e., each partner is equally happy with his/her share. Mathematically, that means that for all partners and : :V_i(X_i) = V_j(X_j) Where: *X_i is the piece of cake allocated to partner ; *V_i is the value measure of partner . It is a real-valued function that, for every piece of cake, returns a number that represents the utility of partner from that piece. Usually these functions are normalized such that V_i(\emptyset)=0 and V_i(EntireCake)=1 for every . See the page on equitability for examples and comparison to other fairness criteria. Finding an equitable cake-cutting for two partners One cut - full revelation When there are 2 partners, it is possible to get an EQ division with a single cut, but it requires full knowledge of the partners' valuations. Assume that the cake ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Adjusted Winner Procedure
Adjusted Winner (AW) is a procedure for envy-free item allocation. Given two agents and some goods, it returns a partition of the goods between the two agents with the following properties: # Envy-freeness: Each agent believes that his share of the goods is at least as good as the other share; # Equitable division, Equitability: The "relative happiness levels" of both agents from their shares are equal; # Pareto-optimality: no other allocation is better for one agent and at least as good for the other agent; # At most one good has to be shared between the agents. For two agents, Adjusted Winner is the only Pareto optimal and equitable procedure that divides at most a single good. The procedure can be used in divorce settlements and partnership dissolutions, as well as international conflicts. The procedure was designed by Steven Brams and Alan D. Taylor. It was first published in their book on fair division and later in a stand-alone book. The algorithm has been commercialized t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Convex Program
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. Convex optimization has applications in a wide range of disciplines, such as automatic control systems, estimation and signal processing, communications and networks, electronic circuit design, data analysis and modeling, finance, statistics ( optimal experimental design), and structural optimization, where the approximation concept has proven to be efficient. With recent advancements in computing and optimization algorithms, convex programming is nearly as straightforward as linear programming. Definition A convex optimization problem is an optimization problem in which the objective function is a convex function and the feasible set is a con ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Utilitarian Cake-cutting
Utilitarian cake-cutting (also called maxsum cake-cutting) is a rule for dividing a heterogeneous resource, such as a cake or a land-estate, among several partners with different cardinal utility functions, such that the ''sum'' of the utilities of the partners is as large as possible. It is a special case of the utilitarian social choice rule. Utilitarian cake-cutting is often not "fair"; hence, utilitarianism is often in conflict with fair cake-cutting. Example Consider a cake with two parts: chocolate and vanilla, and two partners: Alice and George, with the following valuations: The utilitarian rule gives each part to the partner with the highest utility. In this case, the utilitarian rule gives the entire chocolate to Alice and the entire Vanilla to George. The maxsum is 13. The utilitarian division is not fair: it is not proportional since George receives less than half the total cake value, and it is not envy-free since George envies Alice. Notation The cake is calle ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Efficient Cake-cutting
Efficient cake-cutting is a problem in economics and computer science. It involves a ''heterogeneous'' resource, such as a cake with different toppings or a land with different coverings, that is assumed to be ''divisible'' - it is possible to cut arbitrarily small pieces of it without destroying their value. The resource has to be divided among several partners who have different preferences over different parts of the cake, i.e., some people prefer the chocolate toppings, some prefer the cherries, some just want as large a piece as possible, etc. The allocation should be ''economically efficient''. Several notions of efficiency have been studied: * The most common notion is Pareto-efficient, Pareto-efficiency. It means that no other allocation is better for at least one participant and at least as good for everyone. * A weaker notion is non-wastefulness. An allocation is non-wasteful if no agent receives a piece of cake that is worth 0 for him/her, and worth more than 0 for another ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Group Envy-freeness
Group envy-freeness (also called: coalition fairness) is a criterion for fair division. A group-envy-free division is a division of a resource among several partners such that every group of partners feel that their allocated share is at least as good as the share of any other group with the same size. The term is used particularly in problems such as fair resource allocation, fair cake-cutting and fair item allocation. Group-envy-freeness is a very strong fairness requirement: a group-envy-free allocation is both envy-free and Pareto efficient, but the opposite is not true. Definitions Consider a set of ''n'' agents. Each agent ''i'' receives a certain allocation ''Xi'' (e.g. a piece of cake or a bundle of resources). Each agent ''i'' has a certain subjective preference relation <''i'' over pieces/bundles (i.e. means that agent ''i'' prefers piece ''X'' to piece ''Y''). Consider a group ''G'' of the agents, with its current allocation |
Upper Semi-continuous
In mathematical analysis, semicontinuity (or semi-continuity) is a property of extended real-valued functions that is weaker than continuity. An extended real-valued function f is upper (respectively, lower) semicontinuous at a point x_0 if, roughly speaking, the function values for arguments near x_0 are not much higher (respectively, lower) than f\left(x_0\right). A function is continuous if and only if it is both upper and lower semicontinuous. If we take a continuous function and increase its value at a certain point x_0 to f\left(x_0\right) + c for some c>0, then the result is upper semicontinuous; if we decrease its value to f\left(x_0\right) - c then the result is lower semicontinuous. The notion of upper and lower semicontinuous function was first introduced and studied by René Baire in his thesis in 1899. Definitions Assume throughout that X is a topological space and f:X\to\overline is a function with values in the extended real numbers \overline=\R \cup \ = ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kakutani Fixed-point Theorem
In mathematical analysis, the Kakutani fixed-point theorem is a fixed-point theorem for set-valued functions. It provides sufficient conditions for a set-valued function defined on a convex set, convex, compact set, compact subset of a Euclidean space to have a fixed point (mathematics), fixed point, i.e. a point which is map (mathematics), mapped to a set containing it. The Kakutani fixed point theorem is a generalization of the Brouwer fixed point theorem. The Brouwer fixed point theorem is a fundamental result in topology which proves the existence of fixed points for continuous function (topology), continuous functions defined on compact, convex subsets of Euclidean spaces. Kakutani's theorem extends this to set-valued functions. The theorem was developed by Shizuo Kakutani in 1941, and was used by John Forbes Nash, Jr., John Nash in his description of Nash equilibrium, Nash equilibria. It has subsequently found widespread application in game theory and economics. Statement K ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
