Cu toate că domeniul isi are originile in politică şi economie, ceea ce poate frapa este caracterul izbitor algoritmic al problemelor de interes. Nu voi intra foarte adânc in amănuntele de Social Choice ale proiectului, dar cred că ar fi interesant pentru comunitate să explic în ce masură cunoştinţele din liceu ajută mai departe în cercetare. Iata câteva exemple de tehnici de la concursurile de algoritmică pe care le-am folosit pentru a obţine complexităţile îmbunătăţite din lucrare:
* Tehnica "Parametric Search", care a apărut în scena programării competiţionale o dată cu problema 'Aliens':https://ioinformatics.org/files/ioi2016problem6.pdf de la IOI $2016$. Tehnica a mai fost folosită ulterior în problema 'Popcorn':problema/popcorn, iar membrii comunităţii au găsit soluţii alternative mai simple ce o folosesc în probleme propuse în trecut: 'Padurari':problema/padurari şi 'Flooow':problema/flooow.

* Optimizarea "<tex>O(nk^2)</tex> devine <tex>O(nk)</tex>", care a apărut în România o dată cu problemele 'Arbkset':problema/arbkset, 'Lianyu':problema/lianyu şi 'Cli':problema/cli. Aceasta este o rafinare a mai cunoscutei "<tex>O(n^3)</tex> devine <tex>O(n^2)</tex>", folosită în probleme precum: 'Politic':problema/politic, 'Purification':problema/purification şi 'Tricolor':problema/tricolor. Dacă nu aţi auzit de acest smen, puteţi citi o superba explicaţie începând cu pagina $22$ de 'aici':http://www.lookingforachallengethebook.com/uploads/1/4/5/5/14555448/preview-_looking_for_a_challenge.pdf (problema Barricades).

* Optimizarea "<tex>O(nk^2)</tex> devine <tex>O(nk)</tex>", care a apărut în România o dată cu problemele 'Arbkset':problema/arbkset, 'Lianyu':problema/lianyiu şi 'Cli':problema/cli. Aceasta este o rafinare a mai cunoscutei "<tex>O(n^3)</tex> devine <tex>O(n^2)</tex>", folosită în probleme precum: 'Politic':problema/politic, 'Purification':problema/purification şi 'Tricolor':problema/tricolor. Dacă nu aţi auzit de acest smen, puteţi citi o superba explicaţie începând cu pagina $22$ de 'aici':http://www.lookingforachallengethebook.com/uploads/1/4/5/5/14555448/preview-_looking_for_a_challenge.pdf (problema Barricades).

* În afara programei de olimpiadă: 'Algoritmul Simplex':https://en.wikipedia.org/wiki/Linear_programming. Cu toate acestea, problema 'Echilibrare':problema/echilibrare admite o soluţie inedită, alternativă, folosind această tehnică; pentru majoritatea elevilor, Simplex nu e mai mult decât un "black-box". _Aside_: Având în vedere soluţia oficială a problemei, ce putem înţelege, sau intui, din acestea? Există strânse legături între problemele de flux întâlnite la olimpiada, forma lor matriceala şi problemele lor duale de optimizare. Nu nu, nu o să explic ce am vrut să zic cu asta - să vă provoc şi pe voi puţin!
Sistemul de vot pe care îl studiem se numeşte Chamberlin-Courant, şi este destul de uşor de descris. Avem $n$ candidaţi şi $m$ alegatori, fiecare alegător exprimându-şi preferinţele prin liste ordonate de preferinţe. Pentu un $k$ dat, scopul este să alegem un comitet câstigător format din $k$ candidaţi, adica unul de **cost minim**. Cum calculăm costul? Pentru fiecare alegător număram candidaţii mai bine văzuţi de către el decât toţi aleşii din comitetul de $k$, şi apoi adunăm la costul total acest număr. De exemplu, dacă primele opţiuni ale tuturor alegătorilor formeaza o mulţime de cel mult $k$ candidaţi, atunci comitetul câstigător va avea cost $0$! Din păcate, problema generală este NP-hard, dar nu este totul pierdut, deoarece în alegeri reale preferinţele candidaţilor nu sunt arbitrare, sau "worst-case", aşa cum ne obisnuiesc temerarii comisiilor, ci au destul de multa _structură_. În ce sens au structură? Depinde - esenţa este să restrângem domeniul de preferinte suficient de puţin încât să putem înca modela alegerile reale, dar şi suficient de mult încât să putem rezolva problema în timp polinomial. Nu zic mai mult să nu plictisesc!