Výpočetní sociální volba - Computational social choice

Výpočetní sociální volba je pole na křižovatce teorie sociální volby, teoretická informatika a analýza multiagentní systémy.[1] Skládá se z analýzy problémů vyplývajících z agregace předvolby skupiny agentů z hlediska výpočtu. Zejména se výpočetní sociální volba týká efektivního výpočtu výsledků pravidla hlasování, s výpočetní složitostí různých forem manipulace a problémy vyplývající z problému zastupující a vyvolání předvoleb v kombinatorickém nastavení.

Stanovení vítěze

Užitečnost konkrétního hlasovací systém může být výrazně omezeno, pokud výpočet vítěze voleb trvá velmi dlouho. Proto je důležité navrhovat rychle algoritmy který může vyhodnotit hlasovací pravidlo, pokud je dáno hlasovací lístky jako vstup. Jak je běžné v teorie výpočetní složitosti, je algoritmus považován za efektivní, pokud trvá polynomiální čas. Mnoho populárních pravidel hlasování lze v polynomiálním čase vyhodnotit přímým způsobem (tj. Počítat), například Počítat Borda, schvalovací hlasování, nebo pravidlo plurality. Pro pravidla, jako je Schulzeova metoda nebo hodnocené páry lze k zobrazení polynomiálního běhu použít sofistikovanější algoritmy.[2][3] Určité volební systémy je však výpočetně obtížné vyhodnotit.[4] Zejména určení vítěze pro Kemeny-Youngova metoda, Dodgsonova metoda, a Youngova metoda jsou všechny NP-těžké problémy.[4][5][6][7] To vedlo k rozvoji aproximační algoritmy a fixovatelné algoritmy s pevnými parametry zlepšit teoretický výpočet těchto problémů.[8][9][10]

Tvrdost manipulace

Podle Gibbard-Satterthwaiteova věta, mohou být všechna netriviální pravidla hlasování manipulováno v tom smyslu, že voliči mohou někdy dosáhnout lepšího výsledku zkreslením svých preferencí, tj. uvedou nepravdivé hlasování do hlasovacího systému. Teoretici sociální volby již dlouho uvažovali o způsobech, jak tuto otázku obejít, jako je návrh Bartholdiho, Toveyho a Tricka z roku 1989 založený na teorii výpočetní složitosti.[11] Zvažovali Copelandovo pravidlo druhého řádu (který lze vyhodnotit v polynomiálním čase) a dokázal, že je NP-kompletní aby volič na základě znalosti toho, jak hlasovali všichni ostatní, rozhodl, zda je možné manipulovat takovým způsobem, aby se z nějakého favorizovaného kandidáta stal vítěz. Stejná vlastnost platí pro jeden převoditelný hlas.[12]

Proto, za předpokladu široce věřené hypotézy, že P ≠ NP, existují případy, kdy polynomiální čas nestačí k určení, zda je možná prospěšná manipulace. Z tohoto důvodu jsou hlasovací pravidla, která přicházejí s NP-tvrdým problémem manipulace, „odolná“ vůči manipulaci. Je třeba poznamenat, že tyto výsledky se týkají pouze: nejhorší případ: je docela dobře možné, že manipulační problém lze obvykle snadno vyřešit a vyžaduje pouze superpolynomiální čas na velmi neobvyklých vstupech.[13]

Další témata

Turnajová řešení

A turnajové řešení je pravidlo, které se přiřadí každému turnaj sada vítězů. Jelikož preferenční profil vyvolává turnaj prostřednictvím svého většinový vztah, každé turnajové řešení lze také chápat jako hlasovací pravidlo, které využívá pouze informace o výsledcích párových většinových soutěží.[14] Bylo navrženo mnoho turnajových řešení a teoretici výpočetní sociální volby studovali složitost souvisejících problémů s určováním vítězů.[15][1]

Omezení preferencí

Omezené preferenční domény, například jednostranný nebo jednorázový přechod preference, jsou důležitou oblastí studia v teorie sociální volby, protože předvolby z těchto domén se vyhýbají Condorcetův paradox a tak může obejít výsledky nemožnosti jako Arrowova věta a Gibbard-Satterthwaiteova věta.[16][17][18][19] Z výpočetního hlediska jsou taková doménová omezení užitečná k urychlení problémů s určováním vítězů. Výpočtově náročná pravidla pro jednoho a více vítězů lze vypočítat v polynomiálním čase, když jsou předvolby vhodně strukturovány.[20][21][22][23] Na druhé straně je problém manipulace také v těchto doménách snadný, takže štíty proti manipulaci jsou méně účinné.[21][24] Dalším výpočtovým problémem spojeným s omezeními preferencí je rozpoznání, kdy daný profil preferencí patří do určité omezené domény. Tento úkol je v mnoha případech řešitelný polynomiálním časem, včetně preferencí s jedním vrcholem a jedním křížením, ale pro obecnější třídy může být obtížný.[25][26][27]

Volby pro více vítězů

