Helpful context:

Negotiation is the process by which self-interested parties reach agreements. The mathematical theory of negotiation makes this precise: preferences are encoded as utility functions, agreements are points in a joint utility space, and “good” outcomes are characterized by axioms. The hard part is connecting these abstract criteria to what people actually value - and to mechanisms that can be implemented.

The key tension is between what agents want and what they are willing to reveal. An agent who knows their own preferences has an incentive to misrepresent them if misrepresentation leads to a better outcome. Mechanism design is the subfield that confronts this problem directly: given a desired social objective, can we construct a procedure such that self-interested agents, acting in their own interest, collectively produce the desired outcome? The answer depends heavily on the structure of preferences and what social objectives we take to be desirable.

Understanding negotiation mathematically requires three ingredients: a language for expressing preferences (utility theory), a criterion for evaluating outcomes (social welfare), and a consistency condition on how alternatives are compared (independence of irrelevant alternatives). Each is subtle, and their interaction is where impossibility theorems live.

Preference Profiles and Utility

Each agent $i$ has a preference relation $\succeq_i$ over outcomes in a set $X$, where $x \succeq_i y$ means agent $i$ weakly prefers $x$ to $y$. Under mild rationality axioms - completeness ($x \succeq_i y$ or $y \succeq_i x$ for all $x, y$) and transitivity ($x \succeq_i y$ and $y \succeq_i z$ implies $x \succeq_i z$) - this relation is representable by a utility function $u_i: X \to \mathbb{R}$, meaning $x \succeq_i y \iff u_i(x) \geq u_i(y)$.

A preference profile is the tuple $(u_1, \ldots, u_n)$ of all agents' utility functions. It is the complete description of the preference environment from which mechanisms and solutions are designed.

Ordinal utility only ranks outcomes; it is unique up to any strictly increasing transformation. Cardinal utility encodes the intensity of preference: a cardinal utility function is unique only up to positive affine transformations $u_i \mapsto a u_i + b$ with $a > 0$. Most bargaining theory requires cardinal utility, because it asks how much an agent gains or loses, not merely which outcome they prefer. Interpersonal comparison of utilities - comparing $u_i(x)$ to $u_j(x)$ across different agents - is philosophically contested (there is no natural common scale) but practically unavoidable in mechanism design, where trade-offs between agents must be resolved.

The Preference Elicitation Bottleneck

To design good mechanisms, you need to know agents' preferences. Two obstacles arise immediately. First, agents may not know their own preferences precisely, especially over novel or complex outcomes. Second, even if they do, truthful revelation is not always incentive-compatible: an agent may be able to obtain a better outcome by misreporting.

The elicitation bottleneck is a combinatorial obstacle. In multi-issue negotiation - where the outcome is a bundle of decisions across many attributes - the number of possible outcomes is exponential in the number of attributes. A full preference ordering over $2^k$ outcomes requires the agent to specify $2^k$ numbers, which is infeasible even for moderate $k$. Solutions include:

  • Compact preference representations: CP-nets (conditional preference networks) encode preferences over attributes conditionally on other attributes, achieving exponential compression under independence assumptions. GAI-nets (generalized additive independence) decompose utility as a sum over small clusters of attributes.
  • Structured elicitation: rather than asking for a full preference ordering, ask targeted comparison queries designed to identify the best alternative with few questions.
  • Preference learning: infer preferences from observed behavior - choices, rankings, click data - using regression or Bayesian models.

The incentive constraint is handled by the revelation principle: any social choice function implementable by any mechanism (possibly complex, indirect) is also implementable by a direct mechanism in which agents report their types and truth-telling is a Bayesian Nash equilibrium. This reduces the design problem: focus on direct mechanisms where agents report truthfully. The VCG mechanism (Vickrey-Clarke-Groves) implements any affinely maximizable social choice function in dominant strategies by charging each agent the externality they impose on others.

Social Welfare and Efficiency

Given a preference profile $(u_1, \ldots, u_n)$, how do we select an outcome? Different social welfare functions embody different normative commitments.

Utilitarian social welfare maximizes the total utility $\sum_i u_i(x)$. It is efficient in the sense of maximizing the aggregate, but indifferent to distribution: it would accept a world in which one agent is extremely well-off and all others are at their minimum, if the total is high enough.

Egalitarian social welfare maximizes $\min_i u_i(x)$, the worst-off agent’s utility. It is sensitive to distribution but can sacrifice large aggregate gains for marginal improvements to the minimum.

Nash product social welfare maximizes $\prod_i (u_i(x) - d_i)$, where $d_i$ is agent $i$’s disagreement payoff - what they receive if no agreement is reached. This balances efficiency and fairness and arises naturally as the Nash bargaining solution. It is scale-invariant (multiplying any $u_i$ by a positive constant does not change the maximizer) and is the only criterion satisfying the four Nash bargaining axioms.

Pareto optimality is a minimal necessary condition: outcome $x$ is Pareto optimal if there is no $y \in X$ such that $u_i(y) \geq u_i(x)$ for all $i$ with strict inequality for at least one $i$. Any solution that fails Pareto optimality is leaving value on the table - there is a universally better alternative that a rational mechanism should select instead.

