Predictibilitate, influenţe, vot

Suntem (de când se voteazã din nou liber in România) atât de obişnuiţi cu sistemul  majoritar incât tindem sã uitãm faptul cã el nu este folosit peste tot in lume  – cazul alegerilor prezidenţiale americane este desigur cel mai spectaculos. La ei (probabil ştiaţi) preşedintele este ales indirect, de cãtre 538 de electori, grupaţi in colegiul electoral. Alegerile prezidenţiale au doar rolul de a stabili componenţa acestui colegiu. In majoritatea statelor candidatul care câştigã majoritatea voturilor in acel stat primeste sprijinul tuturor electorilor statului. Pentru a complica situaţia, in Maine şi Nebraska regula de alocare a electorilor e diferitã. Sistemul  american poate produce rezultate care contrazic votul majoritãţii: la alegerile din anul 2000 Al Gore a câştigat votul popular dar preşedinte a devenit George W. Bush.

Pentru a vã trezi interesul voi continua cu un puzzle: sã presupunem cã avem alegeri cu doi candidaţi, 0 si 1, atât in România cât şi  in Statele Unite. Sondajele de opinie (efectuate de statisticieni diletanţi – care pur si simplu au intervievat aleator un numãr de persoane din intreaga populaţie   :), fãrã stratificare, estimarea prezenţei la vot, etc – dar, crucial,  la fel de (in)competenţi in ambele cazuri :)) oferã estimãri identice: candidatul 1 e in fruntea sondajelor cu 50.01 la sutã din voturi. Pe care din rezultate pot fi mai sigur, pe cel de la noi sau cel din Statele Unite ?

La drept vorbind, nu vã pot oferi rãspunsul la aceastã intrebare, pentru cã nu il ştiu. Detaliile „din viata realã” (de exemplu prezenţa la vot) pot influenţa decisiv rãspunsul. Ar fi neserios din partea mea sã pretind cã modele matematice idealizate (precum cele de mai jos) pot oferi rãspunsuri corecte altfel decât din intâmplare  (sã ne reamintim, o monedã are dreptate in aproximativ 50% din cazuri) …

Acestea fiind spuse, sper cã aţi inteles cã problema de mai sus e un pretext pentru o excursie in matematica sistemelor de vot. Mai precis, domeniul la care mã voi referi este analiza (Fourier a) funcţiilor booleene, şi felul in care se aplicã unor probleme de tipul celei de mai sus.

Sã presupunem cã in alegerile noastre idealizate avem cinci votanţi care aleg intre doi candidaţi, 0 si 1. Putem reprezenta opţiunile lor printr-un „cuvânt” de genul 01011. In sistemul majoritar „votul” de mai sus l-ar desemna câştigãtor pe candidatul 1, spre deosebire de cuvântul 01010. Voi nota un cuvânt de genul asta cu x. Iar valorii bitului al cincilea din x ii voi spune, evident, {\bf x_{5}}. Dacã alegãtorii aveau initial optiunile specificate de cuvântul x, va trebui sã inventez un nume pentru cuvântul care reprezintã situaţia in care alegãtorul 5 se rãzgândeşte şi işi schimbã opţiunea. Ii voi spune acestui cuvânt {\bf \omega_{5}(x)}. In general, cand avem un numãr general de alegãtori (pe care il notãm cu n), putem reprezenta sistemul nostru de votare printr-o funcţie booleanã f, definitã pe \{0,1\}^{n} (am notat astfel mulţimea cuvintelor de lungime n cu „litere” 0 si 1), şi care au valori 0 sau 1. Mai presupunem cã nu cunoaştem exact opţiunile tuturor alegãtorilor (in alegerile reale nu le ştim) dar cunoaştem (din sondaje) o probabilitate, pe care o notãm cu p, ca alegãtorii sã il voteze oe candidatul 1. Evident, ca aceastã probabilitate sã fie cu adevãrat folositoare, mai trebuie sã presupunem cã votanţii aleg independent unul de celãlalt (lucru care, aşa cum am vãzut, nu se intamplã in realitate).

Bun, pentru cã nu avem informaţii complete nu putem decât sã estimãm probabilitatea ca 1 sã câştige alegerile. Voi nota cu \mu_{p}(f) aceastã probabilitate. In general acest numãr e greu de calculat exact. In orice caz, intr-un sistem de vot „rezonabil” \mu_{1/2}(f)=\frac{1}{2} (nu dorim sã acordãm din start un avantaj unuia dintre candidaţi, nu-i aşa ?).

