86:: ask each member what is his peak, and take the average of all peaks. But this rule easily manipulable. For example, suppose Alice's peak is 30, George's peak is 40, and Chana's peak is 50. If all voters report their true peaks, the actual amount will be 40. But Alice may manipulate and say that her peak is actually 0; then the average will be 30, which is Alice's actual peak. Thus, Alice has gained from the manipulation. Similarly, any agent whose peak is different than the outcome has an incentive to manipulate and report a false peak.
968:. The median rule apparently contradicts this theorem, because it is strategyproof and it is not a dictatorship. In fact there is no contradiction: the Gibbard-Satterthwaite theorem applies only to rules that operate on the entire preference domain (that is, only to voting rules that can handle any set of preference rankings). In contrast, the median rule applies only to a restricted preference domain—the domain of single-peaked preferences.
103:: no voter can gain by reporting a false peak. In the above example, the median is 40, and it remains 40 even if Alice reports 0. In fact, as Alice's true peak is below the median, no false report by Alice can potentially decrease the median; Alice can only increase the median, but this will make her worse-off.
426:
single-peaked preferences (symmetry means that an outcome farther away from the peak should be less preferred than an outcome nearer to the peak, even if the outcomes are on different sides of the peak). The class of strategyproof mechanisms in this smaller domain is strictly larger than the class of
911:
In 1954, the
Iranian Oil Consortium has adopted a median-like rule to determine Iran's total annual oil output. Annually, each member company's role was weighted by its fixed share of the total output. The chosen output, x, was the highest level such that the sum of the shares of members voting for
530:
Berga and
Serizawa seek rules that are both strategyproof and satisfy a condition they call "no vetoer": no individual should be able to avoid any alternative to be the outcome by declaring some preference. They characterize generalized median rules as the only strategyproof rules on "minimally-rich
944:
are an attempt at applying the same voting rule to elections by asking voters to submit judgments (scores) for each candidate. However, the strategyproof nature of the median voting rule does not extend to choosing candidates unless the voters have single-peaked preferences over each candidate's
286:
The median rule is not the only strategyproof rule. One can construct alternative rules by adding fixed votes, that do not depend on the citizen votes. These fixed votes are called "phantoms". For every set of phantoms, the rule that chooses the median of the set of real votes + phantoms is
510:, that is: if the agent's peak is to the right of the outcome, and he moves his peak further to the right, then the outcome does not change; and similarly to the left. Conversely, every uncompromising rule is strategyproof. They prove that a rule is uncompromising if it has at most 2
290:
For example, suppose the votes are 30, 40, and 50. Without phantoms, the median rule selects 40. If we add two phantoms at 0, then the median rule selects 30; if we add two phantoms at 100, the median rule selects 50; if we add medians at 20 and 35, the median rule selects 35.
902:
In quadratic non-separable domains, the only strategyproof mecanisms are dictatorial. But in separable domains, there are multidimensional strategyproof mechanisms that are composed of one-dimensional strategyproof mechanisms, one for each coordinate.
264:
Similarly, consider a voter whose peak is above the median. Reporting a higher peak will not change the median; reporting a lower peak will either keep the median unchanged or decrease the median. In all cases, the voter does not
260:
Consider first a voter whose peak is below the median. Reporting a lower peak will not change the median; reporting a higher peak will either keep the median unchanged or increase the median. In all cases, the voter does not
889:
162:
Note that single-peakedness does not imply any particular distance-measure between the alternatives, and does not imply anything on alternatives at different sides of the peak. In particular, if a >
531:
domains". They proved that the unique maximal domain that includes a minimally-rich domain, which allows for the existence of strategyproof rules satisfying the "no vetoer" condition, is the domain of
665:
760:
500:
427:
generalized median rules. In particular, rules can be disturbed by discontinuity points. Their result allows to design rules that deal with feasibility constraints.
42:
along a one-dimensional domain. Each person votes by writing down his/her ideal value, and the rule selects a single value which is (in the basic mechanism) the
324:-1 phantoms at 50, then the median rule returns 50 if some ideal points are above and some are below 50; otherwise, it returns the vote closest to 50.
404:, even if they are not "peak only", are augmented median rules, that is, can be described by a variant of the median rule with some 2 parameters.
1282:
776:
77:
Each member has in mind an ideal decision, called his "peak". Each agent prefers the actual amount to be as close as possible to his peak.
538:
Barbera, Gul and
Stacchetti also generalize the notions of single-peaked preferences and median voting rules to multidimensional settings.
938:
always selects the candidate preferred by the median voter (the candidate closest to the voter whose peak is the median of all peaks).
928:
mechanisms, in which each agent reports his/her full ranking over alternatives. The theorem says that, if the agents' preferences are
961:
1344:
564:
Border and Jordan generalize the notions of single-peaked preferences and median voting rules to multidimensional settings (see
159:
Once such a linear order exists, the median of any set of peaks can be computed by ordering the peaks along this linear order.
578:
419:
preferences. They prove that, even in this smaller domain, the strategyproof rules are exactly the generalized median rules.
273:, that is: no coalition has a coordinated manipulation that improves the utility of one of them without harming the others.
1349:
339:, strategyproof and Pareto-efficient for all single-peaked preferences if it is equivalent to a median rule with at most
941:
24:
1177:
BarberĂ , Salvador; Gul, Faruk; Stacchetti, Ennio (December 1993). "Generalized Median Voter
Schemes and Committees".
1339:
1071:
Berga, Dolors; Serizawa, Shigehiro (January 2000). "Maximal Domain for
Strategy-Proof Rules with One Public Good".
411:
single-peaked preferences. Several other works allow rules that handle only a subset of single-peaked preferences:
929:
347:
336:
112:
70:
763:
683:
556:- a generalization of single-peaked in which each agent is allowed to have an entire interval of ideal points.
1238:
Moulin, H. (August 1984). "Generalized condorcet-winners for single peaked and single-plateau preferences".
1098:
MassĂł, Jordi; Moreno de
Barreda, Inés (June 2011). "On strategy-proofness and symmetric single-peakedness".
953:, but the rule will not be strategyproof in situations where voters have single-peaked preferences over the
565:
523:
396:
Moulin's characterizations consider only rules that are "peak only", that is, the rule depends only on the
965:
437:
522:. As a corollary, every uncompromising rule is continuous. However, an uncompromising rule that is also
519:
39:
115:. This means that there exists some linear ordering > of the alternatives, such that for each agent
350:
and strategyproof for all single-peaked preferences if it is equivalent to a median rule with at most
921:
20:
514:(that is, at most 2 points that may be elected even if they are not the peak of any voter), and its
1206:"A characterization of strategy-proof social choice functions for economies with pure public goods"
1205:
503:
294:
Here are some special cases of phantom-median rules, assuming all the votes are between 0 and 100:
270:
82:
1315:
1159:
1139:
1050:
1005:
532:
434:
preferences. In the one-dimensional setting, this is equivalent to utility functions of the form
518:(mapping each profile to the set of indices of real+phantom voters whose peak is elected) has a
1278:
950:
100:
56:
Many scenarions of group decision making involve a one-dimensional domain. Some examples are:
63:
Several people working in the same office have to decide on the air-conditioning temperature.
1307:
1270:
1247:
1220:
1186:
1151:
1115:
1107:
1080:
1040:
1032:
997:
935:
328:
66:
Parents of schoolchildren should decide how long the annual school vacation should be.
1333:
1009:
971:
Dummet and
Farquharson present a sufficient condition for stability in voting games.
925:
1054:
357:
A rule is strategyproof for all single-peaked preferences iff it is equivalent to a
60:
Members of a city-council have to decide on the total amount of annual city budget.
1274:
1111:
1190:
1084:
964:
says that every strategyproof rule on three or more alternatives must be a
502:. In this domain, they prove that any strategyproof rule that respects the
1023:
Ching, Stephen (December 1997). "Strategy-proofness and 'median voters'".
1045:
1319:
1251:
1224:
1163:
1036:
1001:
884:{\displaystyle u_{i}(x)=-\sum _{j=1}^{m}a_{i,j}\cdot (x_{j}-p_{j})^{2}}
551:
1120:
111:
The median voting rule holds in any setting in which the agents have
95:
44:
1311:
1298:
Dummett, Michael; Farquharson, Robin (1961). "Stability in Voting".
1155:
545:
preferences, in which the maximal set may contain two alternatives.
269:
Using similar reasoning, one can prove that the median rule is also
988:
Moulin, H. (1980). "On strategy-proofness and single peakedness".
170:> b, then the agent may prefer either a to b or b to a.
541:
Barbera and
Jackson characterized strategyproof rules for
400:
peaks. Ching proved that all rules that are strategyproof
1140:"Straightforward Elections, Unanimity and Phantom Voters"
372:
of voters. The rule returns the minimum over all subsets
256:
Here is a proof that the median rule is strategyproof:
407:
Moulin's characterizations require the rules to handle
660:{\displaystyle u_{i}(x)=\sum _{j=1}^{m}u_{i,j}(x_{j})}
779:
686:
581:
440:
313:-1 phantoms at 100, then the median rule returns the
302:-1 phantoms at 0, then the median rule returns the
883:
754:
659:
494:
1204:BarberĂ , Salvador; Jackson, Matthew (July 1994).
207:. In the basic mechanism, the chosen value when
99:of all votes. This simple change makes the rule
568:). They consider three classes of preferences:
430:Border and Jordan allow rules that handle only
361:of the following form. There are 2 parameters,
1138:Border, Kim C.; Jordan, J. S. (January 1983).
422:Masso and Moreno allow rules that handle only
415:Berga and Serizawa allow rules to handle only
8:
548:Moulin characterized strategyproof rules on
376:, of the maximum of (all peaks of voters in
193:. The values are sorted in ascending order
218:, which equals the median of values (when
1119:
1044:
875:
865:
852:
830:
820:
809:
784:
778:
755:{\displaystyle u_{i}(x)=-(x-p)^{T}A(x-p)}
728:
691:
685:
648:
629:
619:
608:
586:
580:
487:
481:
466:
445:
439:
331:proved the following characterizations:
980:
912:levels as high as x was at least 70%.
674:is a single-peaked utility function);
7:
1133:
1131:
1066:
1064:
1025:International Journal of Game Theory
93:determines the actual budget at the
495:{\displaystyle u_{i}(x)=-|x-p_{i}|}
949:This may be a reasonable model of
69:The public has to decide where to
14:
186:is asked to report the value of
16:Method for group decision-making
907:Application in the oil industry
73:along a one-dimensional street.
1144:The Review of Economic Studies
872:
845:
796:
790:
749:
737:
725:
712:
703:
697:
654:
641:
598:
592:
488:
467:
457:
451:
155:, then agent i prefers a to b.
145:, then agent i prefers a to b;
80:A simple way to decide is the
1:
962:Gibbard–Satterthwaite theorem
222:is even, the chosen value is
392:Additional characterizations
19:Not to be confused with the
1100:Games and Economic Behavior
942:Highest median voting rules
560:Multidimensional extensions
25:highest median voting rules
1366:
1179:Journal of Economic Theory
1073:Journal of Economic Theory
957:(winner) of the election.
252:Proof of strategyproofness
18:
1275:10.1007/978-1-349-81487-9
1240:Social Choice and Welfare
1213:Social Choice and Welfare
1112:10.1016/j.geb.2010.12.001
113:single peaked preferences
898:are positive constants).
764:positive definite matrix
277:Generalized median rules
1345:Participatory budgeting
1265:Blair, John M. (1976).
762:where A is a symmetric
566:star-shaped preferences
1191:10.1006/jeth.1993.1069
1085:10.1006/jeth.1999.2579
885:
825:
756:
661:
624:
496:
249:
886:
805:
757:
662:
604:
497:
287:group-strategyproof.
231:
40:group decision-making
1350:Social choice theory
922:median voter theorem
777:
684:
579:
543:weakly-single-peaked
526:must be dictatorial.
516:elect correspondence
438:
282:Median with phantoms
21:median voter theorem
771:separable quadratic
769:Their intersection
504:unanimity criterion
271:group-strategyproof
83:average voting rule
1267:The Control of Oil
1252:10.1007/BF00452885
1225:10.1007/BF00193809
1037:10.1007/BF01813886
1002:10.1007/BF00128122
881:
752:
657:
533:convex preferences
492:
317:of all real votes.
306:of all real votes.
32:median voting rule
1340:Electoral systems
1284:978-1-349-81489-3
951:expressive voting
148:If b > a >
89:In contrast, the
71:locate a facility
1357:
1324:
1323:
1295:
1289:
1288:
1262:
1256:
1255:
1235:
1229:
1228:
1210:
1201:
1195:
1194:
1174:
1168:
1167:
1135:
1126:
1125:
1123:
1095:
1089:
1088:
1068:
1059:
1058:
1048:
1020:
1014:
1013:
985:
936:Condorcet method
916:Related concepts
890:
888:
887:
882:
880:
879:
870:
869:
857:
856:
841:
840:
824:
819:
789:
788:
761:
759:
758:
753:
733:
732:
696:
695:
666:
664:
663:
658:
653:
652:
640:
639:
623:
618:
591:
590:
501:
499:
498:
493:
491:
486:
485:
470:
450:
449:
233:choice = median(
36:median mechanism
1365:
1364:
1360:
1359:
1358:
1356:
1355:
1354:
1330:
1329:
1328:
1327:
1312:10.2307/1907685
1297:
1296:
1292:
1285:
1264:
1263:
1259:
1237:
1236:
1232:
1208:
1203:
1202:
1198:
1176:
1175:
1171:
1156:10.2307/2296962
1137:
1136:
1129:
1097:
1096:
1092:
1070:
1069:
1062:
1022:
1021:
1017:
987:
986:
982:
977:
918:
909:
896:
871:
861:
848:
826:
780:
775:
774:
724:
687:
682:
681:
672:
644:
625:
582:
577:
576:
562:
477:
441:
436:
435:
394:
385:
368:for any subset
366:
284:
279:
254:
245:
239:
228:
217:
205:
199:
191:
176:
168:
153:
135:
124:
109:
54:
48:of all votes.
28:
17:
12:
11:
5:
1363:
1361:
1353:
1352:
1347:
1342:
1332:
1331:
1326:
1325:
1290:
1283:
1257:
1246:(2): 127–147.
1230:
1196:
1185:(2): 262–289.
1169:
1127:
1106:(2): 467–484.
1090:
1060:
1031:(4): 473–490.
1015:
996:(4): 437–455.
979:
978:
976:
973:
917:
914:
908:
905:
900:
899:
894:
878:
874:
868:
864:
860:
855:
851:
847:
844:
839:
836:
833:
829:
823:
818:
815:
812:
808:
804:
801:
798:
795:
792:
787:
783:
767:
751:
748:
745:
742:
739:
736:
731:
727:
723:
720:
717:
714:
711:
708:
705:
702:
699:
694:
690:
675:
670:
656:
651:
647:
643:
638:
635:
632:
628:
622:
617:
614:
611:
607:
603:
600:
597:
594:
589:
585:
561:
558:
528:
527:
524:differentiable
512:phantom voters
508:uncompromising
490:
484:
480:
476:
473:
469:
465:
462:
459:
456:
453:
448:
444:
428:
420:
417:minimally-rich
402:and continuous
393:
390:
389:
388:
383:
364:
355:
344:
326:
325:
318:
307:
283:
280:
278:
275:
267:
266:
262:
253:
250:
243:
237:
226:
215:
203:
197:
189:
175:
172:
166:
157:
156:
151:
146:
133:
122:
108:
105:
75:
74:
67:
64:
61:
53:
50:
38:is a rule for
15:
13:
10:
9:
6:
4:
3:
2:
1362:
1351:
1348:
1346:
1343:
1341:
1338:
1337:
1335:
1321:
1317:
1313:
1309:
1305:
1301:
1294:
1291:
1286:
1280:
1276:
1272:
1268:
1261:
1258:
1253:
1249:
1245:
1241:
1234:
1231:
1226:
1222:
1218:
1214:
1207:
1200:
1197:
1192:
1188:
1184:
1180:
1173:
1170:
1165:
1161:
1157:
1153:
1149:
1145:
1141:
1134:
1132:
1128:
1122:
1117:
1113:
1109:
1105:
1101:
1094:
1091:
1086:
1082:
1078:
1074:
1067:
1065:
1061:
1056:
1052:
1047:
1042:
1038:
1034:
1030:
1026:
1019:
1016:
1011:
1007:
1003:
999:
995:
991:
990:Public Choice
984:
981:
974:
972:
969:
967:
963:
958:
956:
952:
948:
943:
939:
937:
934:, then every
933:
932:
931:single-peaked
927:
926:ranked voting
923:
915:
913:
906:
904:
897:
876:
866:
862:
858:
853:
849:
842:
837:
834:
831:
827:
821:
816:
813:
810:
806:
802:
799:
793:
785:
781:
772:
768:
765:
746:
743:
740:
734:
729:
721:
718:
715:
709:
706:
700:
692:
688:
679:
676:
673:
667:, where each
649:
645:
636:
633:
630:
626:
620:
615:
612:
609:
605:
601:
595:
587:
583:
574:
571:
570:
569:
567:
559:
557:
555:
553:
546:
544:
539:
536:
534:
525:
521:
517:
513:
509:
505:
482:
478:
474:
471:
463:
460:
454:
446:
442:
433:
429:
425:
421:
418:
414:
413:
412:
410:
405:
403:
399:
391:
386:
379:
375:
371:
367:
360:
356:
353:
349:
345:
342:
338:
334:
333:
332:
330:
323:
320:If there are
319:
316:
312:
309:If there are
308:
305:
301:
298:If there are
297:
296:
295:
292:
288:
281:
276:
274:
272:
263:
259:
258:
257:
251:
248:
246:
236:
230:
225:
221:
214:
210:
206:
196:
192:
185:
181:
173:
171:
169:
160:
154:
147:
144:
140:
136:
129:
128:
127:
125:
118:
114:
107:Preconditions
106:
104:
102:
101:strategyproof
98:
97:
92:
87:
85:
84:
78:
72:
68:
65:
62:
59:
58:
57:
51:
49:
47:
46:
41:
37:
33:
26:
22:
1306:(1): 33–43.
1303:
1300:Econometrica
1299:
1293:
1266:
1260:
1243:
1239:
1233:
1216:
1212:
1199:
1182:
1178:
1172:
1147:
1143:
1103:
1099:
1093:
1079:(1): 39–61.
1076:
1072:
1046:10722/177668
1028:
1024:
1018:
993:
989:
983:
970:
966:dictatorship
959:
954:
946:
940:
930:
919:
910:
901:
892:
770:
677:
668:
572:
563:
549:
547:
542:
540:
537:
529:
520:closed graph
515:
511:
507:
431:
423:
416:
408:
406:
401:
397:
395:
381:
377:
373:
369:
362:
358:
354:+1 phantoms.
351:
343:-1 phantoms.
340:
327:
321:
314:
310:
303:
299:
293:
289:
285:
268:
255:
241:
234:
232:
223:
219:
212:
208:
201:
194:
187:
183:
179:
177:
164:
161:
158:
149:
142:
138:
131:
120:
116:
110:
94:
90:
88:
81:
79:
76:
55:
43:
35:
31:
29:
924:relates to
554:preferences
359:minmax rule
178:Each agent
91:median rule
1334:Categories
1150:(1): 153.
1121:2072/53376
975:References
346:A rule is
335:A rule is
211:is odd is
119:with peak
52:Motivation
1010:154508892
859:−
843:⋅
807:∑
803:−
744:−
719:−
710:−
678:Quadratic
606:∑
573:Separable
475:−
464:−
432:quadratic
424:symmetric
348:anonymous
337:anonymous
182:in 1,...,
174:Procedure
1055:42830689
891:, where
200:≤ ... ≤
1320:1907685
1164:2296962
955:outcome
552:plateau
550:single-
315:maximum
304:minimum
240:, ...,
216:(n+1)/2
1318:
1281:
1162:
1053:
1008:
947:score.
945:final
380:, and
329:Moulin
96:median
45:median
1316:JSTOR
1219:(3).
1209:(PDF)
1160:JSTOR
1051:S2CID
1006:S2CID
265:gain.
261:gain.
141:>
137:>
1279:ISBN
960:The
920:The
30:The
1308:doi
1271:doi
1248:doi
1221:doi
1187:doi
1152:doi
1116:hdl
1108:doi
1081:doi
1041:hdl
1033:doi
998:doi
895:i,j
671:i,j
506:is
409:all
227:n/2
130:If
34:or
23:or
1336::
1314:.
1304:29
1302:.
1277:.
1269:.
1242:.
1217:11
1215:.
1211:.
1183:61
1181:.
1158:.
1148:50
1146:.
1142:.
1130:^
1114:.
1104:72
1102:.
1077:90
1075:.
1063:^
1049:.
1039:.
1029:26
1027:.
1004:.
994:35
992:.
766:);
535:.
387:).
247:).
229:):
126::
1322:.
1310::
1287:.
1273::
1254:.
1250::
1244:1
1227:.
1223::
1193:.
1189::
1166:.
1154::
1124:.
1118::
1110::
1087:.
1083::
1057:.
1043::
1035::
1012:.
1000::
893:a
877:2
873:)
867:j
863:p
854:j
850:x
846:(
838:j
835:,
832:i
828:a
822:m
817:1
814:=
811:j
800:=
797:)
794:x
791:(
786:i
782:u
773:(
750:)
747:p
741:x
738:(
735:A
730:T
726:)
722:p
716:x
713:(
707:=
704:)
701:x
698:(
693:i
689:u
680:(
669:v
655:)
650:j
646:x
642:(
637:j
634:,
631:i
627:u
621:m
616:1
613:=
610:j
602:=
599:)
596:x
593:(
588:i
584:u
575:(
489:|
483:i
479:p
472:x
468:|
461:=
458:)
455:x
452:(
447:i
443:u
398:n
384:S
382:b
378:S
374:S
370:S
365:S
363:b
352:n
341:n
322:n
311:n
300:n
244:n
242:p
238:1
235:p
224:p
220:n
213:p
209:n
204:n
202:p
198:1
195:p
190:i
188:p
184:n
180:i
167:i
165:p
152:i
150:p
143:b
139:a
134:i
132:p
123:i
121:p
117:i
27:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.