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) in collaboration with Rupert Freeman, David Pennock and Jennifer Wortman Vaughan.
Motivation 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 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.
Description
Input 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.
Phantom system A moving-phantoms mechanism is parameterized by a phantom system - a set of n+1 functions F := (f0, f1, ... fn), such that for all k, fk is a continuous and weakly-increasing function from [0,1] to [0,B], with fk(0) = 0 and fk(1) = B.
The original definition also requires that the phantom functions are *non-crossing*, that is, f0(t) >= ... >= fn(t) for all t in [0,1].
Execution At each t in [0,1], the phantom system induces a set of phantom votes (f0(t), f1(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 fk 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 for an example with n=4 voters and m=3 issues.
Computation 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.
Variants 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 fk(0)=0 and fk(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.
Properties
Basic properties 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.
Strategyproofness If all voters have L1 preferences, then every MPM rule is strategyproof. The proof 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 yj 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 yj=0; if i manipulates his vote for j from above to below the median, then yj<0; and if i manipulates his vote for j from below to above the median, then yj>0. Hence, the L1 distance between agent i's peak and the vector of medians at time t* increases by sumj|yj|. (2) If sumj yj = 0, then t* is still a normalization time after manipulation, so the outcome remains the same. Otherwise, assume wlog that sumj yj > 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 sumj yj. Hence, the L1 distance between the vector of medians at time t** and the vector of medians at time t* is sumj yj. By the triangle inequality, the L1 distance between agent i's peak and the vector of medians at time t** increases by at least sumj|yj| - sumjyj, 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.
Vote monotonicity 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.
Range-respect A budget distribution is called range-respecting 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.
Specific phantom systems Below we describe several different MPM-s (with different phantom systems) that have been studied in the literature. See also Peters for an online demo, and Cembrano, Freeman, Kraepelin and Utke for visualizations and detailed welfare comparisons.
Constant
A simple, degenerate MPM is defined by using the following n+1 identical phantom functions:fk(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.
Independent markets rule
The Independent Markets rule is defined by the following phantom system:fk(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 fk(0)=0 and fk(1)=B, so normalization is guaranteed.