Social:Fractional multiwinner approval voting

Fractional multiwinner approval voting (FMAV) is a social choice setting in which there is a set of candidates, each voter votes by stating a subset of a candidates that he approves, and the goal is to determine a distribution over committees of a predetermined size k. For example, if the candidates are Alice, Batya, Chana and David, and k=2, then a possible outcome of FMAV is: "20% {Alice, Batya}, 50% {Alice, Chana}, 30% {Chana, David}". The distribution can be implemented by time-sharing (e.g. Alice and Batya will serve together 20% of the time, then Alice and Chana will serve 50% of the time, etc.). It can also be implemented by a lottery (e.g. with probability 20% the committee is {Alice, Batya}, with probability 50% the committee is {Alice, Chana}, etc.). FMAV has evolved from two simpler social choice settings:

• In multiwinner approval voting, a single committee of size k is elected deterministically. The outcome can be seen as a degenerate distribution, where one committee gets 100% and all other committees get 0%. FMAV is motivated by the observation that deterministic committee selection cannot be fair to everybody. Even positive share — the minimal requirement that every voter obtain some non-zero representation on the elected committee — is not achievable by any deterministic rule, and randomizing over committees is a standard way of circumventing this and related impossibilities.

• In fractional approval voting, a distribution over single candidates is elected; it to the special case of a single winner, k=1. The outcome can be seen as a distribution in which only singleton committees get a positive fraction, e.g. "20% Alice, 50% Chana, 30% David". Fractional approval voting can be interpreted as budget allocation; in this view, FMAV can be seen as the task of distributing a budget of k among several issues, with the additional constraint that each issue can receive at most 1.

History

Lotteries over committees of a fixed size were first studied by Cheng, Jiang, Munagala and Wang, who introduced them under the name stable lotteries as a way of rescuing the core: an integral committee that no coalition wants to deviate from is not known to exist, whereas a lottery with the analogous property in expectation always does.

An earlier precursor appears in the peer-selection literature under a different name: Aziz, Lev, Mattei, Rosenschein and Walsh select exactly k agents at random from the nominations of their peers, and show that randomization is unavoidable if such a mechanism is to be strategyproof. They also develop a rounding technique that can be used to turn a fractional committee (given as the fraction assigned to each candidate) into a lottery.

The systematic study of ex-ante and ex-post axioms in FMAV was initiated by Aziz, Lu, Suzuki, Vollen and Walsh.

Model

There is a finite set C of m candidates and a finite set N of n voters. Each voter i reports an approval set A_i ⊆ C. An instance also specifies a committee size k ≤ m.

An integral committee is a subset W ⊆ C with |W| = k. A fractional committee is a vector p = (p_c)_{c ∈ C} of numbers in [0, 1] summing to k. A lottery is a probability distribution over integral committees; it induces a unique fractional committee, whose entries are the marginal probabilities of the candidates, and a lottery inducing a given fractional committee p is called an implementation of p.

Each voter is assumed to gain a utility of 1 from every approved candidate on the committee, so that u_i(W) = |A_i ∩ W| and u_i(p) = Σ_{c ∈ Ai} p_c. The utility of a voter from a fractional committee equals their expected utility under any implementation of it, so that fractional committees and lotteries can be used interchangeably when only expected utilities matter.

A property of a lottery is called ex ante if it is a property of the induced fractional committee, and ex post if it holds for every committee in the support of the lottery. Since the fractional outcome averages over committees, ex-ante properties are typically much easier to attain, and a large part of the literature asks which pairs of an ex-ante and an ex-post property can be attained simultaneously.

Desired properties

Efficiency properties

Pareto-efficiency (PE) comes in two variants: ex-ante PE means that no other fractional committee gives at least as high a utility to every voter and a strictly higher utility to some voter. ex-post PE is the weaker requirement that every committee in the support of the lottery be Pareto-optimal among integral committees.

Efficiency interacts badly with fairness in a way that is specific to the committee setting: applying an arbitrary Pareto improvement to a fair fractional committee may destroy its fairness, so fairness and efficiency cannot in general be pursued one after the other.

Fairness properties

Ex-ante fairness is captured by variants of the notion of fair share. Two hierarchies of such axioms were adapted to committee voting by Aziz, Lu, Suzuki, Vollen and Walsh from the single-winner axioms of Bogomolnaia, Moulin and Stong:

