Strategic fair division

Last updated

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. [1] 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).

The research in strategic fair division has two main branches.

One branch is related to game theory and studies the equilibria in games created by fair division algorithms:

The other branch is related to mechanism design and aims to find truthful mechanisms for fair division, in particular:

Related Research Articles

An envy-free cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the envy-free criterion, namely, that every partner feels that their allocated share is at least as good as any other share, according to their own subjective valuation.

Divide and choose is a procedure for fair division of a continuous resource, such as a cake, between two parties. It involves a heterogeneous good or resource and two partners who have different preferences over parts of the cake. The protocol proceeds as follows: one person cuts the cake into two pieces; the other person selects one of the pieces; the cutter receives the remaining piece.

Adjusted Winner (AW) is an algorithm for envy-free item allocation. Given two parties and some discrete goods, it returns a partition of the goods between the two parties that is:

  1. Envy-free: Each party believes their share of the goods is as good as or better than their opponent's;
  2. Equitable: The "relative happiness levels" of both parties from their shares are equal;
  3. Pareto-optimal: no other allocation is better for one party and still at least as good for the other party; and
  4. Involves splitting at most one good between the parties.

Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments.

Distributed algorithmic mechanism design (DAMD) is an extension of algorithmic mechanism design.

<span class="mw-page-title-main">Fair cake-cutting</span> Fair division problem

Fair cake-cutting is a kind of fair division problem. The problem involves a heterogeneous resource, such as a cake with different toppings, 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. The division should be unanimously fair – each person should receive a piece believed to be a fair share.

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:

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 i and j:

Fair item allocation is a kind of the fair division problem in which the items to divide are discrete rather than continuous. The items have to be divided among several partners who potentially value them differently, and each item has to be given as a whole to a single person. This situation arises in various real-life scenarios:

A proportional cake-cutting is a kind of fair cake-cutting. It is a division of a heterogeneous resource ("cake") that satisfies the proportionality criterion, namely, that every partner feels that his allocated share is worth at least 1/n of the total.

A picking sequence is a protocol for fair item assignment. Suppose m items have to be divided among n agents. One way to allocate the items is to let one agent select a single item, then let another agent select a single item, and so on. A picking-sequence is a sequence of m agent-names, where each name determines what agent is the next to pick an item.

Various experiments have been made to evaluate various procedures for fair division, the problem of dividing resources among several people. These include case studies, computerized simulations, and lab experiments.

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.

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.

In computer science, the Robertson–Webb (RW) query model is a model of computation used by algorithms for the problem of fair cake-cutting. In this problem, there is a resource called a "cake", and several agents with different value measures on the cake. The goal is to divide the cake among the agents such that each agent will consider his/her piece as "fair" by his/her personal value measure. Since the agents' valuations can be very complex, they cannot - in general - be given as inputs to a fair division algorithm. The RW model specifies two kinds of queries that a fair division algorithm may ask the agents: Eval and Cut. Informally, an Eval query asks an agent to specify his/her value to a given piece of the cake, and a Cut query asks an agent to specify a piece of cake with a given value.

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. So fPO is a stronger requirement than PO: every fPO allocation is PO, but not every PO allocation is fPO.

In computational economics, a single-minded agent is an agent who wants only a very specific combination of items. The valuation function of such an agent assigns a positive value only to a specific set of items, and to all sets that contain it. It assigns a zero value to all other sets. A single-minded agent regards the set of items he wants as purely complementary goods.

Fair division among groups is a class of fair division problems, in which the resources are allocated among groups of agents, rather than among individual agents. After the division, all members in each group consume the same share, but they may have different preferences; therefore, different members in the same group might disagree on whether the allocation is fair or not. Some examples of group fair division settings are:

In mechanism design, a regret-free truth-telling mechanism is a mechanism in which each player who reveals his true private information does not feel regret after seeing the mechanism outcome. A regret-free mechanism incentivizes agents who want to avoid regret to report their preferences truthfully.

References

  1. ↑ Singer, Eugene (April 1962). "Extension of the Classical Rule of "Divide and Choose"". Southern Economic Journal. 28 (4): 391–394. JSTOR   1055235.
  2. ↑ Brânzei, Simina; Miltersen, Peter Bro (2013). "Equilibrium Analysis in Cake Cutting" (PDF). Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems (AAMAS '13). Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems. pp. 327–334. ISBN   9781450319935.
  3. ↑ Brânzei, Simina; Caragiannis, Ioannis; Kurokawa, David; Procaccia, Ariel D. (2016-02-21). "An Algorithmic Framework for Strategic Fair Division". Thirtieth AAAI Conference on Artificial Intelligence. 30. arXiv: 1307.2225 . doi:10.1609/aaai.v30i1.10042. S2CID   7226490.
  4. ↑ Tadenuma, Koichi; Thomson, William (1995-05-01). "Games of Fair Division". Games and Economic Behavior. 9 (2): 191–204. doi: 10.1006/game.1995.1015 . ISSN   0899-8256.
  5. ↑ Brânzei, Simina; Gkatzelis, Vasilis; Mehta, Ruta (2016-07-06). "Nash Social Welfare Approximation for Strategic Agents". arXiv: 1607.01569 [cs.GT].
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.