660:
638:
666:
all four preferences are single-peaked. To formally prove this, consider the set of three outcomes {A, D, E}. Each of these outcomes is a worst outcome of some agent: A is worst for the red agent, D is worst for the blue agent, and E is worst for the green agent above. Therefore, no ordering on X can make the set of preferences single-peaked.
827:
The outcome space can also be thought as different policies in an ideological spectrum: policies from the Left vs policies from the Right; policies that are more liberal vs policies that are more conservative; policies that are pro free markets vs policies that are pro state intervention. Voters have
665:
For the blue preferences, it can be seen that the preference ranking spikes down for "D" and then spikes up for "E". This proves that the blue preferences are not single-peaked with respect to the ordering A<B<C<D<E, but it still does not prove that there is no other ordering with which
632:
The following graph shows a set of three preferences that are single-peaked over outcomes {A,B,C,D,E}. On the vertical axis, the number represents the preference ranking of the outcome, with 1 being most preferred. Two outcomes that are equally preferred have the same ranking.
41:
to purchase. The amount is a one-dimensional variable. Usually, each consumer decides on a certain quantity which is best for him or her, and if the actual quantity is more/less than that ideal quantity, the agent is then less satisfied.
643:
The ordering over the outcomes is A < B < C < D < E. The ideal outcome for the green agent is A, for the red it is B, for the blue it is C. For each agent, when we move away from his ideal outcome, the ranking decreases.
776:
as the address of an individual. Suppose a single bus stop has to be located on the street and every individual wishes to walk as little as possible to the stop. Individuals then have single-peaked preferences: individual
485:
394:
879:: given a set of preferences on a set of outcomes, decide if there is a common order of the outcomes for which the preferences are single-peaked. Usually, it is required to also find this common order, if it exists.
647:
It can also be verified that, for each triplet of outcomes, one of them is never ranked last - the one in the middle. E.g., in {A,B,C}, B is never ranked last; in {C,D,E}, D is never ranked last; etc.
828:
single-peaked preferences if they have an ideal balance between the two directions of the ideological spectrum and if they dislike policies the farther away they are from their ideal point.
747:
132:
655:
If each of the two preferences represented by the following two graphs is added to the three preferences above, then the resulting group of four preferences is not single-peaked:
176:
586:
234:
207:
556:
520:
270:
822:
774:
669:
The green preferences are not formally single-peaked because they have two outcomes that are the most preferred: "B" and "C". Such preferences are sometimes called
526:. When the agent compares between two outcomes that are both to the right or to the left of his ideal point, he strictly prefers whichever option is closest to
795:
1250:
399:
308:
37:
Single-peaked preferences are typical of one-dimensional domains. A typical example is when several consumers have to decide on the amount of
1267:
1234:
1215:
1182:
885:
Escoffier, Spanjaard and
Tydrichova study the problem of recognizing preferences that are single-peaked on a general graph.
26:. A group has single-peaked preferences over a set of outcomes if the outcomes can be ordered along a line such that:
687:
1292:
1159:. Lecture Notes in Computer Science. Vol. 12283. Cham: Springer International Publishing. pp. 291–306.
54:
79:
882:
Trick presents a polynomial-time algorithm for recognizing preferences that are single-peaked on a tree.
894:
824:
and she dislikes other locations the farther they are to the west or the farther they are to the east.
137:
1152:
899:
38:
596:
Ballester and
Haeringer proved the following necessary condition for single-peaked preferences.
564:
212:
185:
529:
493:
243:
1224:
921:
800:
752:
50:
33:
For each agent, outcomes that are further from his or her best outcome are preferred less.
8:
1072:
23:
1153:"Recognizing Single-Peaked Preferences on an Arbitrary Graph: Complexity and Algorithms"
1287:
1244:
1188:
1160:
1053:
1006:
949:
840:
over a set of possible outcomes if the outcomes can be ordered along a line such that:
780:
681:
Single-peaked preferences have a number of interpretations for different applications.
46:
1113:
588:
are different, but the ordering > of the outcomes must be the same for all agents.
49:
for selecting an outcome, which is to select the median quantity; this results in the
1263:
1230:
1211:
1192:
1178:
1133:
1129:
1094:
1045:
998:
953:
941:
1057:
863:
Lackner and Peters study a class of preferences that are single-peaked on a circle.
1170:
1125:
1084:
1037:
993:
988:
980:
933:
876:
1174:
684:
A simple application of ideological preferences is to think of the outcome space
1025:
1041:
294:, if there exists an ordering > of the outcomes such that, for every agent
1281:
1137:
1098:
1049:
1002:
945:
65:
480:{\displaystyle x_{k}>x_{j}\geq x_{i}^{*}\Rightarrow x_{j}\succ _{i}x_{k}}
389:{\displaystyle x_{k}<x_{j}\leq x_{i}^{*}\Rightarrow x_{j}\succ _{i}x_{k}}
61:
1089:
902:- an extension of single-peaked preferences to multi-dimensional domains.
1010:
968:
1225:
Mas-Colell, Andreu, Michael D. Whinston, and Jerry R. Green (1995).
1151:
Escoffier, Bruno; Spanjaard, Olivier; Tydrichová, Magdaléna (2020).
984:
1165:
937:
615:, there exists an outcome that is not ranked last by any agent in
1205:
659:
637:
1150:
53:. It is truthful because the median function satisfies the
1024:
Ballester, Miguel A.; Haeringer, Guillaume (2010-07-15).
178:
be the set of agents. The preference-relation of agent
803:
783:
755:
690:
567:
532:
496:
402:
311:
246:
215:
188:
140:
82:
967:
Baumol, William J.; Arrow, Kenneth J. (1952-01-01).
1208:
Positive
Political Theory I: Collective Preferences
851:For each agent, outcomes that are further from his
1023:
816:
789:
768:
741:
580:
550:
514:
479:
388:
277:
264:
228:
201:
170:
126:
45:With single-peaked preferences, there is a simple
1114:"Recognizing single-peaked preferences on a tree"
1279:
1206:Austen-Smith, David & Jeffrey Banks (2000).
1026:"A characterization of the single-peaked domain"
650:
1071:Peters, Dominik; Lackner, Martin (2020-06-24).
30:Each agent has a "best outcome" in the set, and
1257:
1070:
831:
742:{\displaystyle \{x_{1},x_{2},\ldots ,x_{n}\}}
1249:: CS1 maint: multiple names: authors list (
736:
691:
627:
165:
147:
121:
89:
1077:Journal of Artificial Intelligence Research
966:
922:"On the Rationale of Group Decision-making"
16:Restriction on preferences in social choice
1164:
1088:
992:
127:{\displaystyle X=\{x_{1},\ldots ,x_{m}\}}
611:, then for every triplet of outcomes in
1155:. In Harks, Tobias; Klimm, Max (eds.).
1073:"Preferences Single-Peaked on a Circle"
1280:
591:
1260:Axioms of Cooperative Decision Making
1111:
969:"Social Choice and Individual Values"
919:
134:be the set of possible outcomes. Let
561:Note that the preference-relations
13:
836:A group of agents is said to have
749:as locations on a street and each
676:
60:The notion was first presented by
14:
1304:
873:single-peaked recognition problem
171:{\displaystyle N=\{1,\ldots ,n\}}
1210:. University of Michigan Press.
1112:Trick, Michael A. (1989-06-01).
658:
636:
622:
278:Definition using a common order
1262:. Cambridge University Press.
1144:
1105:
1064:
1017:
960:
913:
866:
444:
353:
71:
1:
906:
651:Non single-peaked preferences
522:is the ideal point for agent
1175:10.1007/978-3-030-57980-7_19
1130:10.1016/0165-4896(89)90060-7
1118:Mathematical Social Sciences
926:Journal of Political Economy
920:Black, Duncan (1948-02-01).
7:
1229:. Oxford University Press.
888:
10:
1309:
895:Single-parameter mechanism
848:outcome" in the set, and -
832:Related preference domains
581:{\displaystyle \succ _{i}}
229:{\displaystyle \succ _{i}}
202:{\displaystyle \succ _{i}}
1042:10.1007/s00355-010-0476-3
1030:Social Choice and Welfare
838:single-dipped preferences
628:Single-peaked preferences
605:single-peaked preferences
551:{\displaystyle x_{i}^{*}}
515:{\displaystyle x_{i}^{*}}
288:single-peaked preferences
265:{\displaystyle x_{i}^{*}}
209:. The maximum element of
20:Single-peaked preferences
1157:Algorithmic Game Theory
994:2027/inu.30000082056718
900:Star-shaped preferences
1293:Utility function types
1258:Moulin, Hervé (1991).
855:outcome are preferred
818:
791:
770:
743:
582:
552:
516:
488:
481:
390:
266:
230:
203:
172:
128:
819:
817:{\displaystyle x_{i}}
792:
771:
769:{\displaystyle x_{i}}
744:
583:
553:
517:
482:
391:
304:
267:
231:
204:
173:
129:
1227:Microeconomic Theory
1090:10.1613/jair.1.11732
801:
781:
753:
688:
565:
530:
494:
400:
309:
244:
213:
186:
138:
80:
51:median voter theorem
24:preference relations
592:Necessary condition
547:
511:
443:
352:
261:
55:strong monotonicity
844:Each agent has a "
814:
797:'s ideal point is
787:
766:
739:
578:
548:
533:
512:
497:
477:
429:
386:
338:
262:
247:
226:
199:
168:
124:
47:truthful mechanism
1269:978-0-521-42458-5
1236:978-0-19-507340-9
1217:978-0-472-08721-1
1184:978-3-030-57980-7
875:is the following
790:{\displaystyle i}
1300:
1273:
1254:
1248:
1240:
1221:
1197:
1196:
1168:
1148:
1142:
1141:
1109:
1103:
1102:
1092:
1068:
1062:
1061:
1021:
1015:
1014:
996:
964:
958:
957:
917:
877:decision problem
823:
821:
820:
815:
813:
812:
796:
794:
793:
788:
775:
773:
772:
767:
765:
764:
748:
746:
745:
740:
735:
734:
716:
715:
703:
702:
671:single-plateaued
662:
640:
587:
585:
584:
579:
577:
576:
557:
555:
554:
549:
546:
541:
521:
519:
518:
513:
510:
505:
486:
484:
483:
478:
476:
475:
466:
465:
456:
455:
442:
437:
425:
424:
412:
411:
395:
393:
392:
387:
385:
384:
375:
374:
365:
364:
351:
346:
334:
333:
321:
320:
286:is said to have
271:
269:
268:
263:
260:
255:
235:
233:
232:
227:
225:
224:
208:
206:
205:
200:
198:
197:
177:
175:
174:
169:
133:
131:
130:
125:
120:
119:
101:
100:
1308:
1307:
1303:
1302:
1301:
1299:
1298:
1297:
1278:
1277:
1276:
1270:
1242:
1241:
1237:
1218:
1201:
1200:
1185:
1149:
1145:
1110:
1106:
1069:
1065:
1022:
1018:
985:10.2307/1907815
965:
961:
918:
914:
909:
891:
869:
834:
808:
804:
802:
799:
798:
782:
779:
778:
760:
756:
754:
751:
750:
730:
726:
711:
707:
698:
694:
689:
686:
685:
679:
677:Interpretations
653:
630:
625:
594:
572:
568:
566:
563:
562:
542:
537:
531:
528:
527:
506:
501:
495:
492:
491:
471:
467:
461:
457:
451:
447:
438:
433:
420:
416:
407:
403:
401:
398:
397:
396:
380:
376:
370:
366:
360:
356:
347:
342:
329:
325:
316:
312:
310:
307:
306:
280:
274:
256:
251:
245:
242:
241:
220:
216:
214:
211:
210:
193:
189:
187:
184:
183:
139:
136:
135:
115:
111:
96:
92:
81:
78:
77:
74:
22:are a class of
17:
12:
11:
5:
1306:
1296:
1295:
1290:
1275:
1274:
1268:
1255:
1235:
1222:
1216:
1202:
1199:
1198:
1183:
1143:
1124:(3): 329–334.
1104:
1063:
1036:(2): 305–322.
1016:
959:
938:10.1086/256633
911:
910:
908:
905:
904:
903:
897:
890:
887:
868:
865:
861:
860:
849:
833:
830:
811:
807:
786:
763:
759:
738:
733:
729:
725:
722:
719:
714:
710:
706:
701:
697:
693:
678:
675:
652:
649:
629:
626:
624:
621:
593:
590:
575:
571:
545:
540:
536:
509:
504:
500:
474:
470:
464:
460:
454:
450:
446:
441:
436:
432:
428:
423:
419:
415:
410:
406:
383:
379:
373:
369:
363:
359:
355:
350:
345:
341:
337:
332:
328:
324:
319:
315:
279:
276:
272:
259:
254:
250:
240:is denoted by
223:
219:
196:
192:
182:is denoted by
167:
164:
161:
158:
155:
152:
149:
146:
143:
123:
118:
114:
110:
107:
104:
99:
95:
91:
88:
85:
73:
70:
35:
34:
31:
15:
9:
6:
4:
3:
2:
1305:
1294:
1291:
1289:
1286:
1285:
1283:
1271:
1265:
1261:
1256:
1252:
1246:
1238:
1232:
1228:
1223:
1219:
1213:
1209:
1204:
1203:
1194:
1190:
1186:
1180:
1176:
1172:
1167:
1162:
1158:
1154:
1147:
1139:
1135:
1131:
1127:
1123:
1119:
1115:
1108:
1100:
1096:
1091:
1086:
1082:
1078:
1074:
1067:
1059:
1055:
1051:
1047:
1043:
1039:
1035:
1031:
1027:
1020:
1012:
1008:
1004:
1000:
995:
990:
986:
982:
978:
974:
970:
963:
955:
951:
947:
943:
939:
935:
931:
927:
923:
916:
912:
901:
898:
896:
893:
892:
886:
883:
880:
878:
874:
864:
858:
854:
850:
847:
843:
842:
841:
839:
829:
825:
809:
805:
784:
761:
757:
731:
727:
723:
720:
717:
712:
708:
704:
699:
695:
682:
674:
672:
667:
663:
661:
656:
648:
645:
641:
639:
634:
623:Some examples
620:
618:
614:
610:
606:
602:
599:If the group
597:
589:
573:
569:
559:
543:
538:
534:
525:
507:
502:
498:
487:
472:
468:
462:
458:
452:
448:
439:
434:
430:
426:
421:
417:
413:
408:
404:
381:
377:
371:
367:
361:
357:
348:
343:
339:
335:
330:
326:
322:
317:
313:
303:
301:
297:
293:
289:
285:
275:
257:
252:
248:
239:
221:
217:
194:
190:
181:
162:
159:
156:
153:
150:
144:
141:
116:
112:
108:
105:
102:
97:
93:
86:
83:
69:
67:
66:Kenneth Arrow
64:and later by
63:
58:
56:
52:
48:
43:
40:
32:
29:
28:
27:
25:
21:
1259:
1226:
1207:
1156:
1146:
1121:
1117:
1107:
1080:
1076:
1066:
1033:
1029:
1019:
976:
973:Econometrica
972:
962:
932:(1): 23–34.
929:
925:
915:
884:
881:
872:
870:
862:
856:
852:
845:
837:
835:
826:
683:
680:
670:
668:
664:
657:
654:
646:
642:
635:
631:
616:
612:
608:
604:
600:
598:
595:
560:
523:
489:
305:
299:
295:
291:
287:
283:
281:
237:
179:
75:
62:Duncan Black
59:
44:
36:
19:
18:
1083:: 463–502.
867:Recognition
72:Definitions
39:public good
1282:Categories
1166:2004.13602
979:(1): 110.
907:References
490:In words,
282:The group
57:property.
1288:Elections
1245:cite book
1193:216562247
1138:0165-4896
1099:1076-9757
1050:0176-1714
1003:0012-9682
954:153953456
946:0022-3808
721:…
570:≻
544:∗
508:∗
459:≻
445:⇒
440:∗
427:≥
368:≻
354:⇒
349:∗
336:≤
258:∗
218:≻
191:≻
157:…
106:…
1058:14975233
889:See also
1011:1907815
1266:
1233:
1214:
1191:
1181:
1136:
1097:
1056:
1048:
1009:
1001:
952:
944:
1189:S2CID
1161:arXiv
1054:S2CID
1007:JSTOR
950:S2CID
853:worst
846:worst
607:over
290:over
76:Let
1264:ISBN
1251:link
1231:ISBN
1212:ISBN
1179:ISBN
1134:ISSN
1095:ISSN
1046:ISSN
999:ISSN
942:ISSN
871:The
857:more
603:has
414:>
323:<
1171:doi
1126:doi
1085:doi
1038:doi
989:hdl
981:doi
934:doi
298:in
236:in
1284::
1247:}}
1243:{{
1187:.
1177:.
1169:.
1132:.
1122:17
1120:.
1116:.
1093:.
1081:68
1079:.
1075:.
1052:.
1044:.
1034:36
1032:.
1028:.
1005:.
997:.
987:.
977:20
975:.
971:.
948:.
940:.
930:56
928:.
924:.
673:.
619:.
558:.
68:.
1272:.
1253:)
1239:.
1220:.
1195:.
1173::
1163::
1140:.
1128::
1101:.
1087::
1060:.
1040::
1013:.
991::
983::
956:.
936::
859:.
810:i
806:x
785:i
762:i
758:x
737:}
732:n
728:x
724:,
718:,
713:2
709:x
705:,
700:1
696:x
692:{
617:N
613:X
609:X
601:N
574:i
539:i
535:x
524:i
503:i
499:x
473:k
469:x
463:i
453:j
449:x
435:i
431:x
422:j
418:x
409:k
405:x
382:k
378:x
372:i
362:j
358:x
344:i
340:x
331:j
327:x
318:k
314:x
302::
300:N
296:i
292:X
284:N
273:.
253:i
249:x
238:X
222:i
195:i
180:i
166:}
163:n
160:,
154:,
151:1
148:{
145:=
142:N
122:}
117:m
113:x
109:,
103:,
98:1
94:x
90:{
87:=
84:X
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
