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 Ai ⊆ 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 = (pc)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 ui(W) = |Ai ∩ W| and ui(p) = Σc ∈ Ai pc. 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, |Ai|}. 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, |Ai|}.
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 pc ≥ |S|·k/n − maxT ⊆ S [ |T|·k/n − |∪i ∈ TAi| ].
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