3. Algorytm ZGP

2013.03.25

Algorytm ZGP

Systemy wyborcze PGP i ZGP ("Pojedynczy Głos Przechodni" i "Zbiorczy Głos Przechodni") są pewnymi osobnymi grupami wśród metod preferencyjnych. Idea metod preferencyjnych (transferowych, "Głosu Przechodniego") polega na tym, że w obliczaniu wyniku wyborów, dla wybrania każdego kolejnego kandydata jest potrzebna pewna ustalona (automatycznie) 'właściwa' (optymalna) ilość wyborców (czy(li) ich 'kart wyborczych'), przydzielanych w chwili wyboru temu kandydatowi - i ta ilość ma być już wyłączona z dalszych obliczeń, tzn. przy wybieraniu kolejnych kandydatów.

Idee PGP i ZGP różnią się tym, że w PGP po wybraniu kandydata, jego nadmiarowe 'głosy' są przekazywane ('spychane') innym kandydatom (trudno jest obliczyć, komu najlepiej je przekazać), natomiast w ZGP nadmiarowe 'głosy' są brane ('wyciągane') od całego zestawu już wybranych kandydatów i przydzielane następnemu najlepszemu (optymalnemu) kandydatowi (łatwo obliczyć któremu - jest więc to metoda też bardziej obiektywna).

Poniższy algorytm jest napisany częściowo opisowo, częściowo skrótowo, a częściowo w języku podobnym do 'tradycyjnych' języków programowania.



PROGRAM MetodaZGP ;

   // "IleGłosówWymag" jest to wymagana ilość wyborców głosujących
   // na jakiegoś kandydata, potrzebna do uznania tego kandydata za wybranego.
   // Zwykle, standardowo przyjmuje się jej następującą wartość:
   IleGłosówWymag = 1 + CzęśćCałkowita( IlośćKartWyborczych / (IlośćKandydatówDoWybrania + 1) ) ;

   WczytanieKartDoGłosowania ;
   // z zapamiętaniem każdej karty osobno np. w macierzy
   // 2-wskaźnikowej o wymiarach IlośćKart x IlośćKandydatów;
   // wartość w elemencie macierzy o wskaźnikach 'w1' i 'w2' jest to
   // numer kolumny (czyli numer preferencji, czyli numer etapu
   // obliczania wyniku wyborów), w której wyborca o numerze 'w1'
   // zaznaczył w swojej karcie wyborczej kandydata o numerze 'w2'
   // (a np. 0, jeśli go nie zaznaczył);
   // Uwaga: jeśli na jakiejś karcie wyborczej jakiś kandydat ma
   // wpisany krzyżyk w więcej niż jednej kolumnie, to uznana
   // powinna być tylko jedna z tych kolumn
   // (można by przyjąć, że zawsze pierwsza z nich)
   //----------------

   ObliczWynikGłosowania( IleGłosówWymag ) ;

   // Podczas obliczania wyniku wyborów program ten powinien
   // zapisywać w jakimś pliku historię tego obliczania
   // (z wybieranym stopniem szczegółowości)
   // a więc np. decyzje, który kandydat zostaje uznany
   // za wybranego i na jakiej podstawie
   // Dzięki temu można by porównać obliczenia z innymi
   // programami, łatwiej szukać błędów, pokazać wyborcom,
   // aby bardziej zrozumieli tę metodę itp..
ENDPROGRAM MetodaZGP ;
//------------------------------------------------------------------