• One hierarchy starts from the requirement that each voter receive at least a 1/n fraction of the utility they could obtain from their most preferred committee;
• The other, the strong hierarchy, starts from the requirement that each voter be able to control a k/n share of the committee.

The two are equivalent when k=1, but logically independent otherwise, so neither of their strongest members implies the other.

• Individual fair share (IFS) requires each individual voter to receive their 1/n share.
• Unanimous fair share (UFS) requires the same of every group of voters submitting identical approval sets. Strong UFS strengthens this: for every group S of voters with identical ballots, each member must receive utility at least min{|S|·k/n, |A_i|}.
• Group fair share (GFS) applies to arbitrary groups: for every S ⊆ N, the total fraction assigned to candidates approved by at least one member of S must be at least (1/n)·Σ_{i ∈ S} min{k, |A_i|}.

Group resource proportionality (GRP) was introduced by Suzuki and Vollen in order to unify the two hierarchies. It lower-bounds, for every group S, the expected number of elected candidates approved by some member of S. The bound is not the group's proportional entitlement |S|·k/n, because a candidate can absorb at most one unit of the resource and a group approving few candidates cannot spend its whole entitlement; the entitlement is therefore discounted by the largest shortfall of any subgroup:

Σ_{c ∈ ∪i ∈ SAi} p_c ≥ |S|·k/n − max_{T ⊆ S} [ |T|·k/n − |∪_{i ∈ T}A_i| ].

GRP implies both GFS and strong UFS.

The fractional core is the strongest of these notions. A fractional committee is in the fractional core if no group S of voters can pool its entitlements to buy a fractional committee of total size at most |S|·k/n that all of its members prefer. Under the fair-taxation interpertation of Lindahl, k/n is a voter's tax contribution, and the axiom says that no group could have spent its own contribution in a way that made all of its members better off. The fractional core implies GRP.

A different randomized relaxation of the core is the stable lottery of Cheng, Jiang, Munagala and Wang, which requires that for every committee of size α, the expected number of voters who prefer it to the committee drawn from the lottery be at most α·n/k.

The ex-post counterparts of these axioms are the justified representation properties — justified representation (JR), extended justified representation (EJR), its strengthening EJR+, and fully justified representation (FJR) — which are required of every committee in the support of the lottery.

Strategic properties

A rule is strategyproof if no voter can obtain a higher utility by reporting an approval set other than their true one. Since strategyproofness clashes with fairness, weaker variants are of interest, notably excludable strategyproofness, under which a voter derives utility only from candidates they claimed to approve.

Because a fair rule cannot in general be efficient among all fractional committees and strategyproof at once, the literature also studies constrained efficiency: a rule is GRP-efficient if it returns a fractional committee that is Pareto-optimal among those satisfying GRP, and GFS-efficient is defined analogously.

Robustness properties

A separate strand asks for guarantees about the candidates rather than the voters. Kehne, Schmidt-Kraepelin and Sornat argue that candidates supported by similar groups of voters should be selected with similar probabilities, and study ex-ante neutrality, monotonicity and continuity of the selection probabilities. Continuity — that a small change in the ballots induces only a small change in the distribution — is the most demanding of the three.

Rules

Maximum Nash welfare

The Nash welfare rule maximizes the product of the voters' utilities. When k = 1 it is ex-ante efficient and lies in the fractional core. This does not survive the passage to committees: Suzuki and Vollen exhibit an instance with four voters, three candidates and k = 2 whose unique Nash-optimal fractional committee violates GRP, and hence the fractional core. The failure is not a conflict with efficiency, since an ex-ante efficient GRP outcome exists in that instance; rather, Nash welfare measures fairness in a welfarist way, by aggregating utilities symmetrically, whereas GRP and the core measure it by comparison with a deserved outside option. The two coincide when k = 1, where every voter's best possible utility is 1, but diverge for larger committees, where voters' best possible utilities may be any integer up to k.

Redistributive utilitarian rule

The redistributive utilitarian rule returns a fractional committee that is ex-ante efficient and satisfies GRP, in polynomial time. It maintains weights on the voters, initially all 1, and repeatedly adds to a growing subnetwork the candidate of highest weighted approval score, recomputes a maximum flow, freezes the weights of voters whose entitlements are exhausted, and raises the remaining weights until a new candidate attains the threshold score; leftover probability is allocated greedily by score. The delicate step, which gives the rule its name, is that each maximum flow must exhaust a voter's entitlement only when strictly necessary, which is arranged by pushing flow around cycles in the residual network. For k = 1 the rule coincides with the fair utilitarian rule of Bogomolnaia, Moulin and Stong.

