|
Strategic Fair Division
Strategic fair division studies problems of fair division, in which participants cooperate to subdivide goods or resources fairly, from a point of view in which the participants are assumed to hide their preferences and act strategically in order to maximize their own utility, rather than playing sincerely according to their true preferences. To illustrate the difference between strategic fair division and classic fair division, consider the divide and choose procedure for dividing a cake among two agents. In classic fair division, it is assumed that the cutter cuts the cake into two pieces that are equal in his eyes, and thus he always gets a piece that he values at exactly 1/2 of the total cake value. However, if the cutter knows the chooser's preferences, he can get much more than 1/2 by acting strategically. For example, suppose the cutter values a piece by its size while the chooser values a piece by the amount of chocolate in it. So the cutter can cut the cake into two pieces ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Fair Division
Fair division is the problem in game theory of dividing a set of resources among several people who have an Entitlement (fair division), entitlement to them so that each person receives their due share. The central tenet of fair division is that such a division should be performed by the players themselves, without the need for external arbitration, as only the players themselves really know how they value the goods. There are many different kinds of fair division problems, depending on the nature of goods to divide, the criteria for fairness, the nature of the players and their preferences, and other criteria for evaluating the quality of the division. The archetypal fair division algorithm is divide and choose. The research in fair division can be seen as an extension of this procedure to various more complex settings. Description In game theory, fair division is the problem of dividing a set of resources among several people who have an Entitlement (fair division), entitlem ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Divide And Choose
Divide and choose (also cut and choose or I cut, you choose) is a procedure for fair division of a continuous resource between two parties. It involves a heterogeneous good or resource and two partners who have different preferences over parts of the cake (both want as much of it as possible). The procedure proceeds as follows: one person divides the resource into two pieces; the other person selects one of the pieces; the cutter receives the remaining piece. Since ancient times some have used the procedure to divide land, food and other resources between two parties. Currently, there is an entire field of research, called fair cake-cutting, devoted to various extensions and generalizations of cut-and-choose. Divide and choose is envy-free in the following sense: each of the two partners can act in a way that guarantees that, according to their own subjective taste, their allocated share is at least as valuable as the other share, regardless of what the other partner does. Desc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Game Theory
Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed two-person zero-sum games, in which a participant's gains or losses are exactly balanced by the losses and gains of the other participant. In the 1950s, it was extended to the study of non zero-sum games, and was eventually applied to a wide range of Human behavior, behavioral relations. It is now an umbrella term for the science of rational Decision-making, decision making in humans, animals, and computers. Modern game theory began with the idea 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 f ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Nash Equilibrium
In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed). The idea of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to his model of competition in an oligopoly. If each player has chosen a strategy an action plan based on what has happened so far in the game and no one can increase one's own expected payoff by changing one's strategy while the other players keep theirs unchanged, then the current set of strategy choices constitutes a Nash equilibrium. If two players Alice and Bob choose strategies A and B, (A, B) is a Nash equilibrium if Alice has no other strategy available that does better than A at maximizing her payoff in response to Bob choosing B, and Bob has no other strategy available that does better than B at maximizing his payoff in response to Alice c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Subgame-perfect Equilibrium
In game theory, a subgame perfect equilibrium (SPE), or subgame perfect Nash equilibrium (SPNE), is a refinement of the Nash equilibrium concept, specifically designed for dynamic games where players make sequential decisions. A strategy profile is an SPE if it represents a Nash equilibrium in every possible subgame of the original game. Informally, this means that at any point in the game, the players' behavior from that point onward should represent a Nash equilibrium of the continuation game (i.e. of the subgame), no matter what happened before. This ensures that strategies are credible and rational throughout the entire game, eliminating non-credible threats. Every finite extensive game with complete information (all players know the complete state of the game) and perfect recall (each player remembers all their previous actions and knowledge throughout the game) has a subgame perfect equilibrium. A common method for finding SPE in finite games is backward induction, where ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Price Of Anarchy
The Price of Anarchy (PoA) is a concept in economics and game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of efficiency. For example, consider the system of transportation of a city and many agents trying to go from some initial location to a destination. Here, efficiency means the average time for an agent to reach the destination. In the 'centralized' solution, a central authority can tell each agent which path to take in order to minimize the average travel time. In the 'decentralized' version, each agent chooses its own path. The Price of Anarchy measures the ratio between average travel time in the two cases. Usually the system is modeled as a game and the efficiency is some function of the outcomes (e.g. maximum delay in a network, congestion in a transportation system, social welfare in an auction, etc.). Different concepts of equilibrium can be us ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
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 se ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Mechanism Design
Mechanism design (sometimes implementation theory or institution design) is a branch of economics and game theory. It studies how to construct rules—called Game form, mechanisms or institutions—that produce good outcomes according to Social welfare function, some predefined metric, even when the designer does not know the players' true preferences or what information they have. Mechanism design thus focuses on the study of solution concepts for a class of private-information games. Mechanism design has broad applications, including traditional domains of economics such as market design, but also political science (through voting theory). It is a foundational component in the operation of the internet, being used in networked systems (such as inter-domain routing), e-commerce, and Sponsored search auction, advertisement auctions by Facebook and Google. Because it starts with the end of the game (a particular result), then works backwards to find a game that implements it, it ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Truthful Mechanism
In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly- dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have private information (e.g. their type or their value to some item), and the strategy space of each player consists of the possible information values (e.g. possible types or values), a truthful mechanism is a game in which revealing the true information is a weakly-dominant strategy for each player. An SP mechanism is also called dominant-strategy-incentive-compatible (DSIC), to distinguish it from other kinds of incentive compatibility. A SP mechanism is immune to manipulations by individual players (but not by coalitions). In contrast, in a group strategyproof mechanism, no group of people can collude to misreport their preferences in a way that makes every member better off. In a strong group strategyproof mechanism, no group of people can c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Truthful Cake-cutting
Truthful cake-cutting is the study of algorithms for fair cake-cutting that are also truthful mechanisms, i.e., they incentivize the participants to reveal their true valuations to the various parts of the cake. The classic divide and choose procedure for cake-cutting is not truthful: if the cutter knows the chooser's preferences, they can get much more than 1/2 by acting strategically. For example, suppose the cutter values a piece by its size while the chooser values a piece by the amount of chocolate in it. So the cutter can cut the cake into two pieces with almost the same amount of chocolate, such that the smaller piece has slightly more chocolate. Then, the chooser will take the smaller piece and the cutter will win the larger piece, which may be worth much more than 1/2 (depending on how the chocolate is distributed). Randomized mechanisms There is a trivial randomized truthful mechanism for fair cake-cutting: select a single agent uniformly at random, and give him/her the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Truthful Resource Allocation
Truthful resource allocation is the problem of allocating resources among agents with different valuations over the resources, such that agents are incentivized to reveal their true valuations over the resources. Model There are ''m'' resources that are assumed to be ''homogeneous'' and ''divisible''. Examples are: * Materials, such as wood or metal; * Virtual resources, such as CPU time or computer memory; * Financial resources, such as shares in firms. There are ''n'' agents. Each agent has a function that attributes a numeric value to each "bundle" (combination of resources). It is often assumed that the agents' value functions are ''linear'', so that if the agent receives a fraction ''rj'' of each resource ''j'', then his/her value is the sum of ''rj'' ∗''vj'' . Design goals The goal is to design a truthful mechanism, that will induce the agents to reveal their true value functions, and then calculate an allocation that satisfies some fairness and efficiency object ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
Rental Harmony
Rental harmony is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem and room-assignment-rent-division are alternative names to the same problem. In the typical setting, there are n partners who rent together an n-room house for cost fixed by the homeowner. Each housemate may have different preferences — one may prefer a large room, another may prefer a room with a view to the main road, etc. The following two problems should be solved simultaneously: * (a) Assign a room to each partner, * (b) Determine the amount each partner should pay, such that the sum of payments equals the fixed cost. There are several properties that we would like the assignment to satisfy. * Non-negativity (NN): all prices must be 0 or more: no partner should be paid to get a room. * Envy-freeness (EF): Given a pricing scheme (an assignment of rent to rooms), we say that a partner ''prefers'' a given room if he ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] [Amazon] |