Zatímco většina tradičních pravidel hlasování se zaměřuje na výběr jednoho vítěze, mnoho situací vyžaduje výběr více vítězů. To je případ pevné velikosti parlament nebo a výbor má být zvolen, ačkoli k výběru skupiny lze použít také pravidla hlasování pro více hráčů doporučení nebo zařízení nebo sdílený balíček položek. Práce ve výpočetní sociální volbě se zaměřila na definování takových pravidel hlasování, porozumění jejich vlastnostem a studium složitosti souvisejících problémů s určováním vítězů.[28][29][30][31][32]

Viz také

Reference

  1. ^ A b Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016-04-25). Příručka výpočetní sociální volby. Cambridge University Press. ISBN  9781107060432.
  2. ^ Schulze, Markus (11.7.2010). „Nová monotónní, na klonech nezávislá, obrácená symetrická a soustavně konzistentní metoda voleb pro jednoho vítěze“. Sociální volba a sociální péče. 36 (2): 267–303. doi:10.1007 / s00355-010-0475-4.
  3. ^ Brill, Markus; Fischer, Felix (01.01.2012). „Cena neutrality pro metodu hodnocených párů“. Sborník příspěvků z 26. konference AAAI o umělé inteligenci. AAAI'12: 1299–1305.
  4. ^ A b Bartholdi III, J .; Tovey, C. A .; Trick, M. A. (1989-04-01). „Hlasovací schémata, u nichž může být obtížné zjistit, kdo vyhrál volby.“ Sociální volba a sociální péče. 6 (2): 157–165. doi:10.1007 / BF00303169.
  5. ^ Hemaspaandra, Edith; Spakowski, Holger; Vogel, Jörg (16. 12. 2005). „Složitost voleb Kemenyho“. Teoretická informatika. 349 (3): 382–391. doi:10.1016 / j.tcs.2005.08.031.
  6. ^ Hemaspaandra, Edith; Hemaspaandra, Lane A .; Rothe, Jörg (1997). „Přesná analýza Dodgsonových voleb: Hlasovací systém Lewise Carrolla z roku 1876 je dokončen pro paralelní přístup k NP“. J. ACM. 44 (6): 806–825. arXiv:cs / 9907036. doi:10.1145/268999.269002.
  7. ^ Rothe, Jörg; Spakowski, Holger; Vogel, Jörg (06.06.2003). "Přesná složitost problému vítězů pro mladé volby". Teorie výpočetních systémů. 36 (4): 375–386. arXiv:cs / 0112021. doi:10.1007 / s00224-002-1093-z.
  8. ^ Caragiannis, Ioannis; Covey, Jason A .; Feldman, Michal; Homan, Christopher M .; Kaklamanis, Christos; Karanikolas, Nikos; Procaccia, Ariel D .; Rosenschein, Jeffrey S. (01.08.2012). „O sbližování voleb Dodgsona a Younga“. Umělá inteligence. 187: 31–51. doi:10.1016 / j.artint.2012.04.004.
  9. ^ Ailon, Nir; Charikar, Mojžíš; Newman, Alantha (01.11.2008). "Agregace nekonzistentních informací: hodnocení a shlukování". J. ACM. 55 (5): 23:1–23:27. doi:10.1145/1411509.1411513.
  10. ^ Betzler, Nadja; Fellows, Michael R .; Guo, Jiong; Niedermeier, Rolf; Rosamond, Frances A. (2008-06-23). Fleischer, Rudolf; Xu, Jinhui (eds.). Algoritmy s pevnými parametry pro skóre Kemeny. Přednášky z informatiky. Springer Berlin Heidelberg. str. 60–71. CiteSeerX  10.1.1.145.9310. doi:10.1007/978-3-540-68880-8_8. ISBN  9783540688655.
  11. ^ Bartholdi, J. J .; Tovey, C. A .; Trick, M. A. (1989). "Výpočetní obtížnost manipulace voleb". Sociální volba a sociální péče. 6 (3): 227–241. doi:10.1007 / BF00295861.
  12. ^ Bartholdi, John J .; Orlin, James B. (1991). "Jediný převoditelný hlas odolává strategickému hlasování". Sociální volba a sociální péče. 8 (4): 341–354. CiteSeerX  10.1.1.127.97. doi:10.1007 / BF00183045.
  13. ^ Faliszewski, Piotr; Procaccia, Ariel D. (2010-09-23). „Válka AI proti manipulaci: vyhráváme?“. AI Magazine. 31 (4): 53–64. CiteSeerX  10.1.1.205.2873. doi:10.1609 / aimag.v31i4.2314.
  14. ^ Fishburn, P. (01.01.1977). "Condorcet Social Choice Functions". SIAM Journal on Applied Mathematics. 33 (3): 469–489. doi:10.1137/0133030.
  15. ^ Moon, John W. (01.01.1968). Témata o turnajích. Holt, Rinehart a Winston.
  16. ^ Black, Duncan (01.01.1948). „O důvodech skupinového rozhodování“. Journal of Political Economy. 56 (1): 23–34. doi:10.1086/256633. JSTOR  1825026.
  17. ^ Rothstein, P. (01.12.1990). Msgstr "Objednat omezené preference a většinové pravidlo". Sociální volba a sociální péče. 7 (4): 331–342. doi:10.1007 / BF01376281.
  18. ^ Arrow, Kenneth J. (2012-06-26). Sociální volba a individuální hodnoty. Yale University Press. ISBN  978-0300186987.
  19. ^ Sen, Amartya; Pattanaik, Prasanta K (01.08.1969). "Nezbytné a dostatečné podmínky pro racionální volbu na základě většinového rozhodnutí". Journal of Economic Theory. 1 (2): 178–202. doi:10.1016/0022-0531(69)90020-9.
  20. ^ Elkind, Edith; Lackner, Martin; Peters, Dominik (01.07.2016). „Omezení preferencí ve výpočetní sociální volbě: nedávný pokrok“ (PDF). Sborník z 25. mezinárodní konference o umělé inteligenci. IJCAI'16: 4062–4065.
  21. ^ A b Brandt, Felix; Brill, Markus; Hemaspaandra, Edith; Hemaspaandra, Lane (01.01.2015). „Obcházení kombinatorických ochran: Algoritmy polynomiálního času pro jednopólové voliče“. Journal of Artificial Intelligence Research. 53: 439–496. doi:10.1613 / jair.4647.
  22. ^ N., Betzler; A., Slinko; J., Uhlmann (2013). „O výpočtu plně proporcionálního zastoupení“. Journal of Artificial Intelligence Research. 47 (2013): 475–519. arXiv:1402.0580. Bibcode:2014arXiv1402.0580B. doi:10.1613 / jair.3896.
  23. ^ Skowron, Piotr; Yu, Lan; Faliszewski, Piotr; Elkind, Edith (2015-03-02). "Složitost plně proporcionálního zastoupení voličů s jedním křížením". Teoretická informatika. 569: 43–57. arXiv:1307.1252. doi:10.1016 / j.tcs.2014.12.012.
  24. ^ Faliszewski, Piotr; Hemaspaandra, Edith; Hemaspaandra, Lane A .; Rothe, Jörg (01.02.2011). „Štít, který nikdy nebyl: Společnosti s preference s jedním vrcholem jsou otevřenější manipulaci a kontrole“. Informace a výpočet. 209 (2): 89–107. arXiv:0909.3257. doi:10.1016 / j.ic.2010.09.001.
  25. ^ Peters, Dominik (2016-02-25). Msgstr "Rozpoznávání vícerozměrných euklidovských předvoleb". arXiv:1602.08109 [cs.GT ].
  26. ^ Doignon, J. P .; Falmagne, J. C. (01.03.1994). "Polynomiální časový algoritmus pro jednorozměrné rozvinutí reprezentací". Journal of Algorithms. 16 (2): 218–233. doi:10.1006 / jagm.1994.1010.
  27. ^ Escoffier, Bruno; Lang, Jérôme; Öztürk, Meltem (01.01.2008). Jednotná vrcholná konzistence a její složitost. Sborník konference z roku 2008 o ECAI 2008: 18. evropská konference o umělé inteligenci. 366–370. ISBN  9781586038915.
  28. ^ Skowron, Piotr; Faliszewski, Piotr; Lang, Jerome (01.01.2015). Nalezení kolektivní sady položek: Od proporcionální multireprezentace po doporučení skupiny. Sborník z dvacáté deváté konference AAAI o umělé inteligenci. AAAI'15. 1402. 2131–2137. arXiv:1402.3044. Bibcode:2014arXiv1402.3044S. ISBN  978-0262511292.
  29. ^ Elkind, Edith; Faliszewski, Piotr; Skowron, Piotr; Slinko, Arkadii (01.01.2014). Vlastnosti pravidel hlasování pro více hráčů. Sborník mezinárodní konference 2014 o autonomních agentech a multiagentních systémech. AAMAS '14. 1506. str. 53–60. arXiv:1506.02891. Bibcode:2015arXiv150602891E. ISBN  9781450327381.
  30. ^ Procaccia, Ariel D .; Rosenschein, Jeffrey S .; Zohar, Aviv (2007-04-19). "O složitosti dosažení poměrného zastoupení". Sociální volba a sociální péče. 30 (3): 353–362. doi:10.1007 / s00355-007-0235-2.
  31. ^ Lu, Tyler; Boutilier, Craig (01.01.2011). Rozpočtová sociální volba: Od konsensu po personalizované rozhodování. Sborník z dvacáté druhé mezinárodní společné konference o umělé inteligenci. IJCAI'11. str. 280–286. doi:10.5591 / 978-1-57735-516-8 / IJCAI11-057. ISBN  9781577355137.
  32. ^ Skowron, Piotr; Faliszewski, Piotr; Slinko, Arkadii (01.05.2015). "Dosažení plně poměrného zastoupení: výsledky přibližnosti". Umělá inteligence. 222: 67–103. arXiv:1312.4026. doi:10.1016 / j.artint.2015.01.003.

externí odkazy

  • Webové stránky COMSOC, nabízející sbírku materiálů souvisejících s výpočetní sociální volbou, jako jsou akademické workshopy, disertační práce a seznam adresátů.