Multe sisteme de vot sunt funcţii booleene monotone. Asta inseamnã cã faptul cã dacã in ultima clipã decid sã il votez pe candidatul deja câştigãtor, lucrul acesta n-are cum sã-i dãuneze 🙂 Sistemele din România şi Statele Unite sunt, evident, funcţii monotone. Nu este foarte surprinzãtor faptul cã pentru astfel de metode funcţia \mu_{p}(f) de mai sus, definitã pe [0,1] cu valori [0,1] este una monoton crescãtoare: cu cât e mai probabil sã votez un candidat, cu atât e mai probabil ca el sã câştige.

Demonstraţia faptului de mai sus e simplã, dar foloseste un concept (cuplajul a doua variabile aleatoare) care nu se predã in cursurile universitare de probabilitãţi din România – un fel de a spune cã meritã cititã de cei interesaţi 🙂

CUM MÃSOR INFLUENŢA VOTULUI MEU ? …

Ideea e simplã: care e probabilitatea ca votul meu sã decidã câstigãtorul. Spun probabilitatea pentru cã nu pot sã ştiu, inainte de a afla rezultatul, cum au votat exact ceilalţi alegãtori. Tot ce ştiu e probabilitatea ca sã-l voteze pe unul din candidaţii 1 sau 0. Prin urmare influenţa alegãtorului 5 asupra metodei de vot f este

I_{5}^{p}(f) = Pr_{p}[f(x)\neq f(\omega_{5}(x))].

Un punct cumva subtil in definiţia de mai sus: in definiţie nu am luat in calcul cum voteazã alegãtorul 5, ci doar dacã sistemul de vot il pune in poziţia ca votul lui sã fie crucial. Influenţa depinde, evident, de felul in care voteazã restul alegãtorilor: dacã restul votanţilor il aleg pe primul din candidaţi cu probabilitate 0.9, influenţa votului meu va fi, evident, practic nulã, el contând doar in cazul puţin probabil – dar nu imposibil – in care restul voturilor s-ar impãrţi in mod egal.

… DAR PREDICTIBILITATEA UNUI SISTEM DE VOT ?

Am spus cã voi presupune procente foarte apropiate de 50%, cu alte cuvinte p\sim 0.5. Pentru a mãsura predictibilitatea unui sistem de vot trebuie sã vãd in ce mãsurã uşorul avans faţã de 50% ii creşte candidatului „cu şanse mai bune” probabilitatea de a câştiga. OK, e timpul pentru a vã reaminti ceva din analiza de clasa a 11-a :). Rata de creştere a unei functii „netede” in jurul unui punct se poate calcula folosind derivata funcţiei in acel punct. In cazul nostru, pentru un numãr finit de candidaţi, functia \mu_{p}(f) este  o functie analiticã şi monoton crescãtoare. Mãrimea care ne intereseazã, Predict_{p}[f], este deci

Predict_{p}[f] = \frac{d\mu_{p}(f)}{dp}.

In cazul unei alegeri foarte strânse ne intereseazã predictibilitatea in punctul p=\frac{1}{2}. Dar mãrimea are sens pentru orice p, şi ar fi utilã, de exemplu, dacã vrem sã pariem pe procentele finale 🙂

PREDICTIBILITATE VERSUS INFLUENŢE: LEMA LUI MARGULIS-RUSSO

Am ajuns in punctul in care vã pot dezvãlui un prim secret pe care ni-l pune la dispoziţie matematica funcţiilor booleene: existã o relatie strânsã (şi foarte simplã) intre predictibilitate şi influenţe (aşa cum le-am definit mai sus). Ea se exprimã prin formula:

Predict_{p}[f]=I_{1}^{p}(f)+I_{2}^{p}(f)+\ldots+I_{n}^{p}(f).

Altfel spus: o metodã de vot este cu atât mai predictibilã cu cât puterea medie a unui alegãtor de a fi decisiv in stabilirea rezultatului este mai mare. Sunã uşor paradoxal la prima vedere, nu-i asa ?

Formula de mai sus se numeşte lema lui Margulis-Russo si a apãrut mai intâi intr-o teorie din fizica matematicã numitã teoria percolãrii. Demonstraţia ei este, credeţi-mã, foarte simplã: orice student care a trecut prin analiza de anul intâi din facultate (calcul diferenţial in mai multe variabile, derivate parţiale, etc) o poate inţelege uşor.

VOTUL MAJORITAR: CEL MAI PREDICTIBIL

Da, aţi inteles bine. Din toate sistemele de votare (a.k.a funcţii booleene) f monotone de n variabile funcţia „majoritate” este cea care maximizeazã cantitatea Pred_{\frac{1}{2}}[f]. Un alt fel de a enunţa proprietatea de mai sus este urmãtorul: din toate funcţiile monotone f, funcţia MAJORITATE pe n biţi este cea pentru care panta funcţiei \mu_{p}(f) in punctul 1/2 este cea mai mare; altfel spus, intervalul in jurul lui 1/2 in care functia  \mu_{p}(f) creşte de la aproape zero la aproape 1 este cel mai restrâns.

