Nash welfare rule

In social choice and operations research, the Nash welfare rule (also called the max-product rule, the Nash-optimal rule or maximum Nash welfare, often abbreviated MNW) is a rule saying that, among all possible alternatives, society should pick the alternative which maximizes the product of the utilities of all individuals in society. The product of utilities is called the Nash social welfare, after John Forbes Nash Jr., whose solution to the cooperative bargaining problem selects the utility profile maximizing the product of the agents' gains. The corresponding social welfare function was axiomatized by Kaneko and Nakamura.

The Nash welfare rule is often described as a compromise between the utilitarian rule, which maximizes the sum of utilities and emphasizes aggregate efficiency, and the egalitarian rule, which maximizes the minimum utility and emphasizes the worst-off individual. Because the logarithm of the Nash welfare equals the sum of the logarithms of the utilities, maximizing the Nash welfare rewards increases in the utility of an agent in inverse proportion to that agent's current utility level: raising a poor agent's utility from 1 to 2 doubles the product, whereas raising a rich agent's utility from 10 to 11 increases it by only ten percent. The rule is closely related to the proportional-fair rule used in the analysis of communication networks.

Definition

Let $X$ be a set of possible "states of the world" or "alternatives". Society wishes to choose a single state from $X$. For example, in a single-winner election, $X$ may represent the set of candidates; in a resource allocation setting, $X$ may represent all possible allocations of the resource.

Let $I$ be a finite set, representing a collection of individuals. For each $i\in I$, let $u_{i}:X\to \mathbb {R} _{\geq 0}$ be a utility function, describing the amount of happiness that individual i derives from each possible state.

The Nash welfare rule selects a state $x\in X$ which maximizes the product of utilities:

$x^{\text{Nash}}\in \arg \max _{x\in X}\prod _{i\in I}u_{i}(x).$

Equivalently, since the maximizer of a product of positive numbers is also the maximizer of the sum of their logarithms, the rule selects a state maximizing $\sum _{i\in I}\log u_{i}(x)$, or the geometric mean $\left(\prod _{i\in I}u_{i}(x)\right)^{1/|I|}$. When some agents may inevitably receive zero utility, the rule is commonly refined to first maximize the number of agents with positive utility and then maximize the product of utilities among those agents.

Comparison with the utilitarian and egalitarian rules

The three rules can be viewed as members of a single family. For a parameter $p$, consider the rule maximizing the generalized power mean $\left({\tfrac {1}{|I|}}\sum _{i\in I}u_{i}(x)^{p}\right)^{1/p}$. Taking $p=1$ gives the utilitarian rule; the limit $p\to -\infty$ gives the egalitarian rule (refined by lexicographic max-min optimization); and the limit $p\to 0$ gives the Nash welfare rule. In this sense the Nash welfare rule sits strictly between efficiency and equality.

A distinctive advantage of the Nash welfare rule concerns interpersonal comparisons of utility. The utilitarian rule requires the ability to compare utility differences across individuals, and the egalitarian rule requires the ability to compare utility levels across individuals. The Nash welfare rule requires neither: if each individual utility function $u_{i}$ is multiplied by a positive constant $c_{i}$ (for example, because each individual reports utilities in different units), the product of utilities is multiplied by the constant $\prod _{i}c_{i}$, so the ranking of alternatives is unchanged. The rule is therefore invariant to independent rescaling of individual utilities, given a fixed common "zero" point; Kaneko and Nakamura's axiomatization postulates such a distinguished origin, representing one of the worst states for all individuals.

Examples

The following examples illustrate how the three rules can select three different outcomes in various social choice domains.

Dividing a divisible resource

Suppose a single divisible resource of size 1 (for example, a plot of land) has to be divided between Alice and Bob. If Alice receives a fraction $t$ of the resource, her utility is $u_{A}=10t$, while Bob's utility from the remaining fraction is $u_{B}=2(1-t)$; Alice enjoys the resource five times more intensely than Bob.

• The utilitarian rule maximizes $10t+2(1-t)$, which is increasing in $t$, so it gives the entire resource to Alice: $t=1$, with utility profile $(10,0)$. Bob is left with nothing.
• The egalitarian rule maximizes the minimum utility, which requires $10t=2(1-t)$, giving $t=1/6$ and the utility profile $(5/3,\,5/3)$. Equality is attained, but the total welfare is small.
• The Nash welfare rule maximizes $10t\cdot 2(1-t)$, which is maximized at $t=1/2$, with utility profile $(5,1)$. Each agent receives an equal share of the resource, so no agent envies the other, while the more intense preferences of Alice are still reflected in the outcome.

Allocation of indivisible items

Suppose three indivisible items a, b, c have to be allocated between Alice and Bob, whose additive valuations are given in the following table.