PROCEDURE ObliczWynikGłosowania( IleGłosówWymag ) ;

   // macierz: którzy kandydaci zostali już wybrani
   VAR JestUznanyZaWybranego[1..IlośćKandydatów] OF BOOLEAN ;

   VAR IlośćPozostGłosówDlaKand[1..IlośćKandydatów] OF INTEGER ;

   NrAktualnegoEtapu = 1 ; // nr kolumny z krzyżykami (czyli nr preferencji),
          // do której włącznie (od 1.) są sumowane 'głosy'

   BrakDalszychEtapow = FALSE ; // jeśli 'TRUE', to nie byłaby już wymagana wartość 'IleGłosówWymag'

   WHILE ZliczKandWybranych( JestUznanyZaWybranego ) < IlośćKandydatówDoWybrania    // tzn. ilość miejsc
      // Trzeba szukać kolejnego kandydata do wybrania

      ObliczIlośćPozostGłosówDlaKand( IlośćPozostGłosówDlaKand ) ;

      //----
      // wybranie numeru tego kandydata, który ma w tej macierzy
      // (w parametrze aktualnym) największa ilość 'głosów';
      // uwaga: mogą się zdarzyć takie sytuacje, że paru kandydatów
      // spełnia wymagany warunek, podczas gdy tylko jeden kandydat
      // miał zostać wybrany; w takiej sytuacji należy użyć
      // dodatkowych kryteriów: najpierw porównać ilość 'głosów'
      // takich kandydatów w pierwszej preferencji (kolumnie),
      // a jeśli jest równa, to w drugiej itd. (aż do ostatniej),
      // (potem ew. też dodatkowych kryteriów, np. ilości głosów
      // poparcia przy kandydowaniu na kandydata, itp.)
      NrKand = WybierzNajlepszegoKand( IlośćPozostGłosówDlaKand ) ;
      IleGłosówNajlepszegoKand = IlośćPozostGłosówDlaKand( NrKand ) ;

      IF IleGłosówNajlepszegoKand >= IleGlosówWymag THEN
         // kandydat uzyskał wymaganą ilość 'głosów'
         JestUznanyZaWybranego( NrKand ) = TRUE ;
         IleGłosówPrzydzielonych( NrKand ) = IleGlosówWymag ;
      ELSEIF NOT BrakDalszychEtapow AND NrAktualnegoEtapu < IlośćEtapów THEN
         // dalsze szukanie odbędzie się w większej ilości kolumn (==preferencji==etapów)
         NrAktualnegoEtapu = NrAktualnegoEtapu + 1 ;
      ELSE
         // wtedy nie jest wymagana 'standardowa' ilość 'głosów'
         BrakDalszychEtapow = TRUE ;
         JestUznanyZaWybranego( NrKand ) = TRUE ;
         IleGłosówPrzydzielonych( NrKand ) = IleGłosówNajlepszegoKand ;
      ENDIF ;
   ENDWHILE ;
ENDPROCEDURE ObliczWynikGłosowania ;
//------------------------------------------------------------------