PREDICTIBILITATE VERSUS STABILITATE

Pânã acum am presupus cã voturile sunt numãrate 100% corect – un singur vot in plus era de ajuns pentru a inclina balanţa in favoarea unuia sau altuia din candidaţi. In realitate ştim cu toţii cã nu se intâmplã aşa; chiar neluând in calcul eventuale tentative de fraudare, pentru fiecare vot luat in parte exista o posibilitate – micã – de a fi centralizat incorect. Putem modela situaţia de mai sus in felul urmãtor: consideram un cuvânt x. Perturbãm fiecare bit al lui x independent cu o probabilitate micã, aceeaşi pentru toti biţii, pe care o vom nota cu \epsilon. Cuvântul perturbat il vom nota cu x_{\epsilon}.

Masurãm stabilitatea unei metode de vot f prin probabilitatea ca rezultatul sã rãmânã neschimbat, adicã egal cu f(x), unde x e luat la rândul lui la intâmplare. In simboluri

S_{\epsilon}(f)=Prob[ f(x)=f(x_{\epsilon})].

Stabilitatea are de-a face, evident, cu „predictibilitatea” in sens intuitiv – dar nu neapãrat in sensul descris inainte. Mai curând mãsoarã „rezistenţa la erori” – lucru foarte important când votul e de aproximativ 50-50 %, aşa cum au arãtat alegerile americane din 2000 🙂

Care e funcţia cea mai stabilã ? Pentru un rãspuns cu sens la aceastã intrebare trebuie sã limitãm clasa funcţiilor f pe care le luãm in considerare:

  • o primã condiţie e una pe care am mai intalnit-o, \mu_{1/2}(f)=1/2.
  • cea de-a doua impune faptul ca influenţa oricãrui bit asupra lui f sã fie suficient de micã. Dacã n-am pune aceastã condiţie atunci o funcţie ca f(x_{1},x_{2},\ldots, x_{n})=x_{1}, care depinde practic doar de bitul x_{1} ar fi foarte stabilã – insã nu ne intereseazã genul acesta de „alegeri” 🙂

Cu aceste clarificãri, rãspunsul la intrebarea de mai sus (cu nişte fineţuri tehnice pe care le omit :)) este din nou funcţia MAJORITATE. Spre deosebire de rezultatul despre predictibilitate, acest rezultat e mult mai greu de demonstrat – el a apãrut abia in 2006, intr-o lucrare publicatã intr-una din cele doua conferinţe de top din domeniul informaticii teoretice – echivalentul „Science” sau „Nature” pentru acest domeniu. Nu pot da amãnunte privind demonstraţia intr-o prezentare „de popularizare” precum aceasta – pentru specialişti pot spune ca intervin elemente de analizã funcţionalã, de genul inegalitãţilor hipercontractive pentru anumiţi operatori …. mã opresc aici, pentru restul lumii „pãsãreasca” aceasta nu e prea interesantã 🙂

INTERMEZZO: DE CE ANALIZA FOURIER ?

Cititorul atent a observat poate faptul ca am folosit cuvintele „analiza Fourier”, şi mai ştie poate faptul cã aceastã teorie e folositã la „descompunerea” unui semnal in sinusoide.

In cazul nostru nu e vorba de metoda „cu aplicaţii inginereşti” de mai sus: funcţiile cu care lucrãm nu sunt „semnale” definite pe un interval de numere reale, ci  funcţii cu un numar finit de valori definite pe un spaţiu discret de elemente care nu sunt numere, cuvintele de tip \{0,1\}^{n}. Principiul este insa similar: cãutãm o „bazã ortonormatã” care sa ne permitã sã descompunem o funcţie f intr-o combinatie liniarã de componente ale bazei. Cum se face asta in mod concret, şi ce legaturã au lucrurile astea cu cele de care am vorbit inainte (influenţe, predictibilitate, stabilitate, etc) ? Sper sã prezint lucrurile intr-un mesaj ulterior (fatalmente foarte tehnic).

Ce este important la funcţiile booleene este faptul cã spaţiul pe care sunt definite (acela al cuvintelor de lungime n) are o structurã matematicã de grup. Acesta este cadrul natural pentru tipul de analiza Fourier pe care il folosim – teoria este mai uşoarã in cazuri (precum cel al functiilor booleene) in care grupul pe care e definit funcţia este abelian (comutativ). In cazul nostru acest lucru este adevãrat, şi se reduce in esenţã la faptul cã funcţia XOR pe doi biţi este simetricã: x \oplus y = y \oplus x pentru oricare doi biţi x si y. Pentru grupuri necomutative (de exemplu permutãrile a n elemente care, precum am invãţat in clasa a 11-a, nu comutã faţã de compunere pentru n\geq 3) teoria e mai  abstractã şi foloseşte aşa-numitele reprezentãri de grupuri. Sunã abstract ? Da, dar e vorba de metode foarte puternice, şi cu  aplicaţii la probleme foarte „concrete” din analiza algoritmilor. Un singur exemplu:

