Moving-phantoms mechanism

Moving-phantoms mechanisms (MPM) are rules for budget-proposal aggregation, a task in computational social choice. Their distinguishing feature is that they are strategyproof. They were developed in 2019 by Dominik Peters (as part of his Ph.D. thesis^[1]) in collaboration with Rupert Freeman, David Pennock and Jennifer Wortman Vaughan.^[2][3]

The task of budget-proposal aggregation involves a group of individuals who have a fixed budget, and need to decide how to divide it among several issues (e.g. government ministries, departments in a faculty, etc.). Each group member votes by submitting a proposal for allocating the budget, representing his ideal budget allocation in his or her opinion. The proposals of all voters should be aggregated by some pre-determined rule, to yield the actual budget allocation. Various aggregation rules have been studied.

In the average voting rule, the implemented budget is the arithmetic mean of all proposals. This rule is very simple to implement and understand. It is also arguably fair, as each voter has exactly the same influence over the total budget, namely 1/n (where n is the number of voters). The main problem with this rule is that it is very prone to manipulation: a voter who supports an issue with few other supporters would probably vote by allocating an exaggerated amount to that issue, in order to "pull" the average upwards. For example, suppose there are two issues, and your ideal budget allocation is 20,80, but you know that most other voters will give the first issue only 10 or less. Then, you will probably vote 100,0, in order to increase the average of the first issue. Thus, an important research question is how to find aggregation rules that are strategyproof - cannot be manipulated in this way.

When there are only two issues, the problem is essentially one-dimensional: it is sufficient to decide on the allocation to issue 1, as the allocation to issue 2 equals the total budget minus the allocation to issue 1. In this setting, the median voting rule is known to be strategyproof. When there are three or more issues, one could allocate, to each issue, the median of the votes on that issue. However, the sum of medians would not necessarily sum up to the total budget.

One way to solve this problem is to use a generalization of the median rule. In a (one-dimensional) generalized median rule, there is a set of fixed votes, and the median is computed based on the union of the fixed votes and the actual votes. Every generalized median rule is strategyproof, and Moulin^[4] proved that the opposite is also true: every strategyproof mechanism is a generalized median rule. By carefully selecting the fixed votes in each issue, one can ensure that the sum of medians in all issues equals the total budget.

A moving-phantoms mechanism is a sophisticated algorithm for selecting the fixed votes, such that the sum of generalized medians equals the total budget. It works for any number of issues. If the agents' preferences are based on L1-distance (that is, agents always prefer a budget-allocation with a smaller L1-distance to their ideal allocation), then any MPM is also strategyproof.

A total budget B>0 has to be divided among some m issues. There are n voters, each of whom votes by declaring his ideal budget-distribution (also called peak) - a vector of m non-negative numbers with sum exactly B.

A moving-phantoms mechanism is parameterized by a phantom system - a set of n+1 functions F := (f₀, f₁, ... f_n), such that for all k, f_k is a continuous and weakly-increasing function from [0,1] to [0,B], with f_k(0) = 0 and f_k(1) = B.

The original definition^{[1]: Def.4.6 [3]: Def.6} also requires that the phantom functions are *non-crossing*, that is, f₀(t) >= ... >= f_n(t) for all t in [0,1].

At each t in [0,1], the phantom system induces a set of phantom votes (f₀(t), f₁(t), ...). For each issue j in [m], one can compute the generalized median at t - the median of the multiset containing all real votes on issue j and all phantom votes. As the total number of votes is an odd integer (2n+1), the median in each issue is always the (n+1)-th smallest element in that multiset.

As all f_k are continuous and weakly increasing, the same holds for each of the m medians, and the same holds for the sum of all m medians. At t=0 all n+1 phantoms equal 0, so all m medians equal 0 and their sum is 0. At t=1 all n+1 phantoms equal B, so all m medians equal B and their sum is mB > B. Hence, by the intermediate value theorem, there exists some t* in [0,1] for which the sum of m medians exactly equals B; such a t* is called a normalization time. This normalization time need not be unique, but the vector of m medians is unique, because each median is weakly increasing and their sum is constant for all normalization times. This unique vector of medians is the budget-distribution returned by the mechanism. See ^[3]: 10 for an example with n=4 voters and m=3 issues.