Agent	a	b	c
Alice	10	6	2
Bob	3	2	1

• The utilitarian rule gives every item to the agent who values it most, so Alice receives all three items; the utility profile is $(18,0)$ and Bob receives nothing.
• The egalitarian rule maximizes the minimum utility. The best attainable minimum is 4, attained uniquely by giving item b to Alice and items a and c to Bob, with utility profile $(6,4)$. Note that this allocation sacrifices a lot of Alice's utility in order to help Bob.
• The Nash welfare rule maximizes the product of utilities. The maximum product is $10\cdot 3=30$, attained uniquely by giving item a to Alice and items b and c to Bob, with utility profile $(10,3)$. The outcome is intermediate: Bob is guaranteed a substantial share, but items are not moved to Bob when his gain is small relative to Alice's loss. This allocation is also envy-free up to one item: Alice does not envy Bob, and Bob does not envy Alice once item a is removed from her bundle.

Participatory budgeting with divisible funds

Suppose a city runs a participatory budgeting process to divide a budget of $100 between two public projects, P and Q. There are 100 voters: 80 voters care only about P, and 20 voters care only about Q. The utility of each voter equals the amount of money allocated to the project that the voter cares about.

• The utilitarian rule maximizes $80x+20(100-x)$, where $x$ is the amount given to P. The sum is maximized at $x=100$: the entire budget is spent on P, and the minority of 20 voters receives nothing.
• The egalitarian rule equalizes the utilities of the two groups, splitting the budget equally: $50 to each project. The minority of 20 voters controls half the budget, which arguably over-represents them.
• The Nash welfare rule maximizes $x^{80}(100-x)^{20}$, which is maximized at $x=80$: the budget is split in proportion to the number of supporters, $80 to P and $20 to Q. Each group of voters receives influence over the budget proportional to its size, a property closely related to the core in participatory budgeting.

An analogous phenomenon appears in probabilistic voting over mutually exclusive outcomes: with 80 voters who like only outcome P and 20 voters who like only outcome Q, the utilitarian rule chooses P with certainty, an egalitarian lottery gives each outcome probability 1/2, and the Nash welfare rule selects the lottery choosing P with probability 0.8 and Q with probability 0.2, again giving each group influence proportional to its size.

Results

Allocation of divisible private goods

In the fair division of divisible private goods among agents with additive (linear) utilities, the allocation maximizing the Nash welfare coincides with the outcome of a competitive equilibrium from equal incomes (CEEI) — the equilibrium of a Fisher market in which all agents have equal budgets. This follows from the convex program of Eisenberg and Gale, whose objective is exactly the sum of the logarithms of the agents' utilities. Since Varian proved that a CEEI allocation is envy-free and Pareto-optimal, the Nash-optimal allocation of divisible goods is envy-free, proportional and Pareto-optimal. Moreover, it can be computed in polynomial time by convex optimization of the Eisenberg–Gale program.

In fair cake-cutting (allocation of a single heterogeneous divisible resource), Segal-Halevi and Sziklai prove that the Nash-optimal rule is Pareto-optimal, envy-free and satisfies a strong competitive-equilibrium condition, and — in contrast to many classic cake-cutting procedures — it is also resource-monotonic (when the cake grows, no agent is worse off) and population-monotonic (when an agent leaves, no remaining agent is worse off). They further show that it is the only rule among a natural family of welfare-maximizing rules that is both proportional and resource-monotonic.

Allocation of indivisible private goods

In fair item allocation, for agents with additive valuations, Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang prove that every allocation maximizing the Nash welfare is envy-free up to one good (EF1) and Pareto-optimal — a combination of fairness and efficiency that is difficult to achieve by other means. They also prove that the maximum Nash welfare allocation gives each agent at least a $\Theta (1/{\sqrt {n}})$ fraction of her maximin share (where n is the number of agents), and that this bound is tight in the worst case, although the approximation is much better in practice. These results extend to a mixture of divisible and indivisible goods.

Suksompong characterized MNW as the only additive welfarist rule that satisfies EF1, even in the two-agent setting. Yuen and Suksompong extended this characterization to show that it is the only welfarist rule.

In contrast to the divisible setting, computing a Nash-optimal allocation of indivisible items is computationally hard: Nguyen and Rothe prove that the problem is NP-hard, and Lee proves that it is even APX-hard, so it admits no polynomial-time approximation scheme unless P = NP. On the positive side, Cole and Gkatzelis designed the first constant-factor approximation algorithm for the Nash welfare with additive valuations, using a spending-restricted market equilibrium relaxation; Barman, Krishnamurthy and Vaish improved the approximation factor to $e^{1/e}\approx 1.45$, and additionally gave a pseudo-polynomial-time algorithm for finding an allocation that is both EF1 and Pareto-optimal, based on approximate competitive equilibria with integral allocations.

An important tractable special case is that of binary additive valuations, in which each agent values each item at 0 or 1. Halpern, Procaccia, Psomas and Shah show that in this case a Nash-optimal allocation can be computed efficiently, and that the maximum Nash welfare rule with lexicographic tie-breaking is group-strategyproof in addition to being envy-free up to one good and Pareto-optimal; they also show that the fractional maximum Nash welfare rule can be implemented as a lottery over deterministic maximum Nash welfare allocations. They conclude that, in the realm of binary additive preferences, maximum Nash welfare simultaneously achieves truthfulness, fairness and efficiency, which is impossible for general additive preferences.

Public decision making

In the public decision making model, society must decide on several independent issues, and each decision affects all agents simultaneously; this generalizes the allocation of private goods. Conitzer, Freeman and Shah prove that any outcome maximizing the Nash welfare satisfies proportionality up to one issue (Prop1) — each agent can obtain her proportional share of utility after changing the decision on a single issue in her favor — together with Pareto-optimality. Thus the fairness guarantees of the maximum Nash welfare rule carry over from private goods, in a suitably relaxed form, to public decisions.

Participatory budgeting with divisible funds

In participatory budgeting with divisible projects (where any amount of money may be allocated to each project), Fain, Goel and Munagala study fairness through the game-theoretic notion of the core: no coalition of voters should be able to deviate with its proportional share of the budget and make all its members better off. They characterize a market equilibrium for public goods (the Lindahl equilibrium), which is always in the core, and show that for a broad class of utility functions this equilibrium corresponds to the budget allocation maximizing the Nash welfare, which can be computed in polynomial time by convex programming. Hence the Nash welfare rule yields core-stable, proportionally representative budget divisions, as illustrated in the example above.

In budget-proposal aggregation, when agents have Leontief preferences (each agent evaluates a budget by taking the smallest (over all issues) ratio between the funding given to that issue and the ideal funding for that issue), the Nash welfare rule is the unique rule that is group-strategyproof and satisfies core-fair-share.

Participatory budgeting with indivisible projects

In combinatorial participatory budgeting (PB with indivisible projects - each project must be either fully funded or not funded, subject to a budget constraint), maximizing the Nash welfare corresponds to a fair variant of the knapsack problem. Fluschnik, Skowron, Triphaus and Wilker prove that computing a budget-feasible set of projects maximizing the Nash welfare is NP-hard, even in quite restricted settings, and they chart its parameterized complexity, identifying tractable special cases (for example, with respect to the number of voters or through pseudo-polynomial-time algorithms).

Proportional approval voting (PAV) is a rule closely related to MNW: it maximizes the sum of the Harmonic function of agents' utilities, which is the same as the logarithmic function up to a constant. In the special case in which all projects have the same cost (equivalent to multiwinner voting), PAV is the only rule known to satisfy both extended justified representation (EJR) and Pareto efficiency. With general cost functions, PAV is still Pareto-efficient, but does not satisfy EJR.

Fractional social choice (probabilistic voting)

In fractional social choice, agents collectively choose a lottery (or a fractional mixture) over mutually exclusive public outcomes. In the special case of fractional approval voting, in which agents have dichotomous (approval) preferences, Aziz, Bogomolnaia and Moulin study the Nash Max Product rule, which selects the mixture maximizing the product of the agents' utilities. They show that this rule is Pareto-efficient and offers the strongest welfare guarantees to coalitions among the rules they consider: any group of like-minded agents can force its commonly approved outcomes to receive probability proportional to the group's size. However, unlike the conditional-utilitarian and egalitarian rules studied in the same work, the Nash Max Product rule does not satisfy their strategyproofness properties.

Summary of the trade-off

Across these domains, a common pattern emerges. The utilitarian rule maximizes total welfare but may leave some individuals or minorities with nothing; the egalitarian rule protects the worst-off individual but may sacrifice a large amount of total welfare and may over-represent small groups in public-goods settings; the Nash welfare rule guarantees each individual and each group a share of the outcome roughly proportional to its size and preferences (envy-freeness or EF1 for private goods, core stability or proportionality for public goods), while remaining Pareto-optimal. Its main practical drawback is computational: for indivisible resources, exact maximization of the Nash welfare is NP-hard and even APX-hard, in contrast to the utilitarian rule, which is trivial to maximize for additive valuations.

See also

• Proportional-fair rule - a rule for selecting between alternatives. Aims to attain a balance between efficiency and fairness.
• Proportional-fair scheduling - a network scheduling algorithm based on similar principles.
• Nash bargaining solution - analogue of Nash welfare rule in cooperative barganing.
• Budget-proposal aggregation - another domain in which the Nash welfare rule has desirable properties.