Despre matematica votului

M-am gândit cã dacã azi România (sau o parte a ei :)) voteazã, şi acest lucru provoacã atât de multe comentarii in presã şi blogosferã, poate e bine sã aflaţi despre un rezultat clasic din domeniul matematicii votului, un rezultat care are şi aspecte moderne pe care nu cred cã le cunoaşteţi.

Mã refer la Teorema Gibbard-Satterthwaite. Este (presupunând cã nu ştiţi despre ce este vorba) un rezultat fundamental despre sistemele de vot cu cel puţin trei candidaţi (sau alternative :))

Ce spune teorema ? Pe scurt, in condiţiile de mai sus cel puţin una din condiţiile urmãtoare este adevãratã:

1. Sistemul de vot este dictatorial, in sensul cã existã unul dintre candidaţi al cãrui vot determinã rezultatul alegerilor. Cred cã sunteţi de acord cã un sistem de vot cu aceastã proprietate este unul nerezonabil.

2. Existã un candidat care nu poate fi ales/(alternativã care nu este realizabilã), oricare ar fi preferinţele alegãtorilor. Comentariul este similar celui de la punctul 1.

3. Sistemul de vot este susceptibil la vot tactic. Cu alte cuvinte: existã condiţii care pot determina unii alegãtori sã nu aleagã alternativele pe care le preferã, pentru cã pot impiedica, schimbându-şi opţiunea, realizarea alternativelor pe care le urãsc cel mai mult, facând alegeri neoptime din punctul de vedere al preferinţelor lor.

Referendumul care are loc azi este, prin decizia curţii constituţionale, unul cu trei opţiuni (din punctul de vedere al exprimãrii): DA, NU, NU PARTICIP. Nu este de mirare, prin urmare, cã referendumul oferã posibilitatea votului tactic: acest lucru urmeazã direct din teorema Gibbard-Satterthwaite.

Nu cred cã acest rezultat are neapãrat implicaţii „politice”: opţiuni colective cu cel puţin trei alternative avem mai intotdeauna (alegerile generale, de exemplu). Nici nu cred cã trebuie dramatizatã/politizatã posibilitatea votului tactic: pânã la urmã „raţionalitatea” pe care o manifestã (in teorie :)) alegãtorii se manifestã prin alegerea opţiunii care le maximizeazã utilitatea, oricare ar fi ea aceasta.

Dacã vi se pare cã teorema Gibbard-Satterthwaite are unele asemãnãri cu celebra teoremã a lui Arrow nu vã inşelaţi: ele sunt inrudite şi pot fi derivate intr-un mod unitar.

In sfârşit: dacã vã intrebaţi dacã lucrurile astea au vreo legãturã cu informatica teoreticã, domeniul meu de interes ştiinţific, rãspunsul este pozitiv. N-ar trebui sã vã mire dacã mi-aţi citit acest mesaj: in definitiv metodele de analizã Fourier a funcţiilor booleene dezvoltate in literatura de informaticã teoreticã au aplicaţii, cum spuneam, la teorema lui Arrow.

Revenind la teorema Gibbard-Satterthwaite, un rezultat recent care aparţine lui Marcus Isaksson, Guy Kindler şi Elchanan Mossel a apãrut in conferinţa FOCS 2010 şi oferã o versiune cantitativã a teoremei Gibbard-Satterthwaite. S-ar putea sã puteţi vedea (in funcţie de capriciile serverului) o prezentare video a rezultatului aici.

Ce spune  rezultatul lui lui Mossel et al. (pe Elchanan il cunosc, asta explicã formularea mea :)) ? Pentru a-l putea explica trebuie sã prezint pe scurt contextul ştiinţific in care a apãrut:

  • pe de o parte existau rezultate care arãtau cã pentru un utilizator fixat poate fi nepractic (din motive de dificultate algoritmicã) sã manipulezi o anumitã schemã de vot: Bartholdi şi Orlin,
    Bartholdi, Tovey şi Trick au arãtat cã pentru anumite scheme de vot manipularea este NP-completã. Una din autoritãţile in acest domeniu, cel al aplicãrii complexitãţii computaţionale in domeniul sistemelor de vot este nimeni altul decât coautorul meu şi fostul membru al comisiei mele de doctorat, Lane Hemaspaandra, profesor de informaticã la University of Rochester.
  • pe de altã parte, dacã posibilitatea votului tactic ar fi un fenomen izolat, valabil doar intr-un numãr restrâns de ordonãri  ale preferinţelor alegãtorilor, poate cã rezultatul din teorema lui Gibbard-Satterthwaite e mai curând unul „teoretic”.

Mossel et al. extind la cazul a cel puţin patru alegãtori un rezultat anterior al lui Friedgut, Kalai şi Nisan, (care trata cazul n=3), arãtând (dacã „traducem” limbajul matematic al teoremei in cuvinte) cã pentru orice alegere care nu indeplineşte condiţiile nerezonabile 1 şi 2 din teorema G-S de mai sus, probabilitatea ca o ordonare aleatoare a preferinţelor alegãtorilor sã permitã votul tactic este „suficient de mare”. Mai mult, acest lucru (votul tactic) poate fi realizat de un algoritm probabilist simplu.

Cu alte cuvinte: singurele metode de alegere intre cel puţin trei opţiuni care sunt „puţin susceptibile” la manipulare/strategii/vot tactic; cuvântul folosit in englezã este strategyproof; l-aţi intâlnit des dacã aţi auzit recent despre, de exemplu, algorithmic mechanism design 🙂 …

Spunea, singurele metode de alegere „puţin susceptibile” la manipulare/strategii/vot tactic sunt cele „foarte apropiate” de a fi dictatoriale, in sensul cã in majoritatea cazurilor alegerea unei singure persoane determinã rezultatul final.

EU CU CINE VOTEZ ?

Nu ştiu. Nu ştiu in primul rând dacã votaţi, şi nu imi doresc sã aflu. Dacã vã aşteptaţi sã gãsiţi aici o analizã a votului pro/anti-Bãsescu, imi pare rãu cã v-am inşelat aşteptãrile: n-o s-o fac, e plinã piaţa de asemenea „analize”, le puteţi citi pe acelea. Eu prefer sã vorbesc de lucruri care stimuleazã intelectul :), şi care sunt de interes/valabile şi la vest de Beba Veche.

NOTE:

[1]INAPOI] O diferenţã simpatic-deprimantã intre teorie şi realitate e faptul cã domeniul comportamentului strategic in vot, in agregarea preferinţelor mai general, intrã din punct de vedere tehnic in domeniul mechanism design without money. Without money este, evident, in teorie …

Anunțuri
Acest articol a fost publicat în informaticã teoreticã, popularizarea_ştiinţei. Pune un semn de carte cu legătura permanentă.

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s