To compute the outcome of an MPM, it is sufficient to compute a normalization time t*. Such a t* can be computed to any desired accuracy using the bisection method; the run-time is polynomial in the number of desired accuracy digits. If the phantom functions are piecewise-linear, then t* is always rational and can be computed exactly in polynomial time.

Different number of phantom functions. The number of phantom functions can be different than n+1. The proof of strategyproofness does not depend at all on the number of phantom functions. The number n+1 is only needed to ensure that a normalization time exists. In fact, normalization is guaranteed for any number larger than n+1 phantoms (with the same proof). Normalization is guaranteed even with only n-1 phantoms. In that case, the total number of votes in each issue is still an odd integer. At t=0 the median in each issue equals the minimum real vote on that issue, so the sum of all m medians is at most B; at t=1 the median in each issue equals the maximum real vote on that issue, so the sum of all m medians is at least B. Hence, a normalization time t* always exists by the intermediate value theorem. However, with fewer than n-1 phantoms, a normalization time might not exist.

Different end points. The proof of strategyproofness also does not depend on the requirement that f_k(0)=0 and f_k(1)=B. This requirement comes to guarantee normalization, but in fact, to guarantee normalization, it is sufficient that some n phantom functions satisfy this requirement. The proof is similar to the proof for n-1 phantoms: at t=0 the median is at most the minimum real vote on that issue, and at t=1 the median in each issue is at least the maximum real vote on that issue.

Different phantom functions for each issue. One can use a different phantom system for each issue. The resulting MPM is still strategyproof, as the proof of strategyproofness (below) remains valid as-is. However, it is not neutral.

Every MPM is continuous, that is, the outcome is a continuous function of the votes.

Every MPM is anonymous, as it depends only on the set of votes, and not on the identity of voters.

Every MPM is neutral, as the phantom functions are the same for each issue.

If all voters have L1 preferences, then every MPM rule is strategyproof. The proof^{[1]: Thm.4.8 [3]: Thm.2} proceeds in two steps:

• (1) If an agent changes his reported peak, but all the phantoms are fixed in place, then we have a median voting rule in each issue, so the outcome in each issue either stays the same or goes farther from the agent's real peak.
• (2) As the phantoms move, the outcome in some issues may move nearer to the agent's real peak, but the agent's gain from this is at most the agent's loss in step 1.

Formally, denote by t* the normalization time when agent i is truthful, and by t** the normalization time when agent i manipulates.

• (1) For each issue j, denote by y_j the difference between the median at time t* when i manipulates, and the median at time t* when i is truthful. Then, if i's manipulated vote for j remains at the same side of the median for j, then y_j=0; if i manipulates his vote for j from above to below the median, then y_j<0; and if i manipulates his vote for j from below to above the median, then y_j>0. Hence, the L1 distance between agent i's peak and the vector of medians at time t* increases by sum_j|y_j|.
• (2) If sum_j y_j = 0, then t* is still a normalization time after manipulation, so the outcome remains the same. Otherwise, assume wlog that sum_j y_j > 0. Then the sum of medians at time t* (after manipulation) is larger than B, which means that normalization must occur earlier: t** < t*. By monotonicity, the median in each issue j at time t** is weakly smaller than the median at time t*, and the sum of m medians at time t** is smaller than the sum at time t* (after manipulation) by sum_j y_j. Hence, the L1 distance between the vector of medians at time t** and the vector of medians at time t* is sum_j y_j. By the triangle inequality, the L1 distance between agent i's peak and the vector of medians at time t** increases by at least sum_j|y_j| - sum_jy_j, which is at least 0.