$$\text{Pareto optimal}: \nexists y \in X \text{ such that } u_i(y) \geq u_i(x) ;\forall i \text{ and } u_j(y) > u_j(x) \text{ for some } j$$

Independence of Irrelevant Alternatives

Arrow’s IIA states that the social ranking of alternatives $x$ versus $y$ should depend only on individual agents' rankings of $x$ versus $y$, not on their attitudes toward any third alternative $z$. This is a coherence condition: if you preferred $x$ to $y$ before learning that $z$ is unavailable, your preference should not change - $z$’s availability is irrelevant to the $x$-vs-$y$ comparison.

Arrow’s impossibility theorem shows that no social welfare function on three or more alternatives and two or more agents simultaneously satisfies Pareto optimality, IIA, and non-dictatorship (where non-dictatorship means there is no agent $i$ whose strict preferences always determine the social ranking regardless of other agents' preferences). Any two of the three are simultaneously satisfiable; all three are not.

$$\text{Arrow (1951): } \nexists \text{ SWF satisfying Pareto + IIA + non-dictatorship for } |X| \geq 3, n \geq 2$$

IIA in bargaining takes a different, weaker form. Nash’s version: if we shrink the feasible set $S$ to $T \subseteq S$ but the Nash solution $F^N(S, d)$ is still in $T$, then $F^N(T, d) = F^N(S, d)$. The solution is determined locally - only the solution point and the local shape of the frontier matter, not the global shape of $S$. This is what uniquely characterizes the Nash bargaining solution.

IIA has principled critics. The Allais paradox and context effects in psychology document systematic violations by real agents. More to the point, there are coherent reasons to violate IIA: the Kalai-Smorodinsky solution drops IIA in favor of individual monotonicity (expanding the feasible set in a way that benefits agent $i$ should not hurt agent $i$), recovering a different, equally axiomatically grounded solution.

Stable Matching and Gale-Shapley

The stable matching problem (Gale and Shapley, 1962) asks: given $n$ men and $n$ women, each with a complete preference ranking over the other side, find a matching such that no man-woman pair both prefer each other to their current partners.

A blocking pair $(m, w)$ exists if $m$ prefers $w$ to his current partner AND $w$ prefers $m$ to her current partner. A matching is stable if it has no blocking pairs. Unstable matchings fall apart spontaneously - the blocking pair will elope.

Gale-Shapley algorithm (deferred acceptance):

Initialize: all men and women unmatched
While some man m is unmatched and has not proposed to every woman:
    w = highest-ranked woman m has not yet proposed to
    m proposes to w
    If w is unmatched: w tentatively accepts m
    If w prefers m to her current partner m':
        w drops m' (m' becomes unmatched), tentatively accepts m
    Else: w rejects m

Theorem (Gale-Shapley 1962). The algorithm always terminates with a stable matching, in at most $n^2$ proposals.

Proof of stability. Suppose $(m, w)$ is a blocking pair. Since $m$ prefers $w$, he proposed to $w$ before his final partner. When $m$ proposed to $w$, she either rejected him immediately (preferring her then-partner) or accepted then later dropped him for someone better. Either way, $w$’s final partner is at least as good as $m$ from $w$’s perspective - so $w$ does not prefer $m$. Contradiction. $\square$

Optimality. The man-proposing Gale-Shapley gives every man his best stable partner - the best partner he gets in ANY stable matching. It gives every woman her worst stable partner. The woman-proposing version flips this. This is a theorem, not an accident: Gale-Shapley is strategyproof for the proposing side (truth-telling is a dominant strategy), but NOT for the receiving side.

Applications.

  • National Resident Matching Program (NRMP): since 1952, US medical students are matched to hospital residency programs. The algorithm was identified as Gale-Shapley in retrospect. Roth won the 2012 Nobel Prize for this work and for redesigning the Boston school choice and NYC high school matching systems.
  • College admissions, job markets, kidney exchange.

Extension: Roommate problem. Stable matching in a non-bipartite setting (everyone can be matched with anyone). Stable matchings need not exist. Irving’s algorithm handles this case.

Price of stability in matching. Every stable matching has the same set of matched and unmatched agents (this is the rural hospital theorem - hospitals that fill under one stable matching fill under all stable matchings). So stability is a strong global property.

Summary

Concept Key Definition
Preference profile Tuple of utility functions $(u_1,\ldots,u_n)$ over outcomes
Cardinal utility Unique up to positive affine transformation; encodes preference intensity
Elicitation bottleneck Exponential outcome space makes full preference queries infeasible
Utilitarian welfare $\sum_i u_i(x)$ - maximizes aggregate utility
Egalitarian welfare $\min_i u_i(x)$ - maximizes worst-off agent’s utility
Nash product $\prod_i (u_i(x) - d_i)$ - balances efficiency and fairness
Pareto optimality No outcome makes all agents weakly better and one strictly better
VCG mechanism Implements utilitarian optimum in dominant strategies via externality pricing
IIA (Arrow) Social ranking of $x, y$ independent of rankings of irrelevant $z$
Arrow’s theorem No SWF satisfies Pareto optimality + IIA + non-dictatorship
Stable matching No blocking pair; Gale-Shapley deferred acceptance finds one in $O(n^2)$
Rural hospital theorem Every stable matching matches the same set of agents

Read next: