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 be a set of possible "states of the world" or "alternatives". Society wishes to choose a single state from . For example, in a single-winner election, may represent the set of candidates; in a resource allocation setting, may represent all possible allocations of the resource.
Let be a finite set, representing a collection of individuals. For each , let be a utility function, describing the amount of happiness that individual i derives from each possible state.
The Nash welfare rule selects a state which maximizes the product of utilities:
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 , or the geometric mean . 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 , consider the rule maximizing the generalized power mean . Taking gives the utilitarian rule; the limit gives the egalitarian rule (refined by lexicographic max-min optimization); and the limit 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 is multiplied by a positive constant (for example, because each individual reports utilities in different units), the product of utilities is multiplied by the constant , 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 of the resource, her utility is , while Bob's utility from the remaining fraction is ; Alice enjoys the resource five times more intensely than Bob. The utilitarian rule maximizes , which is increasing in , so it gives the entire resource to Alice: , with utility profile . Bob is left with nothing. The egalitarian rule maximizes the minimum utility, which requires , giving and the utility profile . Equality is attained, but the total welfare is small. The Nash welfare rule maximizes , which is maximized at , with utility profile . 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 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 . 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 , attained uniquely by giving item a to Alice and items b and c to Bob, with utility profile . 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 , where is the amount given to P. The sum is maximized at : 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 , which is maximized at : 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 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 , 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