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.
Description
Input
A total budget B>0 has be divided among some m issues. There are n voters, each of whom votes by declaring his ideal budget-distribution - 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[1]:Def.4.6[3]:Def.6 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 [3]:10 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. One can use phantom systems with n-1 functions, instead of n+1. The total number of votes in each issue is still an odd integer. Here, at t=0 the median in each issue is the minimum vote on that issue, so the sum of all m medians is at most B; at t=1 the median in each issue is the maximum vote on that issue, so the sum of all m medians is at least B. Hence, a normalization time t* always exists. However, with fewer than n-1 phantoms, a normalization time might not exist.
Different phantom functionsfor each issue. One can use a different phantom system for each issue. The resulting MPM will not be neutral.
Properties
All MPM-s are anonymous, neutral and continuous. In addition, they satisfy the following properties.
Truthfulness
If all voters have L1 preferences, then every MPM rule is strategyproof. The proof[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.
The proof of step (2) crucially relies on the assumption of L1 utilities, and does not work with other distance metrics. For example, suppose there are 3 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.[3]:Thm.3
Range-respect
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.
Specific phantom systems
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.
Independent markets rule
A particular moving-phantoms rule is the Independent Markets rule,[3]:Sec.5 where the n+1 phantoms are:
fi(t):= C*min(1,i*t), for all i in 0,...,n.
where C is the total budget. 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 we change f0 to always equal 0 and fn to always equal C, then these two extreme phantoms cancel out, and the situation is identical to having only n-1 phantoms. The resulting moving-phantoms mechanism is always range-respecting, but might still fail to be Pareto-efficient for m >= 3 issues.
Utililtarian moving-phantoms rule
Suppose the n+1 phantom functions all start at 0, and move one by one towards C, such that there is always at most one "interior" phantom.
Whenever phantoms f0,...,fk are at 0 and phantoms fk+1,...,fn are at C, the rule selects, for each issue, the k-th highest vote. When phantom k moves from 0 to C, 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[8]:Sec.6 that this property is necessary and sufficient for a distribution being utilitarian (= minimizes the sum of L1 distances).
This specific moving-phantoms mechanism chooses a distribution that, among all utilitarian allocations, minimizes the L2 distance to the uniform distribution. It is the only moving-phantoms mechanism that is Pareto-efficient.
Piecewise-uniform rule
Caragiannis, Christodoulou and Protopapas[9] extended the definition of proportionality from single-minded preference profiles to any preference profile. They define the proportional outcome as the arithmetic mean of peaks. The only mechanism which is always proportional is the average rule, which is not strategyproof. Hence, they define the L1 distance between the outcome of a rule and the average as the degree of dis-proportionality. The disproportionality of any budget-allocation is between 0 and 2. They evaluate BPA mechanisms by their worst-case disproportionality. In BPA with two issues, they show that UPM has worst-case disproportionality 1/2. With 3 issues, the independent-markets mechanism may have disproportionality 0.6862; they propose another moving-phantoms rule, called Piecewise-Uniform rule, which is still proportional, and has disproportionality ~2/3. They prove that the worst-case disproportionality of a moving-phantoms mechanism on m issues is at least 1-1/m, and the worst-case disproportionality of any truthful mechanism is at least 1/2; this implies that their mechanisms attain the optimal disproportionality.
Ladder rule
Freeman and Schmidt-Kraepelin[10] study a different measure of dis-proportionality: the L-infinity distance between the outcome and the average (i.e., the maximum difference per project, rather than the sum of differences). They define a new moving-phantoms rule called the Ladder rule, which underfunds a project by at most 1/2-1/(2m), and overfunds a project by at most 1/4; both bounds are tight for moving-phantoms rules.
Other rules
It is an open question whether every anonymous, neutral, continuous and strategyproof rule is an MPM.[11][9]
Elkind, Suksompong and Teh[12] define various axioms for BPA with L1-disutilities, analyze the implications between axioms, and determine which axioms are satisfied by common aggregation rules. They study two classes of rules: those based on coordinate-wise aggregation (average, maximum, minimum, median, product), and those based on global optimization (utilitarian, egalitarian).
This article or section is undergoing significant expansion or restructuring. You are welcome to assist in its construction by editing it as well. If this article or section has not been edited in several days, please remove this template. If you are actively editing this article or section, you can replace this template with {{in use|5 minutes}}.This article was last edited by Erel Segal(talk | contribs) 2 seconds ago. (Updatetimer)
This page is based on this Wikipedia article Text is available under the CC BY-SA 4.0 license; additional terms may apply. Images, videos and audio are available under their respective licenses.