Reliance on L1 disutilities. The proof of step (2) crucially relies on the assumption of L1 disutilities, and does not work with other utility models. For example, suppose there are three issues and two agents with peaks at (20,60,20) and (0,50,50). One moving-phantoms rule (the "independent markets" rule below) returns (20,50,30), so agent 1's L1 disutility is 10+10+0=20 and L2 disutility is sqrt(100+100+0)=sqrt(200). If agent 1 changes his peak to (30,50,20), then the rule returns (25,50,25). Agent 1's L1 disutility is 5+10+5=20 and L2 disutility is sqrt(25+100+25)=sqrt(150). Agent 1 does not gain in L1 disutility, but does gain in L2 disutility.

A budget-aggregation rule satisfies vote monotonicity if whenever some voter i increases the vote on some issue j and weakly decreases the votes on every other issue, and the other votes remain unchanged, the final allocation to issue j weakly increases. Every MPM satisfies vote-monotonicity.^[3]: Thm.3

A budget distribution is called range-respecting^[3][5] if the allocation to each issue is between the minimum vote and the maximum vote for that issue. An MPM with n+1 phantoms might not always return a range-respecting outcome. However, with n-1 phantoms, there are always more real votes than phantom votes, so the median in each issue is always between the smallest and largest real votes; hence, the outcome is always range-respecting.

Below we describe several different MPM-s (with different phantom systems) that have been studied in the literature. See also Peters^[6] for an online demo, and Cembrano, Freeman, Kraepelin and Utke^[7]: App.A for visualizations and detailed welfare comparisons.

A simple, degenerate MPM is defined by using the following n+1 identical phantom functions:^[7]: App.A

f_k(t) := B*t, for all k in 0,...,n.

With this phantom system, the median at each time t is always B*t. Hence, normalization always occurs at t=1/m, when all medians are B/m. This MPM returns the uniform budget distribution (B/m,...,B/m) regardless of the votes.

The Independent Markets rule^[3]: Sec.5 is defined by the following phantom system:

f_k(t) := B*min(1,k*t), for all k in 0,...,n.

All phantoms start at 0, and move at different speeds towards B. Whenever a phantom reaches B, it stops and remains at B. Note that phantoms 1,...,n satisfy the endpoint requirements f_k(0)=0 and f_k(1)=B, so normalization is guaranteed.