// ** podstawowy fragment algorytmu ZGP **
// Wpisanie do macierzy (parametr) ilości pozostałych głosów (kart) dla każdego z kandydatów
PROCEDURE ObliczIlośćPozostGłosówDlaKand( IlośćPozostGłosówDlaKand ) ;

   FOR NrKand IN ZbiórNumerówKandydatówJeszczeNieUznanychZaWybranych( JestUznanyZaWybranego )
       IlośćKartDlaKand = JakaśDużaWartość ; // (większa od ilości głosów na kandydata)

      FOR Pzk IN ZbiórWszystkichPodzbiorówNumerówKandydatówJużUznanychZaWybranych( JestUznanyZaWybranego )

         // Ilość kart wyborczych, w których od etapu nr 1 do etapu
         // aktualnego jest zaznaczony któryś kandydat z Pzk, ale nie
         // ma tam kandydata nr NrKand
         IlośćKartZPzkAleBezKand = ZliczIlośćKartZPzkAleBezKand( Pzk, NrKand ) ;

         // Ilość kart wyborczych, w których od etapu nr 1 do etapu
         // aktualnego jest zaznaczony któryś z kandydatów z Pzk
         // i jednocześnie też kandydat nr NrKand
         IlośćKartZPzkIZKand = ZliczIlośćKartZPzkIZKand( Pzk, NrKand ) ;

         // Ilość kart wyborczych, w których od etapu nr 1 do etapu
         // aktualnego jest zaznaczony kandydat nr NrKand, ale nie
         // ma tam któregokolwiek z kandydatów z Pzk
         IlośćKartZKandAleBezPzk = ZliczIlośćKartZKandAleBezPzk( Pzk, NrKand ) ;

         // obl.ilości pozostałych kart dla kandydata NrKand - idea:
         // ponieważ dla wszystkich kandydatów z Pzk została już
         // przydzielona ustalona ilość kart ('głosów')
         // = IlośćKartPrzydzDlaPzk (suma z IleGłosówPrzydzielonych dla Pzk),
         //       uwaga: dopóki było NOT BrakDalszychEtapow,
         //       to wtedy IlośćKartPrzydzDlaPzk = IleGłosówWymag * IlośćElementówZbioru(Pzk)
         // więc tę ilość IlośćKartPrzydzDlaPzk trzeba odliczyć od IlośćKartZPzkAleBezKand,
         // jeśli jednak IlośćKartZPzkAleBezKand - IlośćKartPrzydzDlaPzk 0, to wtedy
         // brakującą wartość trzeba wziąć z IlośćKartZPzkIZKand;
         // pozostała z IlośćKartZPzkIZKand wartość dodana do IlośćKartZKandAleBezPzk
         // jest IlośćKartPozostPrzezPzk = ilość kart dla NrKand
         // pozostawionych przez Pzk, czyli:

         IlośćKartPrzydzDlaPzk = ZliczKartyZPzk( Pzk, IleGłosówPrzydzielonych ) ;

         IF IlośćKartZPzkAleBezKand >= IlośćKartPrzydzDlaPzk THEN
            IlośćKartPozostPrzezPzk = IlośćKartZPzkIZKand + IlośćKartZKandAleBezPzk ;
         ELSE
            IlośćKartPozostPrzezPzk = IlośćKartZPzkAleBezKand + IlośćKartZPzkIZKand -
                                                   IlośćKartPrzydzDlaPzk + IlośćKartZKandAleBezPzk ;
         ENDIF ;

         // szukana jest najmniejsza wartość wśród wszystkich
         // kandydatów z Pzk (eliminowane są takie pokrywania się
         // (także częściowe) zaznaczeń kandydatów,
         // które nie pozostawiają odpowiedniej ilości jeszcze
         // 'wolnych' kart do wybrania następnego kandydata
         // spośród tych pokrywających się)
         IlośćKartDlaKand = Min( IlośćKartDlaKand, IlośćKartPozostPrzezPzk ) ; // wart.niewiększa
      ENDFOR Pzk;

      IlośćPozostGłosówDlaKand( NrKand ) = IlośćKartDlaKand ;
   ENDFOR NrKand ;

   // Uwaga: gdyby 'głosy' były zapisane w pamięci sekwencyjnej,
   // (tzn. ze znacznie szybszym odczytem sekwencyjnym) i byłoby ich
   // bardzo dużo, to ich odczytywanie dobrze byłoby zoptymalizować
ENDPROCEDURE ObliczIlośćPozostGłosówDlaKand ;
//======================================================================


Różne odmiany algorytmu ZGP

Jednym z celów pewnej grupy odmian algorytmu ZGP jest wyrównywanie stopnia reprezentatywności wybieranych kandydatów.

Podczas obliczania wybieranych kandydatów, w sytuacji, gdy część kandydatów została już uznana za wybranych, a nie ma już kandydatów spełniających warunek wymaganej standardowej ilości 'głosów', pozostali kandydaci musieliby zostać wybrani mniejszą ilością 'głosów', przez co byliby oni w mniejszym stopniu reprezentatywni niż ci poprzedni, i nie byłoby to też w pewnym sensie sprawiedliwe (szczególnie jeśli ci ostatni zostaliby wybrani bardzo małą ilością 'głosów').