Algoritmul „şcolãresc” de inmulţire a doua matrici n\times n efectueazã un numãr cubic de operaţii, dar el nu este optim. Studenţii la informaticã au intâlnit poate in cursul de algoritmi metoda lui Strassen, cu un numar de operaţii cu ordin de mãrime n^{\log_{2}(7)}. Complexitatea problemei inmulţirii matricilor nu este intru totul elucidatã: avem in orice caz nevoie de cel puţin n^2 operaţii, pentru cã vrem sa calculãm n^2 numere. Dar nu e clar dacã algoritmi cu complexitate de ordin n^{2+\epsilon} sunt posibili pentru orice \epsilon >0. Problema dã naştere la consideratii matematice extrem de sofisticate. In tot cazul, algoritmii cu exponentul cel mai bun cunoscuţi in prezent pot fi obtinuţi (şi explicaţi) folosind metodele „abstracte” de mai sus (analiza Fourier pe grupuri). O prezentare „de popularizare” a acestui rezultat este disponibilã aici.

DE LA ANALIZA FOURIER LA TEOREMA LUI ARROW

Inchei lunga parantezã despre analiza Fourier a funcţiilor booleene spunând cã metodele astea au aplicaţii in domenii foarte variate din informatica teoreticã. Eu m-am intâlnit cu ele in problemele care ma intereseazã cel mai mult:  tranziţii de fazã in probleme combinatoriale. Nu pot explica aici cum se aplicã, dar dacã ne gândim la faptul câ am definit mai sus predictibilitatea unei metode ca derivata unei funcţii (\mu_{p}(f)), parca relevanţa lor  in studiul unor „tranziţii” (salturi bruşte) e mai puţin misterioasã.

Vreau sã inchei cu inca un rezultat din teoria deciziilor de vot. Celebra teoremã a lui Arrow afirmã in esenţã faptul cã singurele metode de vot care satisfac un numãr mic de condiţii relativ intuitive sunt cele „dictatoriale”. Am vazut mai sus cum putem modela o astfel de metoda de „decizie”. Nu este deloc surprinzâtor faptul ca metode „contemporane”, precum cele pe care le-am oferit mai sus, pot imbunãtãţi rezultatul clasic al lui Arrow.

Teorema la care ma refer ii aparţine matematicianului Gil Kalai, autor a unei minunate introduceri in acest gen de probleme, publicatã intr-un volum pe care l-am editat acum câţiva ani. Scenariul este cel al Teoremei lui Arrow: presupunând cã nu acceptãm metode de alegere „dictatoriale”, rezultã faptul cã trebuie sã sacrificãm pentru aceasta una din celelalte condiţii. Una din aceste condiţii, independenţa alternativelor irelevante, este inruditã (intr-un sens oarecum tehnic pe care nu-l explic aici) cu inexistenţa unor situaţii „iraţionale” precum cele descrise de aşa numitul paradox al lui Condorcet. Acest paradox se referã la posibilitatea existenţei unor preferinţe ale alegãtorilor pentru care metoda de alegere dã naştere la un „ciclu de preferinţe” intre trei candidaţi A,B,C, preferând pe A lui B, pe B lui C, pe C lui A.

Paradoxul lui Condorcet nu e neapãrat relevant in toate situaţiile de vot: de exemplu daca preferinţele alegãtorilor sunt complet identice, realizarea clasamentului final nu comportã vreun paradox. Rezultatul lui Kalai introduce un context probabilist in acest scenariu: presupune faptul ca profilurile preferinţelor alegãtorilor sunt alese aleator şi investigheazã probabilitatea apariţiei unui scenariu de tip Condorcet. Arrow a aratat ca aceasta probabilitate e intotdeauna pozitivã. Kalai demonstreazã de exemplu faptul cã pentru orice metoda de alegere dintre trei candidaţi care este o functie simetricã in preferinţele alegãtorilor probabilitatea apariţiei unei „situaţii iraţionale” este mai mare de 8%.

VREŢI SÃ CUNOAŞTEŢI MAI MULT ?

Din câte ştiu nu existã  referinţe bibliografice actuale in limba românã pe aceasta temã. Exista insã multã literaturã, liber accesibilã pe internet, in limba englezã – stau la dispoziţie cititorului interesat, recomandând incã o datã introducerea (mult mai lungã şi tehnicã, dar oarecum tot „de popularizare”) la care m-am referit mai sus.

Anunțuri
Acest articol a fost publicat în Eseuri. 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