In addition to strategyproofness, it satisfies a property called single-minded proportionality: if all agents are single-minded (each agent's ideal budget allocates 100% of the budget to a single issue), then the rule allocates the budget among the issues proportionally to the number of their supporters. However, this rule is not range-respecting, as it might make allocations that are outside the range for all agents. For example, with n=2 and C=100, if one agent votes (80,0,20) and the other one votes (80,20,0), then the IM rule returns (60,20,20).

If only the n-1 phantoms f₁,...,f_n-1 are used, then the resulting moving-phantoms mechanism is always range-respecting, but might still fail to be Pareto-efficient for m >= 3 issues.

The Utilitarian rule is defined by the following phantom system:

f_k(t) :=

• 0 for t in [0, k/(n+1)];
• B*(t*(n+1)-k) for t in [k/(n+1), (k+1)/(n+1)];
• B for t in [(k+1)/(n+1), 1];

Here, the phantoms move one by one from 0 towards B, such that there is always at most one "interior" phantom.

Whenever phantoms f₀,...,f_k are at 0 and phantoms f_k+1,...,f_n are at B, the rule selects, for each issue, the k-th highest vote. When phantom k moves from 0 to B, the allocation for each issue moves continuously from the k-th highest vote to the (k-1)-th highest vote. The process stops when, for some L, all issues are allocated an amount between the L-th highest vote to the (L-1)-th highest vote. It can be proved^[3]: Sec.6 that this property is necessary and sufficient for a distribution being utilitarian (= minimizes the sum of L1 distances).

This specific MPM chooses a distribution that, among all utilitarian allocations, minimizes the L2 distance to the uniform distribution. It is the only MPM that is Pareto-efficient. However, it is not single-minded proportional.

Caragiannis, Christodoulou and Protopapas^[8][9] define an MPM which they call Piecewise-Uniform, using the following phantom system.

• For t<1/2:
  • f_k(t) := 0 for all k < n/2;
  • f_k(t) := B*t*(4k/n - 2) for all k >= n/2.
• For t>=1/2:
  • f_k(t) := B*k*(2t-1)/n for all k < n/2;
  • f_k(t) := B*[k*(3-2t)/n-2+2t] for all k >= n/2.
• In particular, for t=1, f_k(1) := B*k/n for all k.

So in time [0,1/2], the first n/2 phantoms wait at 0 while the last n/2 phantoms spread uniformly across [0,B]; in time [1/2,1], the first n/2 phantoms spread uniformly across [0,B/2] whereas the last n/2 phantoms spread uniformly across [B/2,B].

The goal of this rule is to attain a distribution that is close to the average of peaks in the L1-distance. They prove that the Piecewise-Uniform rule is single-minded proportional, and has disproportionality ~2/3.

Freeman and Schmidt-Kraepelin^[10] define an MPM which they call Ladder, using the following phantom system:

f_k(t) := B*max(0, t - k/n), for all k in 0,...,n.

Figuratively, the phantoms move like rungs in a rope-ladder that is pulled by its top rung. Initially, the phantoms are spread uniformly in [-1, 0]; then they proceed upwards in a constant speed until finally they are spread uniformly in [0,1].

The goal of this rule is to attain a distribution that is close to the average of peaks in the L-infinity distance. They prove that the Ladder rule underfunds a project by at most 1/2-1/(2m), and overfunds a project by at most 1/4; both bounds are tight for MPM-s.

de-Berg, Freeman, Schmidt-Kraepelin and Utke^[11] define a theoretic MPM which they call GreedyMax, using the following phantom system:

• f₀(t) := 0;
• f_k(t) := B*t, for all k in 1,...,n.

Note that phantoms 1,...,n satisfy the endpoint requirements f_k(0)=0 and f_k(1)=B, so normalization is guaranteed.

Note that f₀ does not satisfy the requirement that f₀(1)=B. However, this requirement is required only to prove the existence of a normalization time (all other properties of MPM do not depend on it). In GreedyMax, even though f₀ violates the requirement, normalization is still guaranteed. This is because, at each time t, the median in each issue j is the minimum between B*t and the largest real vote on j. At t=0, all m medians are 0, so the sum of medians is 0; at t=1, the median in each issue j is the largest real vote on j, so the sum of all medians is at least B. Hence, normalization exists by the intermediate value theorem.

An alternative description of GreedyMax is: iterate over the issues in ascending order of their largest votes. For the current issue j, If the largest vote on j is at most B/(n-j-1), then assign the largest vote to issue j and remove this amount from B. Otherwise, assign B/(n-j-1) to the current and all remaining issues.

GreedyMax does not satisfy single-minded proportionality.

Cembrano, Freeman, Kraepelin and Utke^[7]: App.A define a theoretic MPM which they call Fan, defined by the following phantom system:

f_k(t) := B*min(k/n ,t), for all k in 0,...,n.

All phantoms start at 0 and move simultaneously at the same speed; each phantom k stops when it reaches k/n. The Fan rule is single-minded proportional; its utilitarian social welfare is smallest among all single-minded proportional MPM-s.^[7]

Cembrano, Freeman, Kraepelin and Utke^[7]: App.A define an MPM they call UtilProp, defined by the following phantom system:

f_k(t) :=

• 0 for t in [0, k/(n+1)];
• B*(t*(n+1)-k) for t in [k/(n+1), (k+1)/(n+1)];
• B for t in [(k+1)/(n+1), 1];

Here, the phantoms move one by one starting at 0, where each phantom k stops at B*(n-k)/n, such that there is always at most one "interior" phantom. UtilProp is single-minded proportional; among all single-minded proportional rules, it attains the highest utilitarian social welfare.^[7]

There are non-MPM rules that are anonymous, neutral, continuous and strategyproof, even for n=1 voter.^[12]

One class of such rules, defined for any number of voters, is the class of cutoff-phantom mechanisms.^[11]

• Moving-knife procedure