Смит жиналды - Smith set

Жылы дауыс беру жүйелері, Смит жиналды, атындағы Джон Х.Смит, сонымен қатар жоғарғы цикл, немесе Жалпыланған жоғарғы таңдау (GETCHA) - бұл белгілі бір сайлаудағы ең кішкентай бос емес кандидаттар жиынтығы, сондықтан әрбір мүше жұптық сайлауда барлық кандидаттарды жиыннан тыс жеңеді. Смит жиынтығы сайлау нәтижелері үшін оңтайлы таңдаудың бір стандартын ұсынады. Смит жиынтығынан әрқашан үміткерді сайлайтын дауыс беру жүйелері өтеді Смит критерийі және «Смит тиімді» деп аталады.

Жиынтықтың әрбір мүшесі жиынтықтан тыс барлық мүшелерді жұптық әдіспен жеңетін үміткерлер жиынтығы а деп аталады басым жиынтық.

Қасиеттері

  • Смит жиынтығы әрқашан бар және жақсы анықталған. Үстемдік жиынтықтар ұяға салынған және бос емес болғандықтан, үміткерлер жиынтығы шектеулі болғандықтан, тек бір ғана үстем жиын бар.
  • Смит жиынтығында жұптық байланыстарға байланысты немесе циклдар сияқты бірнеше кандидаттар болуы мүмкін Кондорсет парадоксы.
  • The Кондорсет жеңімпазы, егер ол бар болса, Смит жиынтығының жалғыз мүшесі болып табылады. Егер әлсіз Кондорсет жеңімпаздары бар болса, онда олар Смит жиынтығында.
  • Смит жиынтығы әрқашан өзара көпшілік - егер бар болса, ұсынылған кандидаттардың жиынтығы.[1]

Шварц салыстыру жасады

The Шварц қойылды, ретінде белгілі Жалпыланған оңтайлы аксиома немесе GOCHA, онымен тығыз байланысты және әрқашан ішкі жиын Смит жиынтығы. Смарт жиынтығы үлкен болады, егер Шварц жиынтығындағы үміткер Шварц жиынтығында жоқ үміткермен параллель тең болса ғана.

Смит жиынтығын Шварц жиынтығынан үміткерлердің екі түрін бірнеше рет қосу арқылы жасауға болады, егер олардан тыс мұндай үміткерлер болмаса:

  • жинақта кандидаттармен жұптық байланыста болатын кандидаттар,
  • жиынтықта кандидатты жеңген кандидаттар.

Екінші типтегі үміткерлер тек бірінші типтегі кандидаттар қосылғаннан кейін өмір сүре алатындығын ескеріңіз.

Баламалы тұжырымдау

Кез келген екілік қатынас жиынтықта мүмкін табиғи ішінара тәртіпті тудырады үстінде -цикл эквиваленттік сыныптар жиынтығы , сондай-ақ білдіреді .

Қашан болып табылады Beats-or-Ties үміткерлер жиынтығындағы екілік қатынас Beats-or-Ties егер және егер болса жұптық жеңілістер немесе байланыстар онда алынған ішінара реті болып табылады ұрып-соғу тәртібі бұл а жалпы тапсырыс. Смит жиынтығы - бұл максималды элемент beat-or-tie ережесінің.

Алгоритмдер

Смит жиынын -мен есептеуге болады Floyd – Warshall алгоритмі уақытында Θ. Сондай-ақ, нұсқасын пайдаланып есептеуге болады Косараджудың алгоритмі немесе Тарджан алгоритмі уақытында Θ.

Мұны үміткерлердің жұптық жеңістерінің саны бойынша минус жұптық жеңілістерден алынған рейтинг бойынша жұптық салыстыру матрицасын құру арқылы табуға болады (а Копеланд әдісі ), содан кейін барлық ұяшықтардың оң жағындағы ұяшықтар жұптық жеңістерді көрсететін етіп жабылатын ең кіші жоғарғы сол жақтағы шаршыны іздеңіз. Осы ұяшықтардың сол жағында аталған барлық үміткерлер Смит жиынтығында. (Бұл жұмыс істейді, өйткені Копеланд үміткерлерді Смит емес кандидаттарға қарағанда Смиттің үміткерлерінің ұпайлары көп болатындай етіп рейтинг жасайды[2])

