Przykładowo, metoda oparta na zaokrąglaniu programu liniowego daje współczynnik aproksymacji równy 0,7965. Przy standardowych założeniach teorii złożoności obliczeniowej jest to najlepszy współczynnik aproksymacji, który może zostać osiągnięty w czasie wielomianowym. Problem obliczania zwycięskich komitetów względem metody PGA możemy również sformułować jako problem minimalizacyjny (zamiast maksymalizować chcemy zminimalizować ). W tym przypadku najlepszy znany współczynnik aproksymacji wynosi 2,36.
Z punktu widzenia parametrycznej złożoności obliczeniowej, znajdowanie zwycięskich komitetów względem PGA jest (z pewnymi nielicznymi wyjątkami) trudne. Problem jest również NP-trudny, gdy preferencje wyborców odzwierciedlają ich pozycje w dwuwymiarowej przestrzeni poglądów ideologicznych. Problem jest obliczalny w czasie wielomianowym, gdy preferencje wyborców pochodzą z jednowymiarowej przestrzeni poglądów ideologicznych.
Pozostałe zastosowania PGA Metodę PGA można stosować również do bezpośredniego głosowania nad kilkoma niezależnymi uchwałami.
Powiązana literatura Książka opisująca metody wybierania komitetów, gdy wyborcy głosują przez aprobaty: Rozdział książki opisujący metody wybierania komitetów: Artykuł po polsku opisujący proporcjonalność metody PGA:
Powiązane pojęcia metoda D’Hondta metoda równych udziałów
Przypisy
Kategoria:Teoria systemów wyborczych