Fair Division

A division is proportional if each of n agents believes they received at least 1/n of the total value, according to their own subjective valuation. This is a baseline guarantee in cake-cutting and resource allocation.

• Key Property: Ensures no agent feels they received less than their fair share.
• Example: Three agents dividing a cake. A proportional division gives each a piece they value as at least one-third of the whole.
• Protocol: The Dubins-Spanier Moving Knife procedure is a classic protocol guaranteeing a proportional division.

An allocation is envy-free if no agent prefers another agent's bundle of resources to their own. This is a stronger condition than proportionality, as it ensures agents are content with their own allocation relative to others.

• Key Property: Eliminates interpersonal envy; each agent values their bundle at least as much as any other's.
• Relation: An envy-free division for n agents is always proportional, but the converse is not always true.
• Challenge: Guaranteeing envy-freeness for three or more agents with indivisible items is generally impossible without additional concessions.

An allocation is Pareto efficient (or Pareto optimal) if no alternative allocation can make at least one agent better off without making another agent worse off. It defines an economic frontier of possible outcomes.

• Key Property: Represents allocative efficiency; no 'waste' of value exists from the agents' perspectives.
• Trade-offs: A division can be fair but inefficient, or efficient but unfair. Ideal protocols seek Pareto-improvements that enhance at least one agent's utility without harming others.
• Application: Central to evaluating negotiation outcomes in multi-issue bargaining, where trade-offs between issues can lead to Pareto-optimal agreements.

An allocation is equitable if all agents derive equal utility from their respective bundles. Unlike envy-freeness, which is comparative, equitability focuses on absolute equality of perceived happiness.

• Key Property: Agents' subjective valuations of their own shares are identical.
• Measurement: Requires interpersonally comparable utility functions, which is often a strong assumption.
• Combined Goal: A division that is both envy-free and equitable is considered a highly robust fair division, sometimes called a perfect division.

A division protocol is strategy-proof (or incentive-compatible) if agents maximize their utility by reporting their true preferences, regardless of what others report. This prevents strategic manipulation.

• Key Property: Eliminates the benefit of lying about valuations, simplifying agent reasoning.
• Limitation: The Gibbard-Satterthwaite theorem implies severe restrictions on strategy-proof protocols, especially with indivisible goods.
• Example: The Vickrey-Clarke-Groves (VCG) mechanism is a strategy-proof auction protocol, but applying it to general fair division is complex.

An allocation is in the core if no subset (coalition) of agents can defect, reallocate resources among themselves, and all achieve a strictly better outcome. It is a solution concept from cooperative game theory applied to coalition formation.

• Key Property: Guarantees coalitional stability; the allocation is resistant to group deviations.
• Strength: A stronger condition than both Pareto efficiency and individual rationality.
• Computational Challenge: Determining if an allocation is in the core is often computationally hard (NP-complete), making it difficult to verify in large, complex agent systems.

A simple, sequential protocol for allocating indivisible items without side payments. Agents take turns according to a predefined or negotiated sequence (e.g., 1, 2, 3, 3, 2, 1). On their turn, an agent picks their most preferred remaining item. While not guaranteeing envy-freeness or proportionality in general, it is strategy-proof for agents with additive valuations when the sequence is known in advance. Its efficiency depends heavily on the chosen sequence, making it a common heuristic in multi-agent resource allocation due to its low computational overhead and transparency.

A state in a negotiation or resource allocation where no agent can be made better off without making at least one other agent worse off. It represents an efficiency frontier of possible agreements.

• Key Insight: A fair division is often sought among the set of Pareto optimal outcomes, as any non-Pareto-optimal division is wasteful.
• Example: In dividing a budget between two projects, an allocation is Pareto optimal if shifting any funds from one project to the other would harm the first project's outcome more than it helps the second.

A fairness criterion where no agent prefers the bundle of resources allocated to another agent over its own. It is a stronger guarantee than simple proportionality.

• Formal Definition: An allocation is envy-free if for every pair of agents i and j, agent i values its own bundle at least as much as the bundle given to agent j.
• Challenge: Achieving envy-freeness alongside efficiency (Pareto optimality) can be computationally hard, especially with indivisible goods.
• Protocol Example: The Selfridge-Conway procedure is a discrete protocol for envy-free cake-cutting among three agents.

A fundamental fairness criterion stating that in a division among n agents, each agent should receive a bundle it values as at least 1/n of the total value.

• Baseline Fairness: This is often the minimal guarantee sought in fair division protocols.
• Achievability: Proportional divisions are generally easier to compute than envy-free ones. The divide-and-choose protocol for two agents guarantees proportionality.
• Agent Context: In multi-agent systems, a proportional allocation ensures no agent is systematically disadvantaged in the collective outcome.

The inverse of game theory, involving the design of negotiation protocols or 'games' so that the strategic interactions of self-interested agents lead to a socially desirable outcome, such as an efficient or fair division.

• Goal: To engineer protocols where agents' dominant strategies align with the system's objective (e.g., truth-telling about valuations).
• Key Principle: The Revelation Principle states that for any mechanism, an equivalent direct revelation mechanism exists where truth-telling is optimal.
• Application: Auction formats like the Vickrey auction are classic examples of mechanism design for fair and efficient allocation.

A protocol where agents compete to acquire a resource or task by submitting bids according to predefined auction rules, providing a structured market mechanism for fair division.

• Common Types: English (ascending price), Dutch (descending price), Vickrey (sealed-bid, second-price), and combinatorial auctions for bundle of items.
• Fairness & Efficiency: Well-designed auctions can achieve Pareto-optimal allocations and, under certain conditions, strategy-proofness.
• Computational Challenge: The Winner Determination Problem in combinatorial auctions is NP-hard, requiring sophisticated optimization for multi-agent systems.

A framework for modeling multi-agent coordination problems as a set of variables, domains, and constraints distributed among agents, who must collaboratively find a solution that optimizes a global objective, often involving fair resource division.

• Model: Each agent controls some variables. Constraints define costs/utilities based on variable assignments across agents.
• Solution Methods: Algorithms like DPOP (Distributed Pseudo-tree Optimization Procedure) allow agents to find optimal or near-optimal allocations without central control.
• Fair Division Link: DCOP can encode fair division problems where the global objective is to maximize social welfare or minimize envy, with solutions found via distributed message passing.