Мысал: A, B және C үміткерлері Смит жиынтығында болсын, олардың әрқайсысы жұптасып басқаларының бірін ұрады, бірақ барлық 3 жұптық D және E соққыларын жеңеді, A, B және C жоғарғы 3 қатарға орналасады (солай делік) олар екі рет салыстыру кестесінің мысалы үшін), содан кейін барлық ұяшықтарды «A Beats A» -дан (A-ны өзімен салыстыратын ұяшық) «C C C» -ге дейін жабу арқылы көрінетін болады. оң жақтағы ұяшықтар (A, B және C-ді D мен E-ге салыстыратын ұяшықтар) жұптық жеңістерді көрсетер еді, ал кіші ұяшықтар жиынтығы мұны жасай алмады, сондықтан A, B және C Смит жиынтығында болатын еді.

Copeland рейтингін қолдану мысалы:

Шығындар мен байланыстар батыл
ABCД.EFG
A---ЖеңуЖоғалтуЖеңуЖеңуЖеңуЖеңу
BЖоғалту---ЖеңуЖеңуЖеңуЖеңуЖеңу
CЖеңуЖоғалту---ЖоғалтуЖеңуЖеңуЖеңу
Д.ЖоғалтуЖоғалтуЖеңу---ГалстукЖеңуЖеңу
EЖоғалтуЖоғалтуЖоғалтуГалстук---ЖеңуЖеңу
FЖоғалтуЖоғалтуЖоғалтуЖоғалтуЖоғалту---Жеңу
GЖоғалтуЖоғалтуЖоғалтуЖоғалтуЖоғалтуЖоғалту---

А С-ға дейін жоғалады, сондықтан А-дан С-ға дейінгі барлық үміткерлер (A, B және C) Смит жиынтығында екендігі расталады. Смит жиынтығында екендігі расталған үміткердің біреуі бар, ол Смит жиынтығында әлі расталмаған біреуін жоғалтады немесе байланыстырады: С D-ге ұтылады; сондықтан D Смит жиынтығында екендігі расталады. Енді тағы бір сәйкестік бар: D E-мен байланысады, сондықтан E Смит жиынтығына қосылады. А-дан Е-ге дейін барлық үміткерлер Смит жиынтығында екендігі расталмаған барлық үміткерлерді жеңгендіктен, енді Смит жиынтығы А-дан Е-ге дейін екендігі расталды.

Сондай-ақ қараңыз

Пайдаланылған әдебиеттер

  1. ^ http://dss.in.tum.de/files/brandt-research/dodgson.pdf
  2. ^ Себебі, Смит жиынтығындағы кез-келген үміткерді тек басқа Смит жиынының мүшелері жұптасып ұра немесе байлай алады, ал Смит жиынтығына кірмейтін кез-келген кандидатты Смит жиынының мүшелері жеңеді.
  • Уорд, Бенджамин (1961). «Көпшіліктің ережесі және бөлу». Жанжалдарды шешу журналы. 5 (4): 379–389. дои:10.1177/002200276100500405. Көпшілік ережеге негізделген сериялық шешім қабылдауды талдау кезінде Смит пен Шварц жиынтығын сипаттайды.
  • Смит, Дж. (1973). «Өзгермелі сайлаушылармен преференциялардың жиынтығы». Эконометрика. Эконометрикалық қоғам. 41 (6): 1027–1041. дои:10.2307/1914033. JSTOR  1914033. Жалпыға ортақ Кондорсет критерийінің нұсқасын ұсынады, ол жұптық сайлау қарапайым көпшілік таңдауға негізделген кезде орындалады, және кез-келген үстемдік жиынтығы үшін жиынтықтағы кез-келген үміткер жиынтықта жоқ кез-келген үміткерден ұжымдық түрде артықшылық алады. Бірақ Смит ең кіші басым жиынтық идеясын талқыламайды.
  • Фишберн, Питер С. (1977). «Condorcet әлеуметтік таңдау функциялары». Қолданбалы математика бойынша SIAM журналы. 33 (3): 469–489. дои:10.1137/0133030. Нарит Смиттің жалпыланған Кондорсет критерийін ең кіші басым жиынтыққа дейін тартады және оны Смиттің Кондорсет принципі деп атайды.
  • Шварц, Томас (1986). Ұжымдық таңдау логикасы. Нью-Йорк: Колумбия университетінің баспасы. Оңтайлы ұжымдық таңдау үшін мүмкін болатын стандарттар ретінде Смит жиынтығын (GETCHA атауы) және Шварц жиынтығын (GOTCHA атауы) талқылайды.

Сыртқы сілтемелер