Generalized conditional utilitarian rule

The generalized conditional utilitarian rule maximizes utilitarian welfare subject to GRP, and is therefore GRP-efficient. It partitions the candidates into blocks of equal approval score, gives each candidate's arc into the sink a cost equal to the rank of its block, and computes a minimum-cost maximum flow, completing the outcome greedily by block. For k = 1 it specializes to the conditional utilitarian rule, which in the single-winner setting is strategyproof and maximizes welfare subject to GFS.

Random dictator

Under random dictator rules, a voter is drawn at random and the committee is chosen to suit them. These rules are strategyproof and satisfy GFS, and are thus the standard example showing that fairness and incentives are compatible at the GFS level.

Rules based on the method of equal shares

A family of rules obtains ex-ante fairness by randomizing around the output of the method of equal shares of Peters and Skowron. Aziz, Lu, Suzuki, Vollen and Walsh use it as a subroutine to obtain, in polynomial time, a lottery that is ex-post EJR together with ex-ante GFS and ex-ante strong UFS.

Robust randomized rules

Kehne, Schmidt-Kraepelin and Sornat construct randomized rules that combine ex-ante neutrality, monotonicity and continuity of candidate selection probabilities with strong ex-post proportionality. Their stability guarantees are strong enough to imply a form of differential privacy and to support dynamic committee elections in which the committee must change little as the ballots evolve.

Best-of-both-worlds results

The best-of-both-worlds agenda asks for a single lottery that satisfies strong fairness properties ex-ante, while also guaranteeing weaker fairness properties ex-post. The known combinations in committee voting are:

• ex-post EJR with ex-ante GFS and ex-ante strong UFS, in polynomial time;
• ex-post FJR with ex-ante strong UFS, by an algorithm that does not run in polynomial time;
• ex-post FJR with ex-ante GRP, and ex-post EJR+ with ex-ante GRP in polynomial time.

The last two follow from a general tool: for every committee that is affordable — meaning that the voters can pay for exactly its members out of individual budgets of k/n, spending nothing on candidates they do not approve — there is a GRP lottery all of whose committees contain it, computable in polynomial time. The FJR committee of Pierczyński, Skowron and Peters and every output of the method of equal shares are affordable, which yields the two results.

Impossibility results

• No deterministic rule satisfies positive share, the minimal requirement that every voter be represented by at least one elected candidate. This is the basic motivation for randomizing.
• No rule is both strategyproof and GRP-efficient, and none is both strategyproof and GFS-efficient. This is a genuinely multiwinner phenomenon: in the single-winner setting the conditional utilitarian rule attains strategyproofness together with welfare maximization subject to GFS.
• Ex-ante neutrality, monotonicity and continuity of candidate selection probabilities cannot be obtained deterministically.
• In the more general participatory budgeting setting with heterogeneous project costs, several of the ex-ante fair share axioms are incompatible with the ex-post justified representation axioms, and a fractional outcome cannot always be implemented exactly.

Computational aspects

Every fractional committee of size k can be implemented by a lottery over integral committees of size k, and such an implementation is computable in polynomial time by the randomized rounding scheme of Aziz, Lev, Mattei, Rosenschein and Walsh; consequently algorithmic results stated for fractional committees carry over to lotteries. This convenience is specific to committee voting, and fails in participatory budgeting with heterogeneous costs.

The computational status of the fairness axioms differs sharply:

• GRP outcomes always exist and are computable in polynomial time, because a fractional committee satisfies GRP if and only if it dominates, coordinate-wise, some maximum flow on the network that joins a source to each voter with capacity k/n, each voter to the candidates they approve, and each candidate to a sink with capacity 1. Whether a given fractional committee satisfies GRP can also be checked in polynomial time.
• The fractional core is non-empty, since a Lindahl equilibrium is a core outcome. Kroer and Peters show that a Lindahl equilibrium can be computed in polytime even in the capped setting to which FMAV belongs, by giving a convex program whose optimal solutions are Lindahl equilibria; this yields efficiently computable approximate equilibria, and hence approximately core-stable fractional committees, for separable piecewise-linear concave utilities, a class that includes the approval utilities used here. Whether an exact fractional core outcome can be computed efficiently, and whether membership in the fractional core can be verified efficiently, remain open.
• Stable lotteries always exist, by a probabilistic method argument, but no efficient algorithm for computing them under dichotomous preferences is known.