Tę reprezentatywność można by wyrównać, jeśli zostałaby 'obniżona' jakość tamtego warunku. W takiej sytuacji można powtórzyć wykonanie obliczania kandydatów, przyjmując mniejszą wartość ilości wymaganych kandydatów (chodzi o parametr w wywołaniu "ObliczWynikGłosowania( IleGłosówWymag ) ;"). Taka metoda wyrównywałaby więc szanse kandydatów i ważność głosów różnych wyborców.

Jedna z modyfikacji podstawowego algorytmu polegałaby na obniżaniu ilości wymaganych kart na kandydata do takiej maksymalnej wartości, przy której uzyska się pełną ilość wymaganych kandydatów przy ustalonej stałej ilości 'głosów' na kandydata'. Podczas szukania tej wartości można użyć metody połówkowej (logarytmicznej) - maksymalna ilość wykonań obliczeń zestawów kandydatów dla kolejnych ilości wymaganych kart byłaby wtedy logarytmem dwójkowym ze standardowej ilości wymaganych głosów na kandydata (np. jeśli byłoby 60000 kart na kandydata, to wystarczyłoby 16 wywołań "ObliczWynikGłosowania").

Wartość ta stanowiłaby jakby ocenę stopnia reprezentatywności wyborów - np. gdyby wartość ta była większa niż połowa wartości standardowej, to wybory można by uznać za 'średnie' lub 'dobre' (wystarczająco reprezentatywne).

Trochę inna odmiana 'wyrównująca' algorytmu, polegałby na tym, że modyfikacja wyrównująca kandydatów aktywowana byłaby tylko wtedy, gdyby któryś kandydat miał zostać wybrany przez zbyt małą ilość 'głosów' (np. przez nie więcej niż połowę standardowej ilości głosów lub można by przyjąć jakąś większą ich część (np. 90%)).

Są możliwe dwie wersje obniżania ilości wymaganych kart na kandydata:

  • kandydaci wybrani z poprzednią (każdą lub tylko standardową) ilością wymaganych 'głosów' zostaliby przy mniejszej jej wartości 'przymusowo' uznani za wybranych;
  • algorytm działałby normalnie, ale wtedy niektórzy z wcześniej wybranym kandydatów (przy większej wymaganej ilości 'głosów') mogliby nie zostać wybrani, ponieważ wcześniej zostaliby wybrani inni (np. we wcześniejszym etapie, bo zostaliby wtedy uznani przez algorytm za lepszych (z powodu ich jakości, a nie ilości)).


Uwaga o wybieraniu większościowym:

Sytuacja ta, a więc gdy wybrany ma zostać tylko jeden kandydat, jest przypadkiem szczególnym (kartka wyborcza powinna być oczywiście taka sama). Przypadek ten też jest obejmowany przez powyższy algorytm.

Ideę tego algorytmu w przypadku wybierania 'większościowego' można jednak opisać też krócej: Zlicza się głosy kandydatów w kolejnych kolumnach (łącznie), aż któryś kandydat przekroczy połowę ilości głosujących;
lub inaczej wg:

  1. Wymagana ilość 'głosów' to: 1 + CzęśćCałkowita( IlośćKartWyborczych / 2 )
  2. Jako 'etap aktualny' ustala się 1 (czyli nr kolumny z krzyżykami).
  3. Zlicza się głosy kandydatów w kolumnach od 1. do aktualnej
  4. Sprawdza się, czy któryś kandydat osiągnął wymaganą ilość 'głosów':
    • jeśli tak, to za wybranego uznaje się tego, który tych głosów uzyskał najwięcej (a jeśli jest więcej takich, to ten, który ma przewagę w najwcześniejszej preferencji);
    • jeśli nie, to zwiększa się nr etapu (kolumny) o 1 i powraca się do p.3.



Zobacz: Preferencyjne systemy wyborcze
Zobacz: Kartka wyborcza ZGP


Strona główna


Comments