Working Paper Volební systémy pro volby do Poslanecké sněmovny Parlamentu ČR založené na matematickém programování

econstor

www.econstor.eu

Der Open-Access-Publikationsserver der ZBW – Leibniz-Informationszentrum Wirtschaft The Open Access Publication Server of the ZBW – Leibniz Information Centre for Economics

Doležel, Pavel

Working Paper

Volební systémy pro volby do Poslanecké sněmovny Parlamentu ČR založené na matematickém programování IES Working Paper, No. 31/2011 Provided in Cooperation with: Institute of Economic Studies (IES), Charles University

Suggested Citation: Doležel, Pavel (2011) : Volební systémy pro volby do Poslanecké sněmovny Parlamentu ČR založené na matematickém programování, IES Working Paper, No. 31/2011

This Version is available at: http://hdl.handle.net/10419/83467

Nutzungsbedingungen: Die ZBW räumt Ihnen als Nutzerin/Nutzer das unentgeltliche, räumlich unbeschränkte und zeitlich auf die Dauer des Schutzrechts beschränkte einfache Recht ein, das ausgewählte Werk im Rahmen der unter → http://www.econstor.eu/dspace/Nutzungsbedingungen nachzulesenden vollständigen Nutzungsbedingungen zu vervielfältigen, mit denen die Nutzerin/der Nutzer sich durch die erste Nutzung einverstanden erklärt.

zbw

Leibniz-Informationszentrum Wirtschaft Leibniz Information Centre for Economics

Terms of use: The ZBW grants you, the user, the non-exclusive right to use the selected work free of charge, territorially unrestricted and within the time limit of the term of the property rights according to the terms specified at → http://www.econstor.eu/dspace/Nutzungsbedingungen By the first use of the selected work the user agrees and declares to comply with these terms of use.

Institute of Economic Studies, Faculty of Social Sciences Charles University in Prague

Volební systémy pro volby do Poslanecké sněmovny Parlamentu ČR založené na matematickém programování Pavel Doležel

IES Working Paper: 31/2011

Institute of Economic Studies, Faculty of Social Sciences, Charles University in Prague [UK FSV – IES] Opletalova 26 CZ-110 00, Prague E-mail : [email protected] http://ies.fsv.cuni.cz

Institut ekonomických studií Fakulta sociálních věd Univerzita Karlova v Praze Opletalova 26 110 00 Praha 1 E-mail : [email protected] http://ies.fsv.cuni.cz

Disclaimer: The IES Working Papers is an online paper series for works by the faculty and students of the Institute of Economic Studies, Faculty of Social Sciences, Charles University in Prague, Czech Republic. The papers are peer reviewed, but they are not edited or formatted by the editors. The views expressed in documents served by this site do not reflect the views of the IES or any other Charles University Department. They are the sole property of the respective authors. Additional info at: [email protected] Copyright Notice: Although all documents published by the IES are provided without charge, they are licensed for personal, academic or educational use. All rights are reserved by the authors. Citations: All references to documents served by this site must be appropriately cited. Bibliographic information: Doležel, P. (2011). “Volební systémy pro volby do Poslanecké sněmovny Parlamentu ČR založené na matematickém programování” IES Working Paper 31/2011. IES FSV. Charles University. This paper can be downloaded at: http://ies.fsv.cuni.cz

Volební systémy pro volby do Poslanecké sněmovny Parlamentu ČR založené na matematickém programování

Pavel Doležel*

*IES, Charles University Prague E-mail: [email protected]

September 2011

Abstract: V článku navrhujeme tři metody přepočtu hlasů na mandáty pro volby do Poslanecké sněmovny Parlamentu ČR (PS PČR) založené na metodách matematického programování. Důvod pro jejich zavedení spatřujeme v tom, že běžně používané metody přepočtu hlasů na mandáty často vedou k podstatným odchylkám od dokonalé proporcionality a to nad rámec, který je dán uzavírací klauzulí. Ztráta proporcionality je přímým důsledkem nejen nutnosti alokovat politickým subjektům celé mandáty a nikoliv jejich části, ale také rozdělení voleb do volebních obvodů, v nichž probíhá přepočet hlasů na mandáty samostatně. Keywords: disproporcionalita, volební systém, uzavírací klauzule, volební obvod, Poslanecká sněmovna, celočíselné programování JEL: D71, D72 Acknowledgements Text vznikl za podpory grantu GAČR č. 402/09/1066: "Political economy of voting behavior, rational voters' theory and models of strategic voting."

1

´ Uvod a motivace

Pro pˇrepoˇcet hlas˚ u odevzdan´ ych ve volbách do Poslanecké snˇemovny Parlaˇ e republiky (dále jen PS PCR) ˇ mentu Cesk´ jednotliv´ ym kandiduj´ıc´ım politick´ ym subjekt˚ um na poslanecké mandáty, se dnes pouˇz´ıvá volebn´ı systém, kter´ y je dán volebn´ım zákonem (zákon 247/1995 Sb.). Teorie volebn´ıch systém˚ u zná celou ˇradu jin´ ych zp˚ usob˚ u pˇrepoˇctu hlas˚ u na mandáty, viz. napˇr´ıklad [Leb09]. Algoritmus, kter´ y kaˇzdému kandiduj´ıc´ımu politickému uskupen´ı pˇriˇrad´ı poslanecké mandáty na základˇe poˇctu hlas˚ u, které z´ıskalo ve volbách, budeme v tomto textu naz´ yvat metodou pˇrepoˇctu hlas˚ u na mandáty, nebo také volebn´ım systémem. Jednou z nejd˚ uleˇzitˇejˇs´ıch vlastnost´ı volebn´ıch systém˚ u je tzv. m´ıra proporcionality, která udává jak moc je rozdˇelen´ı voliˇcsk´ ych hlas˚ u pro jednotlivé politické subjekty v populaci voliˇc˚ u (kteˇr´ı platnˇe odevzdali sv˚ uj hlas) odliˇsné od fináln´ıho rozdˇelen´ı mandát˚ u mezi tyto subjekty. Vymezen´ı proporcionality a popis jej´ıho v´ yznamu pro studium volebn´ıch systém˚ u je moˇzné naj´ıt napˇr´ıklad v publikaci [Leb09]. Tomáˇs Lebeda ve své studii [Leb06] dokonce uvád´ı: ”M´ıra proporcionality je hlavn´ım a nejd˚ uleˇzitˇejˇs´ım kvantifikovateln´ ym jevem, kter´ y vypov´ıdá o politick´ ych konsekvenc´ıch volebn´ıho systému. Je ukazatelem zkreslen´ı reprezentace – ukazuje na nadreprezentaci, podreprezentaci ˇci nereprezentaci jednotliv´ ych stran – a znaˇcnˇe determinuje podobu stranického systému.”V této studii autor popisuje i snahu jin´ ych autor˚ u o setˇr´ıdˇen´ı volebn´ıch systém˚ u podle m´ıry proporcionality. ˇ asteˇcnˇe v opozici k proporcionalitˇe stoj´ı tzv. efektivita volebn´ıho C´ systému (viz. kupˇr´ıkladu [Col71]). Ta vyjadˇruje schopnost volebn´ıho systému ˇ efektivita vyjadˇruje produkovat zmˇeny statu quo. V pˇr´ıpadˇe PS PCR pravdˇepodobnost vytvoˇren´ı stabiln´ı a silné vlády. Je zˇrejmé, ˇze efektivita a proporcionalita jdou ˇcasto proti sobˇe, protoˇze vysoká m´ıra proporcionality vˇetˇsinou vede k tomu, ˇze mandáty z´ıská velké mnoˇzstv´ı vzájemnˇe nesourod´ ych a nekompatibiln´ıch politick´ ych subjekt˚ u, které se obt´ıˇznˇe dokáˇz´ı dohodnout na u ´ˇcasti ve spoleˇcné vládn´ı koalici a kdyˇz uˇz se dohodnou, b´ yvaj´ı takové koalice sp´ıˇse nestabiln´ı. Pro dosaˇzen´ı rozumné m´ıry efektivity se pouˇz´ıvaj´ı mimojiné tzv. uzav´ırac´ı klauzule, které umoˇzn ˇuj´ı (nikoliv zaruˇcuj´ı) zisk mandátu pouze tˇem stranám, které na celostátn´ı u ´rovni dosáhnou alespoˇ n nˇejakého pˇredem pevnˇe daného pod´ılu poˇctu platn´ ych hlas˚ u. Ve volbách ˇ do PS PCR je uzav´ırac´ı klauzule na u ´rovni 5%. ˇ je jejich rozdˇelen´ı do voDalˇs´ı velmi d˚ uleˇzitou vlastnost´ı voleb do PS PCR lebn´ıch obvod˚ u, pˇriˇcemˇz podle stávaj´ıc´ıho volebn´ıho systému se nejprve aplikuje uzav´ırac´ı klauzule na celostátn´ı u ´rovni, poté prob´ıhá pˇrepoˇcet mandát˚ u na tyto obvody a teprve poté v kaˇzdém obvodu zvláˇst’ prob´ıhá pˇrepoˇcet 1

mandát˚ u na jednotlivé kandiduj´ıc´ı politické subjekty. D˚ uvod˚ u pro zaveden´ı volebn´ıch obvod˚ u je hned nˇekolik. Jednak umoˇzn ˇuj´ı provázanost konkrétn´ıch mandát˚ u s konkrétn´ımi menˇs´ımi u ´zemn´ımi celky, jednak vedou ke spravedlivˇejˇs´ı u ´zemn´ı distribuci mandát˚ u a jednak také usnadˇ nuj´ı a zlevˇ nuj´ı volebn´ı kampanˇe. Bez zaveden´ı volebn´ıch obvod˚ u by mohlo doj´ıt k situaci, kdy by drtivá vˇetˇsina poslanc˚ u byla z nˇekolika velk´ ych mˇest a proto jejich ochota zab´ yvat se regionáln´ımi problémy by byla n´ızká. Volebn´ı obvody se pouˇz´ıvaj´ı ve volbách bˇeˇznˇe v celém svˇetˇe a nav´ıc hraj´ı svoji nezastupitelnou u ´lohu ve volbách do nadnárodn´ıch instituc´ı, jako je Evropská Unie, nebo i do federáln´ıch instituc´ı, jako je kupˇr´ıkladu House of Representatives ve Spojen´ ych státech. V tˇechto instituc´ıch je prakticky nemyslitelné ideu volebn´ıch obvod˚ u u ´plnˇe opustit a to nejen z historick´ ych d˚ uvod˚ u. Sm´ıˇr´ıme-li se s uzav´ırac´ı klauzul´ı jakoˇzto mechanismem omezuj´ıc´ım neefektivitu volebn´ıho systému a sm´ıˇr´ıme-li se i s rozdˇelen´ım voleb do jednotliv´ ych volebn´ıch obvod˚ u, v nichˇz prob´ıhá pˇrepoˇcet hlas˚ u na mandáty oddˇelenˇe, vzniká otázka, zda pouˇzitá metoda pˇrepoˇctu hlas˚ u na mandáty v jednotliv´ ych volebn´ıch obvodech nevytváˇr´ı sama o sobˇe dodateˇcné odch´ ylen´ı od dokonalé proporcionality. A právˇe toto dodateˇcné odch´ ylen´ı se budeme snaˇzit minimalizovat zaveden´ım nov´ ych zp˚ usob˚ u pˇrepoˇctu hlas˚ u na mandáty, ´ celem tˇechto návrh˚ které vyuˇz´ıvaj´ı metod matematického programován´ı. Uˇ u je minimalizovat odch´ ylen´ı od dokonalé proporcionality pˇri rozdˇelen´ı na volebn´ı obvody a pˇri nenulové uzav´ırac´ı klauzuli. V´ yhodou tˇechto návrh˚ u je jejich obecná pouˇzitelnost (lze je prakticky pouze se zmˇenou parametr˚ u aplikovat okamˇzitˇe i na jiné volby vyuˇz´ıvaj´ıc´ı volebn´ı obvody, neˇz jsou volby do ˇ PS PCR). Nev´ yhodou tˇechto návrh˚ u je jejich relativn´ı technická nároˇcnost a nutnost pouˇzit´ı poˇc´ıtaˇce. Veˇskeré algoritmy, které jsme v práci pouˇzili jsou zapsány v jazyku VBA (Visual Basic for Applications) a vytvoˇrili jsme je sami v programu MicrosoftrExcel. Nyn´ı zaved’me základn´ı znaˇcen´ı, které budeme v práci pouˇz´ıvat. Poˇcet vˇsech platn´ ych hlas˚ u odevzdan´ ych ve volbách oznaˇcme v 0 a poˇcet vˇsech obˇ je m = 200). sazovan´ ych mandát˚ u oznaˇcme m (v pˇr´ıpadˇe voleb do PS PCR Pˇredpokládáme, ˇze m < v 0 . Oznaˇcme P 0 poˇcet vˇsech ve volbách kandiduj´ıc´ıch politick´ ych subjekt˚ u a R poˇcet vˇsech volebn´ıch obvod˚ u (v pˇr´ıpadˇe voleb do ˇ PS PCR od roku 2002 jsou volebn´ımi obvody samosprávné kraje a tedy ˇ e národn´ı rady a voleb do PS PCR ˇ do R = 14, v pˇr´ıpadˇe voleb do Cesk´ roku 1998 je volebn´ıch obvod˚ u osm, tedy R = 8). Mnoˇzinu vˇsech kandiduj´ıc´ıch politick´ ych subjekt˚ u oznaˇcme P 0 a tuto mnoˇzinu pevnˇe uspoˇrádejme sestupnˇe podle poˇctu obdrˇzen´ ych hlas˚ u tak, ˇze indexem i0 ∈ {1, . . . , P 0 } bude pevnˇe oznaˇcen právˇe jeden z kandiduj´ıc´ıch politick´ ych subjekt˚ u. Oznaˇcme p0i0 0 poˇcet platn´ ych odevzdan´ ych hlas˚ u pro politick´ y subjekt i a to pro vˇsechna i0 = 1, . . . , P 0 . Mnoˇzinu vˇsech volebn´ıch obvod˚ u pevnˇe uspoˇra´dáme sestupnˇe 2

podle poˇctu odevzdan´ ych platn´ ych hlas˚ u tak, ˇze indexem j ∈ {1, . . . , R} je pevnˇe oznaˇcen právˇe jeden volebn´ı obvod. Poˇcet platn´ ych hlas˚ u odevzdan´ ych 0 0 0 stranˇe i ve volebn´ım obvodu j oznaˇcme vi0 j , pro vˇsechna i = 1, . . . , P 0 a vˇsechna j = 1, . . . , R. Uzav´ırac´ı klauzuli oznaˇcme 0 < u < 1.

3

2

M´ıry disproporcionality

Protoˇze naˇs´ı hlavn´ı motivac´ı je minimalizovat v nˇejakém smyslu odch´ ylen´ı od dokonalé proporcionality, mus´ıme nejprve definovat m´ıry tohoto odch´ ylen´ı. S jejich pomoc´ı budeme navrˇzené systémy porovnávat s ostatn´ımi metodami pˇrepoˇctu hlas˚ u na mandáty. M´ıru odch´ ylen´ı konkrétn´ıho v´ ysledku voleb od teoretického v´ ysledku pˇri dokonalé proporcionalitˇe budeme mˇeˇrit prostˇrednictv´ım tˇr´ı základn´ıch mˇer: (1), (2) a (3). P X R X m 2 ρ= mij − vij , (1) v i=1 j=1 P X R X m mij − vij , v i=1 j=1 2 P X R X mij − mv vij ξ= , m v ij v i=1 j=1

φ=

(2)

(3)

kde m je celkov´ y poˇcet mandát˚ u, v je celkov´ y poˇcet platn´ ych hlas˚ u odevzdan´ ych politick´ ym subjekt˚ um, P je poˇcet kandiduj´ıc´ıch politick´ ych subjekt˚ u, R je poˇcet volebn´ıch obvod˚ u, mij je poˇcet mandát˚ u alokovan´ ych politickému subjektu i ve volebn´ım obvodu j a vij je poˇcet platn´ ych hlas˚ u pro politick´ y subjekt i odevzdan´ ych ve volebn´ım obvodu j.1 M´ıry ρ, φ a ξ jsou formálnˇe funkcemi dvou matic - matice poˇct˚ u mandát˚ u z´ıskan´ ych jednotliv´ ymi stranami v jednotliv´ ych volebn´ıch obvodech M a matice poˇctu hlas˚ u z´ıskan´ ych jednotliv´ ymi stranami v jednotliv´ ych volebn´ıch obvodech V . Budeme-li mˇeˇrit odch´ ylen´ı vektoru mandát˚ u alokovan´ ych politick´ ym subjekt˚ um na celostátn´ı u ´rovni, resp. volebn´ım obvod˚ um pˇres vˇsechny politické subjekty, které proˇsly pˇres uzav´ırac´ı klauzuli, od dokonalé proporcionality pomoc´ı tˇr´ı navrˇzen´ ych mˇer, poloˇz´ıme v jejich definici jednoduˇse R = 1, resp. P = 1. Uvedené m´ıry jsou ˇcasto pouˇz´ıvan´ ymi m´ırami disproporcionality, ale ani zdaleka ne jedin´ ymi. M´ıra ρ je rostouc´ı transformac´ı tzv. Gallagherova indexu, viz. [Gal91], m´ıra ψ je rostouc´ı transformac´ı tzv. Loosemore-Hanbyho 1

Protoˇze pˇredmˇetem naˇseho zkoumán´ı nen´ı nastaven´ı uzav´ırac´ı klauzule, nebudeme disproporcionalitu mˇeˇrit u vˇsech kandiduj´ıc´ıch subjekt˚ u, ale jen u tˇech, které proˇsly pˇres uzav´ırac´ı klauzuli. Proto je znaˇcen´ı uzp˚ usobeno znaˇcen´ı, které zavád´ıme pozdˇeji pro politické subjekty, které proˇsly pˇres uzav´ırac´ı klauzuli. Porovnán´ı volebn´ıch systém˚ u z hlediska m´ıry disproporcionality pˇri stejné uzav´ırac´ı klauzuli t´ım nen´ı dotˇceno, nebot’ subjekty, které neproˇsly pˇres uzav´ırac´ı klauzuli, nemaj´ı alokován ˇzádn´ y mandát a tedy ”jejich pˇr´ınos”do celkové m´ıry disproporcionality je pro vˇsechny volebn´ı systémy se stejnou uzav´ırac´ı klauzul´ı stejn´ y.

4

indexu, viz. [JL71] a m´ıra ξ je rostouc´ı transformac´ı tzv. Sainte-Lagu¨ e indexu, viz. [Kar08]. Mˇer proporcionality je definována celá ˇrada2 . Jak je uvedeno v ˇclánku [Gal91], kaˇzdá metoda pˇrepoˇctu hlas˚ u na mandáty minimalizuje disproporcionalitu vzhledem k nˇejaké m´ıˇre, kterou si sama vol´ı. Nen´ı tedy moˇzné prohlásit jednu metodu pˇrepoˇctu hlas˚ u na mandáty za obecnˇe nejlepˇs´ı z pohledu proporcionality, protoˇze zp˚ usob ovˇeˇren´ı podléhá normativn´ımu v´ ybˇeru jej´ı m´ıry. Pˇresto existuj´ı ˇclánky zab´ yvaj´ıc´ı se porovnáván´ım jednotliv´ ych metod z hlediska proporcionality mezi sebou, viz. kupˇr´ıkladu [Ben00], [Pen98], [Leb09]. V tomto ˇclánku nám ale nejde o to, naj´ıt nejlepˇs´ı m´ıru disproporcionality, n´ ybrˇz o to, jak za pˇredpokladu, ˇze jiˇz byla zvolena, zajistit minimáln´ı disproporcionalitu u voleb rozdˇelen´ ych do volebn´ıch obvod˚ u a obsahuj´ıc´ıch nenulovou uzav´ırac´ı klauzuli. To je oblast, která v nám známé odborné literatuˇre zat´ım chyb´ı. Nav´ıc z naˇsich v´ ysledk˚ u je zˇrejmé, ˇze námi navrhované metody ˇcasto dosahuj´ı ”proporˇcnˇejˇs´ıch”v´ ysledk˚ u neˇz ostatn´ı volebn´ı systémy z hlediska vˇsech tˇr´ı zaveden´ ych mˇer disproporcionality.

3

Obecn´ e pˇ redpoklady pouˇ zitelnosti algoritm˚ u pro pˇ repoˇ cet hlas˚ u na mand´ aty

Aby volebn´ı systém mohl b´ yt pouˇzit ve skuteˇcn´ ych volbách, povaˇzujeme za nutné, aby splˇ noval následuj´ıc´ı tˇri vlastnosti: 1. Determinismus - aby byl deterministick´ y, tj. aby neobsahoval prvky náhody a tud´ıˇz aby pˇri opˇetovné aplikaci na stejné volby dal vˇzdy tent´ yˇz v´ ysledek. 2. Nezápornost ˇreˇsen´ı - aby vˇzdy dospˇel k takové alokaci, která ˇza´dnému z kandiduj´ıc´ıch subjekt˚ u v ˇza´dném z volebn´ıch obvod˚ u nealokuje záporn´ y poˇcet mandát˚ u. 3. Rychlost - aby vˇzdy dospˇel k ˇreˇsen´ı v rozumném, tj. polynomiáln´ım ˇcase. Samotn´ ym navrˇzen´ım volebn´ıho systému tedy naˇse u ´sil´ı nekonˇc´ı. Mus´ıme také ovˇeˇrit, zda kaˇzd´ y z navrhovan´ ych algoritm˚ u má vˇsechny tyto tˇri vlastnosti. Pokud ne, nem˚ uˇze b´ yt v praxi pouˇzit. 2

Rae˚ uv index, Monroe˚ uv index, Giniho index, Farina index, Borooah˚ uv index, Grofman˚ uv index, Lijphart˚ uv index, Gatev˚ uv index, Ryabtsev˚ uv index, Szalai˚ uv index, Aleskerov-Platonov˚ uv index, Atkinson˚ uv index, index zobecnˇené entropie a d’Hondt˚ uv index jsou uvedeny v ˇcl´ anku [Kar08], kde jsou také popsány jejich základn´ı vlastnosti. Mˇeˇren´ı proporcionality je podrobeno detailn´ımu zkoumán´ı v knize [dCMP+ 87].

5

4 4.1

Alokaˇ cn´ı algoritmus Ψ Popis algoritmu

Ve vˇsech zavádˇen´ ych metodách pˇrepoˇctu hlas˚ u na mandáty popsan´ ych v dalˇs´ıch ˇca´stech textu, budeme vyuˇz´ıvat alokaˇcn´ıho algoritmu, kter´ y vede k pˇriˇrazen´ı poˇctu mandát˚ u jednotliv´ ym volebn´ım obvod˚ um, resp. jednotliv´ ym kandiduj´ıc´ım politick´ ym subjekt˚ um, které proˇsly pˇres uzav´ırac´ı klauzuli. Tento algoritmus vede k ˇreˇsen´ı následuj´ıc´ı u ´lohy celoˇc´ıselného programován´ı v pˇr´ıpadˇe mˇeˇren´ı disproporcionality pomoc´ı m´ıry ρ: min

PP

i=1

mi , i=1,...,P

za podm´ınek

PP

i=1

mi −

2 m p v i (4)

mi = m

mi ∈ N0

i = 1, . . . , P,

kde P je poˇcet kandiduj´ıc´ıch politick´ ych subjekt˚ u, které proˇsly pˇres uzav´ırac´ı klauzuli, pi je celkov´ y poˇcet odevzdan´ ych platn´ ych hlas˚ u pro kandiduj´ıc´ı politick´ y subjekt i, kter´ y proˇsel pˇres uzav´ırac´ı klauzuli, v je celkov´ y poˇcet platn´ ych odevzdan´ ych hlas˚ u ve volbách pro politické subjekty, které proˇsly pˇres uzav´ırac´ı klauzuli a m je celkov´ y poˇcet mandát˚ u. Obdobnˇe algoritmus Ψ pouˇzijeme i na u ´lohu PR

min

j=1

mj −

2 m r j v

mj , j=1,...,R

za podm´ınek

PR

j=1

(5)

mj = m

mj ∈ N0

j = 1, . . . , R,

kde R je poˇcet volebn´ıch obvod˚ u, rj je celkov´ y poˇcet platn´ ych hlas˚ u odevzdan´ ych ve volebn´ım obvodu j politick´ ym subjekt˚ um, které proˇsly pˇres uzav´ırac´ı klauzuli, v je celkov´ y poˇcet platn´ ych odevzdan´ ych hlas˚ u politick´ ym subjekt˚ um, které proˇsly pˇres uzav´ırac´ı klauzuli a m je celkov´ y poˇcet mandát˚ u. Obˇe u ´lohy (4) i (5) maj´ı vˇzdy optimáln´ı ˇreˇsen´ı, které je nezáporné i s podm´ınkou mi ∈ Z m´ısto podm´ınky mi ∈ N0 , protoˇze m > 0. V pˇr´ıpadˇe mˇeˇren´ı disproporcionality pomoc´ı m´ıry ψ máme tytéˇz u ´lohy, ale s u ´ˇcelovou funkc´ı P X m m i − pi , v i=1 6

resp. R X m mj − rj v j=1

a v pˇr´ıpadˇe mˇeˇren´ı disproporcionality pomoc´ı m´ıry ξ s u ´ˇcelovou funkc´ı 2 P X mi − mv pi , m p i v i=1 resp. R X mj − j=1

2 m r v j

m r v j

.

Necht’ Q ∈ N. Alokaˇcn´ı algoritmus Ψ má následuj´ıc´ı kroky: 1. Pˇriˇrad´ıme mi := m pro vˇsechna i = 1, . . . , Q. 2. Pro kaˇzdé i = 1, . . . , Q spoˇc´ıtáme 2 m m − v , pˇri minimalizaci m´ıry ρ i i v mi − m vi , pˇri minimalizaci m´ıry ψ v 2 m (mi − v vi ) , pˇri minimalizaci m´ıry ξ. m vi v

3. Ze vˇsech hodnot z´ıskan´ ych v kroku 2 takov´ ych, ˇze mi > m vvi najdeme argument maxima, tj. najdeme nejmenˇs´ı index i∗ , pro kter´ y plat´ı vi∗ 2 vi 2 mi∗ − m ≥ mi − m , v v pro vˇsechna i = 1, . . . , Q pˇri minimalizaci m´ıry ρ, vi∗ vi mi∗ − m ≥ mi − m , v v pro vˇsechna i = 1, . . . , Q pˇri minimalizaci m´ıry ψ a mi∗ − 12 mi − 12 ≥ , vi∗ vi pro vˇsechna i = 1, . . . , Q pˇri minimalizaci m´ıry ξ. 4. Poloˇz´ıme mi∗ := mi∗ − 1. PQ 5. Pokud = m, pak algoritmus konˇc´ı alokac´ı mandát˚ u i=1 mi PQ (m1 , . . . , mQ ) . Pokud i=1 mi > m, pak jdeme zpˇet na krok 2. Pˇri alokaci mandát˚ u na kraje poloˇz´ıme Q := R a za vj dosad´ıme pro vˇsechna j = 1, . . . , R hodnoty rj a pˇri alokaci mandát˚ u na politické subjekty poloˇz´ıme Q := P a za vi dosad´ıme pi pro vˇsechna i = 1, . . . , P. 7

4.2

D˚ ukaz optimality nalezen´ eho ˇ reˇ sen´ı

Dokaˇzme nyn´ı, ˇze algoritmus Ψ najde pˇri minimalizaci m´ıry ρ optimáln´ı ˇreˇsen´ı u ´lohy (4), resp. u ´lohy (5). D˚ ukaz provedeme sporem. Oznaˇcme x∗ ˇreˇsen´ı nalezené prostˇrednictv´ım algoritmu Ψ. Necht’ tedy toto ˇreˇsen´ı nen´ı optimáln´ım ˇreˇsen´ım u ´lohy (4), resp. u ´lohy (5). Mus´ı tedy existovat zp˚ usob, jak sn´ıˇzit ∗ hodnotu u ´ˇcelové funkce. x je pˇr´ıpustn´ ym ˇreˇsen´ım u ´lohy, protoˇze algoritmus Ψ skonˇc´ı pouze tehdy, kdyˇz je splnˇena podm´ınka na celkov´ y souˇcet. Mus´ı tedy existovat nˇejaká dvojice index˚ u i a j takové, ˇze 1 ≤ i 6= j ≤ P, pro nˇeˇz plat´ı vj 2 ∗ vi 2 ∗ vj 2 vi 2 ∗ + xj − 1 − m < xi − m + xj − m (6) x∗i + 1 − m v v v v vi vj ⇔ x∗i + 1 − m < x∗j − m , v v Nyn´ı proberme zvláˇst’ dva pˇr´ıpady. v • Je-li x∗i + 1 − m vvi > 0, pak podle (6) je i x∗j − m vj > 0 a v kroku 3 algoritmu Ψ muselo pˇri bˇehu nˇekdy doj´ıt k porovnán´ı hodnot vj 2 vi 2 ∗ ∗ a xj − m xi + 1 − m v v a jako maximum musela b´ yt vybrána hodnota vi 2 , x∗i + 1 − m v protoˇze jinak by nemohlo b´ yt x∗i + 1 sn´ıˇzeno o jedniˇcku na hodnotu x∗i , aniˇz by pˇred t´ım nedoˇslo ke sn´ıˇzen´ı hodnoty x∗j na hodnotu x∗j − 1. Mus´ı tedy platit alespoˇ n neostrá nerovnost vi 2 ∗ vj 2 ∗ xi + 1 − m ≥ xj − m , v v coˇz je ovˇsem ve sporu s (6). • Situace, kdy

x∗i + 1 − m

vi ≤ 0, v

nem˚ uˇze nastat, protoˇze pak mus´ı b´ yt vi x∗i − m <0 v a ke sn´ıˇzen´ı z hodnoty x∗i +1 na hodnotu x∗i nemohlo nikdy doj´ıt, nebot’ v kroku 3 algoritmu Ψ vyb´ıráme argument maxima jen z takov´ ych prvk˚ u, pro nˇeˇz plat´ı vi xi − m > 0. v 8

Zjistili jsme tedy, ˇze ˇzádná dvojice index˚ u i a j taková, ˇze pro nˇe plat´ı (6) neexistuje a tud´ıˇz neexistuje moˇznost, jak sn´ıˇzit hodnotu u ´ˇcelové funkce. ∗ ˇ Reˇsen´ı x je tedy nejen pˇr´ıpustn´ ym ˇreˇsen´ım nalezen´ ym algoritmem Ψ pˇri minimalizaci m´ıry ρ, ale také optimáln´ım ˇreˇsen´ım u ´lohy (4), resp. (5) pˇri u ´ˇcelové funkci dané m´ırou ρ. Dokaˇzme dále, ˇze algoritmus Ψ najde optimáln´ı ˇreˇsen´ı u ´lohy (4), resp. u ´lohy (5) i pˇri minimalizaci m´ıry φ. Budeme postupovat opˇet sporem, pˇredpokládaje, ˇze x∗ je ˇreˇsen´ım nalezen´ ym algoritmem Ψ, pˇri minimalizaci m´ıry φ, ale nen´ı ˇreˇsen´ım optimáln´ım. Vyjdeme z analogie k (6). vj ∗ vi ∗ vj vi ∗ ∗ xi + 1 − m + xj − 1 − m < xi − m + xj − m v v v v

(7)

v

Pro jednoduchost nyn´ı oznaˇcme A := x∗i − m vvi a B := x∗j − m vj . Existuje 9 moˇznost´ı: 1. 2. 3. 4. 5. 6. 7. 8. 9.

A A < −1 A < −1 A < −1 −1 ≤ A < 0 −1 ≤ A < 0 −1 ≤ A < 0 A≥0 A≥0 A≥0

B |A + 1| + |B − 1| < |A| + |B| B<0 0<0 0≤B<1 −B < B B≥1 −2 < 0 B<0 A < −1 0≤B<1 A+1
kdy plat´ı? nikdy kdyˇz 0 < B vˇzdy nikdy kdyˇz A + 1 < B vˇzdy nikdy nikdy nikdy

Tabulka 1: Seznam vˇsech moˇznost´ı, které mohou nastat Podm´ınka (7) plat´ı tehdy a jen tehdy, pokud nastává jedna ze situac´ı z bod˚ u 2, 3, 5, nebo 6 tabulky 1. V´ıme ale, ˇze A < −1 nem˚ uˇze nastat, jelikoˇz vi ∗ xi − m v > −1. To plyne z kroku 3 algoritmu Ψ, v nˇemˇz vyb´ıráme maximum pouze z tˇech hodnot xi , pro které plat´ı xi −m vvi > 0 a pouze od nich odeˇc´ıtáme v kroku 4 jedniˇcku. Nem˚ uˇzeme se tedy nikdy dostat k x∗i − m vvi ≤ −1. Body 2 a 3 tedy nenastanou a zb´ yvá ukázat, ˇze bod 5 i bod 6 vedou ke sporu. Bod 5 znamená (viz prvn´ı tˇri sloupce ˇrádku 5. tabulky 1), ˇze plat´ı zároveˇ n vj vj vi vi ∗ ∗ ∗ ∗ −1 ≤ xi − m v < 0, 0 ≤ xj − m v < 1 a xi + 1 − m v < xj − m v . Algoritmus Ψ musel v nˇekter´ u stát pˇred porovn´ ∗ em z krok˚ an´ım hodnot xi + 1 − m vi a x∗j − m vj a jako vˇetˇs´ı vybral hodnotu x∗i + 1 − m vi , v v v protoˇze jinak by musel pˇred sn´ıˇzen´ım hodnoty x∗i + 1 o jedniˇcku na hod∗ notu ıˇzit hodnotu x∗j o jedniˇ i sn´ cku a k tomu nedoˇslo. Proto tedy mus´ı pla x vj vi ∗ ∗ tit xi + 1 − m v ≥ xj − m v . Dostáváme tedy vzhledem k nezápornosti 9

v

x∗i + 1 − m vvi a nezápornosti x∗j − m vj nerovnost x∗i + 1 − m vvi ≥ x∗j − m vvi , v která je ve sporu s x∗i + 1 − m vvi < x∗j − m vj . Situace popsaná v bodu 5 tedy také nem˚ uˇze nastat. Bod 6 znamená (viz prvn´ı dva sloupce ˇra´dku 6. tabulky 1), ˇze plat´ı 0 ≤ v ∗ xi + 1 − m vvi < 1 a x∗j − m vj ≥ 1. Ze stejného d˚ uvodu, jako v bodu 5 mus´ı ale platit vj vi ∗ ∗ xi + 1 − m ≥ xj − m . v v Protoˇze absolutn´ı hodnoty jsou zde aplikovány na nezáporná ˇc´ısla, lze je vynechat a dostáváme 1 > x∗i + 1 − m

vi vj ≥ x∗j − m ≥ 1, v v

coˇz je totéˇz jako 1 > 1. Situace z bodu 6 tedy rovnˇeˇz nenastane. T´ım se vˇsak dostáváme do sporu s pˇredpokladem, ˇze x∗ nen´ı optimáln´ım ˇreˇsen´ım u ´lohy (4), resp. u ´lohy (4) pˇri minimalizaci m´ıry φ. Zb´ yvá dokázat, ˇze algoritmus Ψ najde optimáln´ı ˇreˇsen´ı u ´lohy (4), resp. u ´lohy (5) i pˇri minimalizaci m´ıry ξ. Budeme postupovat opˇet sporem, pˇredpokládaje, ˇze x∗ je ˇreˇsen´ım nalezen´ ym algoritmem Ψ pˇri minimalizaci m´ıry ξ, ale nen´ı ˇreˇsen´ım optimáln´ım. Vyjdeme z analogie k (6).

x∗i + 1 − m vvi m vvi

2

v

x∗j − 1 − m vj + m vvi

2

x∗i − m vvi < v m vj

2

v

x∗j − m vj + v m vj

x∗i + ⇔ vi

1 2

2

x∗j − < vj

(8) 1 2

V nˇekterém okamˇziku bˇehu algoritmu Ψ ale muselo doj´ıt k porovnán´ı x∗ − 1 x∗ + 1 x∗ + 1 hodnot ivi 2 a jvj 2 a jako maximum byla vybrána hodnota ivi 2 . Tud´ıˇz x∗i + vi

1 2

≥

x∗j − 12 , vj

ˇ adná dvojice index˚ coˇz je ve sporu s (8). Z´ u i a j taková, ˇze pro nˇe plat´ı (8) neexistuje a tud´ıˇz neexistuje moˇznost, jak sn´ıˇzit hodnotu u ´ˇcelové funkce. ∗ ˇ Reˇsen´ı x je tedy nejen ˇreˇsen´ım nalezen´ ym algoritmem Ψ pˇri minimalizaci m´ıry ξ, ale také ˇreˇsen´ım optimáln´ım pˇri u ´ˇcelové funkci dané m´ırou ξ. 10

Alokaˇ cn´ı algoritmus Ψ•

5 5.1

Popis algoritmu

Vytvoˇr´ıme algoritmus, kter´ y povede k pˇriˇrazen´ı poˇctu mandát˚ u jednotliv´ ym kandiduj´ıc´ım politick´ ym subjekt˚ um v jednotliv´ ych volebn´ıch obvodech. Tento alokaˇcn´ı algoritmus je zobecnˇen´ım alokaˇcn´ıho algoritmu Ψ a budeme jej vyuˇz´ıvat k nalezen´ı nebo alespoˇ n odhadu optimáln´ıho ˇreˇsen´ı následuj´ıc´ı obecné u ´lohy celoˇc´ıselného programován´ı: PP PR min vij 2 i=1 j=1 mij − m v xij , i=1,...,P , j=1,...,R za podm´ınek

PP

i=1

PR

j=1

mij = Lj

j = 1, . . . , R,

(9)

mij = Mi i = 1, . . . , P,

mij ∈ N0

i = 1, . . . , P , j = 1, . . . , R,

kde P je poˇcet kandiduj´ıc´ıch politick´ ych subjekt˚ u, které proˇsly pˇres uzav´ırac´ı klauzuli, R je poˇcet volebn´ıch obvod˚ u, v je celkov´ y poˇcet platn´ ych odevzdan´ ych hlas˚ u ve volbách pro politické subjekty, které proˇsly pˇres uzav´ırac´ı klauzuli, m je celkov´ y poˇcet mandát˚ u, Lj , j = 1, . . . , R a Mi , i = 1, . . . , P PP jsou pˇrirozená ˇc´ısla pro nˇeˇz plat´ı podm´ınka vyváˇzenosti m = i=1 Mi = PR ´lohu s omezen´ımi, které odpov´ıdaj´ı vyváˇzenému dopravn´ımu j=1 Lj . Jde o u problému. Pokud bychom tedy mˇeli lineárn´ı u ´ˇcelovou funkci, pak bychom dostali vyváˇzen´ y dopravn´ı problém, kter´ y by mˇel automaticky celoˇc´ıselné ˇreˇsen´ı a kter´ y by bylo moˇzné ˇreˇsit v polynomiáln´ım ˇcase tˇreba pomoc´ı elipsoidové metody. Naˇse u ´ˇcelová funkce ale lineárn´ı nen´ı. Pro jednoduˇsˇs´ı formáln´ı zápis krok˚ u algoritmu oznaˇcme nyn´ı F = {1, . . . , P } × {1, . . . , R} . Alokaˇcn´ı algoritmus má následuj´ıc´ı kroky: 1. Pˇriˇrad´ıme mij := m pro vˇsechna i = 1, . . . , P, a vˇsechna j = 1, . . . , R. 2. Pro kaˇzdou uspoˇra´danou dvojici index˚ u (i, j) vij 2 mij − m v .

∈

F spoˇc´ıtáme

3. Najdeme takovou uspoˇra´danou dvojici index˚ u (i∗ , j ∗ ) pro n´ıˇz plat´ı vi ∗ j ∗ mi∗ j ∗ > m v a

m

i∗ j ∗

vi∗ j ∗ 2 vij 2 −m ≥ mij − m , v v 11

pro vˇsechna (i, j) ∈ F taková, ˇze mij > m m´ıry ρ,

vij v

v pˇr´ıpadˇe minimalizace

vi∗ j ∗ vij ∗ ∗ mi j − m ≥ mij − m , v v pro vˇsechna (i, j) ∈ F taková, ˇze mij > m m´ıry φ a mi∗ j ∗ − v∗ ∗ m i vj

1 2

vij v

v pˇr´ıpadˇe minimalizace

mij − 12 ≥ , v m vij v

pro vˇsechna (i, j) ∈ F taková, ˇze mij > m vij v pˇr´ıpadˇe minimalizace m´ıry ξ. Pokud je takov´ ych uspoˇra´dan´ ych dvojic v´ıce, vybereme tu s ∗ nejniˇzˇs´ım indexem i a pokud i takov´ ych dvojic je v´ıce, vybereme tu s nejniˇzˇs´ım indexem j ∗ . 4. Poloˇz´ıme mi∗ j ∗ := mi∗ j ∗ − 1. P P 5. Pokud Pi=1 Pj=1 mij = m, pak pˇrejdeme na krok 6, jinak se vrát´ıme na krok 2. o n PR 6. Definujme mnoˇzinu Ω := i ∈ {1, . . . , P } : j=1 mij > Mi , mnoˇzinu o n P Φ := j ∈ {1, . . . , R} : Pi=1 mij > Lj a mnoˇzinu ∆ := Ω × Φ. Pokud Ω = ∅, pak jdeme na krok 8. 7. Poloˇz´ıme 0

0

(i , j ) := arg min

(i,j)∈∆

vij 2 vij 2 mij − 1 − m − mij − m v v

pro m´ıru ρ, n vij vij o m − 1 − m − m − m ij ij (i,j)∈∆ v v

(i0 , j 0 ) := arg min pro m´ıru φ a 0

0

(i , j ) := arg max (i,j)∈∆

mij v vij m

pro m´ıru ξ. Dále poloˇz´ıme mi0 j 0 := mi0 j 0 − 1 a vrát´ıme se na krok 6. 12

n o P 8. Definujme mnoˇzinu Λ := i ∈ {1, . . . , P } : R m < M zinu ij i , mnoˇ j=1 n o P Ξ := j ∈ {1, . . . , R} : Pi=1 mij < Lj a mnoˇzinu Θ := Λ × Ξ. Pokud Λ = ∅, pak algoritmus konˇc´ı alokac´ı mij mandát˚ u subjektu i ve volebn´ım obvodu j pro vˇsechna i ∈ {1, . . . , P } a vˇsechna j ∈ {1, . . . , R} . 9. Poloˇz´ıme 0

0

(i , j ) := arg min

(i,j)∈Θ

vij 2 vij 2 − mij − m mij + 1 − m v v

pro m´ıru ρ n vij vij o (i , j ) := arg min mij + 1 − m − mij − m (i,j)∈Θ v v pro m´ıru φ 0

0

0

0

(i , j ) := arg min (i,j)∈Θ

mij v vij m

pro m´ıru ξ. Dále poloˇz´ıme mi0 j 0 := mi0 j 0 + 1 a vrát´ıme se na krok 8. Tento algoritmus najde ale pouze suboptimáln´ı ˇreˇsen´ı a nav´ıc nikoli nutnˇe nezáporné. Proto jej dopln´ıme jeˇstˇe iteraˇcn´ım algoritmem, kter´ y, jak si pozdˇeji dokáˇzeme, vede k ˇreˇsen´ı optimáln´ımu, za pˇredpokladu, ˇze je toto ˇreˇsen´ı nezáporné. Tento iteraˇcn´ı algoritmus je zaloˇzen na myˇslence tzv. εzmˇeny. Celoˇc´ıselnou ε(i,j),(k,l) -zmˇenou budeme naz´ yvat zobrazen´ı z mnoˇziny celoˇc´ıseln´ ych matic do mnoˇziny celoˇc´ıseln´ ych matic stejného typu dané pˇredpisem:     .. .. .. . . . .. . . . .. . . . ... ... . . . . .      . . . ai,j + ε . . . ai,l − ε . . .   . . . ai,j . . . ai,l . . .    .  .. .. .. ..   . . ... . . . ... . . .  7−→  . . . . .  . .  ,      ... a  k,j . . . ak,l . . .    . . . ak,j − ε . . . ak,l + ε . . .  .. .. . . . .. . . . .. . . . ... ... ... . . . . kde ε ∈ Z. Obecnou celoˇc´ıselnou ε-zmˇenu bez konkrétn´ı specifikace ˇra´dkov´ ych a sloupcov´ ych index˚ u, budeme znaˇcit prostˇe jako ε-zmˇenu. Budeme-li v dalˇs´ım textu zmiˇ novat ε-zmˇenu, budeme vˇzdy m´ıt na mysli celoˇc´ıselnou ε-zmˇenu. Hlavn´ı vlastnost´ı ε-zmˇeny je skuteˇcnost, ˇze je-li aplikována na matici splˇ nuj´ıc´ı omezuj´ıc´ı podm´ınky (vyjma podm´ınky na nezápornost promˇenn´ ych) 13

u ´lohy (9), pak jej´ım v´ ystupem je opˇet matice splˇ nuj´ıc´ı omezuj´ıc´ı podm´ınky téˇze u ´lohy. Právˇe popsan´ y alokaˇcn´ı algoritmus tedy dopln´ıme iteraˇcn´ım algoritmem, kter´ y zjiˇst’uje existenci takové 1-zmˇeny (ˇci −1-zmˇeny), pˇri n´ıˇz dojde ke sn´ıˇzen´ı hodnoty u ´ˇcelové funkce a pokud alespoˇ n jedna taková 1-zmˇena (ˇci −1-zmˇena) existuje, tak aplikuje tu, která sn´ıˇz´ı hodnotu u ´ˇcelové funkce nejv´ıce. Takto postupuje aˇz do okamˇziku, kdy jiˇz ˇza´dná taková 1-zmˇena ani −1-zmˇena neexistuje. Pokud je v´ ysledné ˇreˇsen´ı nezáporné, je to jiˇz hledané optimáln´ı ˇreˇsen´ı u ´lohy (9), jak si dokáˇzeme pozdˇeji. Pokud nezáporné nen´ı, pak k nalezen´ı pˇr´ıpustného ˇreˇsen´ı pouˇzijeme metodu severozápadn´ıho rohu (která vede vˇzdy k nezápornému pˇr´ıpustnému ˇreˇsen´ı) a poté aplikujeme následuj´ıc´ı heuristick´ y iteraˇcn´ı algoritmus zaloˇzen´ y opˇet na ε-zmˇenˇe. 1. Najdeme vˇsechny ε-zmˇeny, kde ε ∈ {−1, 1} takové, ˇze po jejich aplikaci z˚ ustane matice ˇreˇsen´ı nezáporná a hodnota u ´ˇcelové funkce klesne. Mnoˇzinu vˇsech takov´ ych ε-zmˇen oznaˇc´ıme V. 2. Ze vˇsech ε-zmˇen z mnoˇziny V vybereme tu, která vede k nejvˇetˇs´ımu poklesu hodnoty u ´ˇcelové funkce a aplikujeme j´ı na aktuáln´ı matici ˇreˇsen´ı. 3. Pokud mnoˇzina V je prázdná, algoritmus konˇc´ı s aktuáln´ım pˇr´ıpustn´ ym ˇreˇsen´ım. Pokud nen´ı prázdná, vrát´ıme se na krok 1. Vzhledem k faktu, ˇze v kaˇzdém kroku mus´ı doj´ıt ke sn´ıˇzen´ı hodnoty u ´ˇcelové funkce, je algoritmus koneˇcn´ y. Nemus´ı vˇsak nutnˇe vést k optimáln´ımu ˇreˇsen´ı. Dodejme ale, ˇze k tomuto heuristickému algoritmu nebylo tˇreba pˇristoupit v pˇr´ıpadˇe ˇza´dn´ ych z analyzovan´ ych voleb. Spojen´ım popsaného alokaˇcn´ıho a iteraˇcn´ıho algoritmu (pˇr´ıpadnˇe i metody severozápadn´ıho rohu a heuristického iteraˇcn´ıho algoritmu) vznikne algoritmus, kter´ y oznaˇcujeme Ψ• .

5.2

D˚ ukaz optimality nalezen´ eho nez´ aporn´ eho ˇ reˇ sen´ı

Dokaˇzme nyn´ı, ˇze algoritmus Ψ• najde optimáln´ı ˇreˇsen´ı u ´lohy (9) za pˇredpokladu, ˇze toto ˇreˇsen´ı je nezáporné. K tomu potˇrebujeme dokázat nˇekolik tvrzen´ı. Jednak, ˇze algoritmus vˇzdy skonˇc´ı, jednak ˇze najde pˇr´ıpustné ˇreˇsen´ı a jednak, ˇze toto pˇr´ıpustné ˇreˇsen´ı je zároveˇ n optimáln´ı, je-li nezáporné. Skuteˇcnost, ˇze alokaˇcn´ı ˇcást algoritmu skonˇc´ı ukáˇzeme pomˇernˇe snadno. Staˇc´ı ukázat, ˇze algoritmus se nikde nezacykl´ı. K tomu vˇsak m˚ uˇze doj´ıt pouze v kroku 3, v nˇemˇz by nemusela existovat hledaná uspoˇra´daná dvojice index˚ u. Existence uspoˇra´dané dvojice index˚ u (i, j) ∈ F takové, ˇze mij > m 14

vij v

je dána t´ım, ˇze do kroku 3 se algoritmus dostane pouze pokud plat´ı P X R X

mij > m.

i=1 j=1

Protoˇze ale plat´ı P X R X

m

i=1 j=1

vij = m, v

plat´ı také P X R X i=1 j=1

mij >

P X R X

m

i=1 j=1

vij , v

a nem˚ uˇze tud´ıˇz pro vˇsechna (i, j) ∈ F b´ yt mij ≤ m

vij . v

Existuje tedy alespoˇ n jedna dvojice index˚ u (i0 , j 0 ) ∈ F taková, ˇze plat´ı mi0 j 0 > m

vi0 j 0 . v

T´ım je zaruˇceno, ˇze v kroku 3 algoritmus vˇzdy má z ˇceho vyb´ırat maximum. Maximum v kroku 3 je vˇzdy vybráno jen pro takovou uspoˇra´danou dvojici index˚ u (i0 , j 0 ) ∈ F, pro n´ıˇz plat´ı m

v i0 j 0 < mi0 j 0 ∈ N v

a proto je vˇzdy v kroku 4 alokaˇcn´ıho algoritmu odeˇc´ıtána jedniˇcka od celého v0 0 ˇc´ısla, které je vˇetˇs´ı, nebo rovno jedné (plat´ı totiˇz m ivj ≥ 0). Z toho plyne, ˇze pˇri pˇrechodu algoritmu na krok 6 bude aktuáln´ı matice tvoˇrená hodnotami mij nezáporná. V kroku 6 testujeme pouze zda existuje nˇejak´ y ˇra´dek, jehoˇz souˇcet je vyˇsˇs´ı, neˇz pˇr´ısluˇsné ˇrádkové omezen´ı prostˇrednictv´ım formulace Ω = ∅, nebot’ Ω = ∅, právˇe tehdy, kdyˇz Φ = ∅.3 Algoritmus v kroku 7 sniˇzuje o jedniˇcku vˇsechny hodnoty mij pro nˇeˇz plat´ı PP PR ı. Skonˇc´ı k=1 mkj > Lj a k=1 mik > Mi a to tak dlouho, dokud existuj´ 3

Souˇcet vˇsech hodnot tabulky je vyˇsˇs´ı neˇz souˇcet vˇsech ˇrádkov´ ych omezen´ı, právˇe tehdy, kdyˇz je vyˇsˇs´ı neˇz souˇcet vˇsech sloupcov´ ych omezen´ı, protoˇze souˇcet vˇsech ˇrádkov´ ych omezen´ı a souˇcet vˇsech sloupcov´ ych omezen´ı jsou si rovny.

15

ve chv´ıli, kdy ˇza´dn´ y ˇra´dkov´ y ani sloupcov´ y souˇcet nen´ı vyˇsˇs´ı, neˇz pˇr´ısluˇsné ˇra´dkové, ˇci sloupcové omezen´ı. Pochopitelnˇe v tomto okamˇziku plat´ı P X R X

mij ≤ m

i=1 j=1

a algoritmus se posouvá do závˇereˇcné fáze na krok 8. V kroku 8 testujeme pouze zda existuje nˇejak´ y ˇra´dek, jehoˇz souˇcet je niˇzˇs´ı, neˇz pˇr´ısluˇsné ˇra´dkové omezen´ı prostˇrednictv´ım formulace Λ = ∅ z analogického d˚ uvodu,P jako v kroku 6. Algoritmus nyn´ı zvyˇsuje vˇsechny hodnoty PR P mij pro nˇeˇz plat´ı k=1 mkj < Lj a k=1 mik < Mi a to tak dlouho, dokud existuj´ı. Skonˇc´ı ve chv´ıli, kdy ˇzádn´ y ˇra´dkov´ y ani sloupcov´ y souˇcet nen´ı niˇzˇs´ı, neˇz pˇr´ısluˇsné ˇra´dkové, ˇci sloupcové omezen´ı. V tomto okamˇziku jiˇz plat´ı P X R X

mij = m

i=1 j=1

a jsou splnˇena vˇsechna ˇra´dková a sloupcová omezen´ı. Algoritmus tedy nalezl pˇr´ıpustné ˇreˇsen´ı u ´lohy (9) s podm´ınkou (9) s podm´ınkou mij ∈ Z nam´ısto podm´ınky mij ∈ N0 . Nezáporné pˇr´ıpustné ˇreˇsen´ı jsme samozˇrejmˇe mohli nalézt i mnohem ménˇe sofistikovanou metodou (tˇreba metodou severozápadn´ıho rohu, Vogelovou metodou, apod.), nicménˇe náˇs alokaˇcn´ı algoritmus najde ˇreˇsen´ı, které je jiˇz velmi ”bl´ızko”k ˇreˇsen´ı optimáln´ımu. To ale nemus´ı b´ yt ˇreˇsen´ım nezáporn´ ym. Zb´ yvá ukázat, ˇze koneˇcnou posloupnost´ı aplikac´ı 1-zmˇen a −1-zmˇen dospˇejeme k optimáln´ımu ˇreˇsen´ı u ´lohy (9) s podm´ınkou mij ∈ Z nam´ısto podm´ınky mij ∈ N0 . Plat´ı tvrzen´ı, ˇze máme-li dvˇe matice, které splˇ nuj´ı stejná ˇra´dková a sloupcová omezen´ı, existuje koneˇcná posloupnost 1-zmˇen a −1-zmˇen taková, ˇze jejich aplikac´ı na jednu z matic, dostaneme tu druhou4 . V´ıme, ˇze optimáln´ı ˇreˇsen´ı existuje, protoˇze mnoˇzina pˇr´ıpustn´ ych ˇreˇsen´ı je koneˇcná a u ´ˇcelová funkce (at’ jiˇz jde o libovolnou ze tˇr´ı mˇer disproporcionality) je zdola omezená nulou. Mus´ı tedy existovat nˇejaká posloupnost 1-zmˇen a −1-zmˇen taková, ˇze jejich aplikac´ı na matici, která je v´ ystupem alokaˇcn´ıho algoritmu Ψ• dostaneme ˇreˇsen´ı, které je-li nezáporné, je i optimáln´ı. Na kaˇzdou ε-zmˇenu je moˇzné nahl´ıˇzet jako na matici a na aplikaci ε-zmˇeny jako na pˇriˇc´ıtán´ı této matice k p˚ uvodn´ı matici. Protoˇze mnoˇzina vˇsech matic reprezentuj´ıc´ıch celoˇc´ıselné ε-zmˇeny je uzavˇrená na sˇc´ıtán´ı a toto sˇc´ıtán´ı je komutativn´ı a asociativn´ı, ke kaˇzdé ε-zmˇenˇe existuje opaˇcná a pro vˇsechny existuje jedna nulová 0-zmˇena, je tato mnoˇzina spolu s binárn´ı operac´ı sˇc´ıtán´ı komutativn´ı (Abelovou) grupou. Kdyˇz pak libovoln´ y prvek této grupy pˇriˇcteme 4

To lze snadno dok´ azat konstrukc´ı takové posloupnosti.

16

k libovolnému pˇr´ıpustnému ˇreˇsen´ı u ´lohy (9) s podm´ınkou mij ∈ Z nam´ısto podm´ınky mij ∈ N0 , dostaneme opˇet pˇr´ıpustné ˇreˇsen´ı této u ´lohy. Mˇejme tedy nˇejaké pˇr´ıpustné ˇreˇsen´ı u ´lohy (9) s podm´ınkou mij ∈ Z nam´ısto podm´ınky mij ∈ N0 . V´ıme, ˇze existuje posloupnost celoˇc´ıseln´ ych ε-zmˇen taková, ˇze jejich postupnou aplikac´ı na toto pˇr´ıpustné ˇreˇsen´ı dostaneme ˇreˇsen´ı optimáln´ı (oznaˇcme tuto posloupnost v maticovém znaˇcen´ı B1 , . . . , BK ). Pak ˇza´dn´ yz prvk˚ u této posloupnosti nem˚ uˇze sám o sobˇe zv´ yˇsit hodnotu u ´ˇcelové funkce. Kdyby tomu tak bylo, aplikovali bychom k nˇemu opaˇcnou ε-zmˇenu a t´ım by doˇslo ke sn´ıˇzen´ı hodnoty u ´ˇcelové funkce a to je ve sporu s t´ım, ˇze posloupnost B1 , . . . , BK vede k optimáln´ımu ˇreˇsen´ı. Pokud tedy máme pˇr´ıpustné ˇreˇsen´ı a v´ıme, ˇze neexistuje ˇza´dná 1-zmˇena ani ˇza´dná −1-zmˇena, která by vedla ke sn´ıˇzen´ı hodnoty u ´ˇcelové funkce, mus´ı b´ yt jiˇz stávaj´ıc´ı pˇr´ıpustné ˇreˇsen´ı u ´lohy (9) s podm´ınkou mij ∈ Z nam´ısto podm´ınky mij ∈ N0 optimáln´ım ˇreˇsen´ım této u ´lohy. Tento argument vˇsak nelze pouˇz´ıt pˇri podm´ınce nezápornosti mij ∈ N0 , protoˇze pak mnoˇzina vˇsech pˇr´ıpustn´ ych (tj. takov´ ych, které vedou k nezápornému ˇreˇsen´ı) celoˇc´ıseln´ ych ε-zmˇen jiˇz nen´ı Abelovou grupou, jelikoˇz nen´ı zaruˇcena existence pˇr´ıpustné opaˇcné ε-zmˇeny ke kaˇzdému z prvk˚ u posloupnosti B1 , . . . , BK . Proto v pˇr´ıpadˇe, ˇze optimáln´ı ˇreˇsen´ı u ´lohy (9) s podm´ınkou mij ∈ Z nam´ısto podm´ınky mij ∈ N0 nen´ı nezáporné, nemus´ı algoritmus Ψ• nutnˇe nalézt ˇreˇsen´ı u ´lohy (9) s podm´ınkou mij ∈ N0 . Najde vˇsak alespoˇ n nˇejak´ y jeho odhad. Naopak pokud optimáln´ı ˇreˇsen´ı u ´lohy (9) s podm´ınkou mij ∈ Z nam´ısto podm´ınky mij ∈ N0 je nezáporné, algoritmus Ψ• jej vˇzdy najde, nebot’ jeho iterativn´ı ˇca´st se zastav´ı aˇz v okamˇziku, kdy neexistuje ˇza´dná 1-zmˇena, ani −1zmˇena, které by vedly ke sn´ıˇzen´ı hodnoty u ´ˇcelové funkce.

6

Spoleˇ cn´ y z´ aklad navrhovan´ ych algoritm˚ u

Prvn´ı tˇri kroky jsou spoleˇcné vˇsem tˇrem navrhovan´ ym algoritm˚ um a proto je pop´ıˇseme pouze jednou. 1. Prvn´ım krokem vˇsech navrhovan´ ych algoritm˚ u je aplikace uzav´ırac´ı klauzule. Tento krok nen´ı nevyhnuteln´ y a na moˇznost pouˇzit´ı algoritmu nemá ˇzádn´ y vliv. Aby mˇelo smysl porovnávat dosaˇzenou m´ıru proporcionality s jin´ ymi volebn´ımi systémy, budeme vˇzdy aplikovat stejnou uzav´ırac´ı klauzuli jaká je aplikována ve volebn´ım systému s n´ımˇz chceme v´ ysledky porovnávat. 2. Druh´ ym krokem vˇsech navrhovan´ ych algoritm˚ u je aplikace alokaˇcn´ıho algoritmu Ψ na alokaci mandát˚ u jednotliv´ ym kandiduj´ıc´ıcm politick´ ym 17

subjekt˚ um a to nezávisle na volebn´ıch obvodech. Pro kaˇzd´ y z algoritm˚ u se pouze v algoritmu Ψ pouˇzije jemu pˇr´ısluˇsná m´ıra disproporcionality. 3. Tˇret´ım krokem vˇsech navrhovan´ ych algoritm˚ u je aplikace alokaˇcn´ıho algoritmu Ψ na alokaci mandát˚ u jednotliv´ ym volebn´ım obvod˚ um a to nezávisle na jednotliv´ ych kandiduj´ıc´ıch politick´ ych subjektech. Pro kaˇzd´ y z algoritm˚ u se pouze v algoritmu Ψ pouˇzije jemu pˇr´ısluˇsná m´ıra disproporcionality. Nyn´ı popiˇsme tyto tˇri kroky formálnˇe. 1. Prvn´ı krok algoritmu znamená, ˇze pro vˇsechna i0 = 1, . . . , P 0 ovˇeˇr´ıme p0 platnost nerovnosti vi00 > u. Pokud pro dané i0 tato rovnost plat´ı, politick´ y subjekt i0 splnil uzav´ırac´ı klauzuli. Pokud neplat´ı, politick´ y sub0 0 jekt i je vyˇrazen z mnoˇziny P a nejsou mu alokovány ˇza´dné mandáty ve voleném orgánu. Poté, co jsou vyˇrazeny vˇsechny kandiduj´ıc´ı politické subjekty, které nesplnily uzav´ırac´ı klauzuli, zbyde z p˚ uvodn´ı mnoˇziny 0 P mnoˇzina vˇsech politick´ ych subjekt˚ u, které j´ı splnily. Oznaˇcme j´ı P. Jej´ı prvky jsou oznaˇceny nˇejak´ ymi indexy i01 < . . . < i0P . M´ısto indexu i0 , kter´ y jednoznaˇcnˇe oznaˇcoval politick´ y subjekt z mnoˇziny vˇsech kandiduj´ıc´ıch subjekt˚ u P 0 budeme nyn´ı vzhledem k restrikci na mnoˇzinu P pouˇz´ıvat index i ∈ {1, . . . , P } dan´ y poˇrad´ım v uspoˇrádané P -tici 0 0 y politick´ y subjekt i ∈ {1, . . . , P } index˚ u (i1 , . . . , iP ) . Dále pro kaˇzd´ poloˇz´ıme pi := p0i0 a pro kaˇzdé j = 1, . . . , R a kaˇzdé i = 1, . . . , P i PP PR y poˇcet hlas˚ u odepoloˇz´ıme vij := vi00 j a v := i=1 j=1 vij . Celkov´ i vzdan´ ych ve volbách se tedy sn´ıˇz´ı na celkov´ y poˇcet hlas˚ u odevzdan´ ych pouze tˇem politick´ ym subjekt˚ um, které postupuj´ı do skrutinia. Oznaˇcme dále rj poˇcet platn´ ych hlas˚ u odevzdan´ ych vˇsem politick´ ym subjekt˚ um postoupivˇs´ım do skrutinia, ve volebn´ım obvodu j a to pro vˇsechna j = 1, . . . , R. 2. Ve druhém kroku aplikujeme alokaˇcn´ı algoritmus Ψ na alokaci mandát˚ u jednotliv´ ym kandiduj´ıc´ıcm politick´ ym subjekt˚ um. Oznaˇcme Mi poˇcet mandát˚ u pˇriˇrazen´ ych t´ımto algoritmem politickému subjektu i pro vˇsechna i = 1, . . . , P. 3. Ve tˇret´ım kroku aplikujeme alokaˇcn´ı algoritmus Ψ na alokaci mandát˚ u jednotliv´ ym volebn´ım obvod˚ um. Oznaˇcme Lj poˇcet mandát˚ u pˇriˇrazen´ ych t´ımto algoritmem volebn´ımu obvodu j pro vˇsechna j = 1, . . . , R. 18

7

Algoritmus pro m´ıru disproporcionality ρ

Prvn´ı tˇri kroky algoritmu jsou popsány ve spoleˇcném základu navrhovan´ ych algoritm˚ u. 4. Nyn´ı sestav´ıme tabulku s poˇcty hlas˚ u, kde sloupce pˇredstavuj´ı jednotlivé volebn´ı obvody a ˇra´dky kandiduj´ıc´ı politické subjekty, které proˇsly pˇres uzav´ırac´ı klauzuli. Tabulka obsahuje v i−tém ˇra´dku a j−tém sloupci hodnotu vij . Dokonale proporcionáln´ı v´ ysledek voleb je dán mavij tic´ı typu P × R s prvky m ˜ ij := m v , kde i = 1, . . . , P a j = 1, . . . , R. 5. Protoˇze alokovat necelé mandáty nelze, mus´ıme ˇreˇsit následuj´ıc´ı problém celoˇc´ıselného nelineárn´ıho programován´ı: PP PR min ˜ ij − dij )2 i=1 j=1 (m dij , i=1,...,P , j=1,...,R za podm´ınek

PP

i=1

PR

j=1

dij = Lj

j = 1, . . . , R,

(10)

dij = Mi i = 1, . . . , P,

dij ∈ N0

i = 1, . . . , P , j = 1, . . . , R. j=1,...,R Hledáme tedy takovou matici D∗ = d∗ij i=1,...,P , která obsahuje jen nezáporná celá ˇc´ısla a která je ˇreˇsen´ım u ´lohy (10). Za pˇredpokladu, ˇze je ˇreˇsen´ı u ´lohy (10) s podm´ınkou dij ∈ Z nam´ısto podm´ınky dij ∈ N0 nezáporné, najdeme jej prostˇrednictv´ım algoritmu Ψ• minimalizuj´ıc´ıho m´ıru disproporcionality ρ. Pokud nen´ı nezáporné, najde algoritmus Ψ• jeho odhad. V´ ysledn´ y poˇcet mandát˚ u alokovan´ y ve prospˇech politického subjektu i ve volebn´ım obvodu j je roven d∗ij .

8

Algoritmus pro m´ıru disproporcionality φ

Prvn´ı tˇri kroky algoritmu jsou popsány ve spoleˇcném základu navrhovan´ ych algoritm˚ u. 4. Nyn´ı sestav´ıme tabulku s poˇcty hlas˚ u, kde sloupce pˇredstavuj´ı jednotlivé volebn´ı obvody a ˇrádky kandiduj´ıc´ı politické subjekty, které postoupily do skrutinia. Tabulka obsahuje v i−tém ˇrádku a j−tém sloupci hodnotu vij . Dokonale proporcionáln´ı v´ ysledek voleb je dán matic´ı typu v P × R s prvky m ˜ ij := m vij , kde i = 1, . . . , P a j = 1, . . . , R. 19

5. Hledáme matici D∗ = d∗ij

j=1,...,R i=1,...,P

, která je ˇreˇsen´ım u ´lohy (11).

min dij , i=1,...,P , j=1,...,R za podm´ınek

PP

i=1

PR

j=1

dij = Lj

PP PR i=1

j=1

|m ˜ ij − dij |

j = 1, . . . , R,

(11)

dij = Mi i = 1, . . . , P,

dij ∈ N0

i = 1, . . . , P , j = 1, . . . , R,

Za pˇredpokladu, ˇze je ˇreˇsen´ı u ´lohy (11) s podm´ınkou dij ∈ Z nam´ısto podm´ınky dij ∈ N0 nezáporné, najdeme jej prostˇrednictv´ım algoritmu Ψ• minimalizuj´ıc´ıho m´ıru disproporcionality φ. Pokud nen´ı nezáporné, najde algoritmus Ψ• jeho odhad. V´ ysledn´ y poˇcet mandát˚ u alokovan´ y ve prospˇech politického subjektu i ve volebn´ım obvodu j je roven d∗ij .

9

Algoritmus pro m´ıru disproporcionality ξ

Prvn´ı tˇri kroky algoritmu jsou popsány ve spoleˇcném základu navrhovan´ ych algoritm˚ u. Tento algoritmus má ale narozd´ıl od dvou pˇredeˇsl´ ych nˇekolik dodateˇcn´ ych podm´ınek, které vypl´ yvaj´ı z konstrukce m´ıry ξ. Ta je definována pod´ılem, kde ve jmenovateli je poˇcet platn´ ych hlas˚ u vij odevzdan´ ych ve prospˇech politického subjektu i ve volebn´ım obvodu j a ten pochopitelnˇe nesm´ı b´ yt nulov´ y. Nav´ıc nesm´ı b´ yt nulová ani ˇza´dná z hodnot Mi pro libovolné i = 1, . . . , P a ˇzádná z hodnot Lj pro libovolné j = 1, . . . , R. To se ale vzhledem k uzav´ırac´ı klauzuli pro ˇza´dné Mi nestane (nanejv´ yˇs m˚ uˇze b´ yt P = 0 a k alokaci mandát˚ u v˚ ubec nedojde). Pokud by Lj 0 = 0, pro nˇejaké j 0 ∈ {1, . . . , R} pak bychom volebn´ı obvod j 0 vynechali z dalˇs´ıch u ´vah. 4. Sestav´ıme tabulku s poˇcty hlas˚ u, kde sloupce pˇredstavuj´ı jednotlivé volebn´ı obvody a ˇra´dky kandiduj´ıc´ı politické subjekty, které postoupily do skrutinia. Tabulka obsahuje v i−tém ˇra´dku a j−tém sloupci hodnotu vij . Dokonale proporcionáln´ı v´ ysledek voleb je dán matic´ı typu P × R v s prvky m ˜ ij := m vij , kde i = 1, . . . , P a j = 1, . . . , R. 20

5. Hledáme matici D∗ = d∗ij

j=1,...,R i=1,...,P

min

, která je ˇreˇsen´ım u ´lohy (12).

PP PR i=1

j=1

(dij −m) ˜ 2 m ˜

dij , i=1,...,P

za podm´ınek

PP

dij = Lj

PR

dij = Mi i = 1, . . . , P,

i=1

j=1

dij ∈ N0

j = 1, . . . , R,

(12)

i = 1, . . . , P , j = 1, . . . , R.

Za pˇredpokladu, ˇze je ˇreˇsen´ı u ´lohy (12) s podm´ınkou dij ∈ Z nam´ısto podm´ınky dij ∈ N0 nezáporné, najdeme jej prostˇrednictv´ım algoritmu Ψ• minimalizuj´ıc´ıho m´ıru disproporcionality ξ. Pokud nen´ı nezáporné, najde algoritmus Ψ• jeho odhad. V´ ysledn´ y poˇcet mandát˚ u pro politick´ y subjekt i ve volebn´ım obvodu j je ∗ roven dij .

10

Ovˇ eˇ ren´ı pouˇ zitelnosti navrhovan´ ych algoritm˚ u v praxi

Vrat’me se nyn´ı ke zm´ınˇen´ ym tˇrem vlastnostem uveden´ ych algoritm˚ u, jeˇ jichˇz splnˇen´ı je nutné pro reálné pouˇzit´ı ve volbách do PS PCR. Jistˇe jde o algoritmy deterministické, které vedou pˇri kaˇzdé aplikaci na stejné vstupy ke stejnému v´ ystupu. Je tomu tak proto, ˇze k ˇreˇsen´ı nevyuˇz´ıváme ˇzádn´ ych metod zaloˇzen´ ych na generován´ı náhodn´ ych ˇc´ısel. Vˇsechny námi pouˇz´ıvané algoritmy jsou deterministické. Algoritmy jsou aplikovatelné na reálná data a vzhledem k uveden´ ym omezuj´ıc´ım podm´ınkám na nezápornost promˇenn´ ych nevede ani jeden z nich k alokaci záporného poˇctu mandát˚ u. Algoritmus Ψ sice m˚ uˇze dospˇet k ˇreˇsen´ı, které nen´ı nezáporné, ale tato moˇznost je oˇsetˇrena následn´ ym druh´ ym nápoˇctem obecnˇe suboptimáln´ıho nezáporného ˇreˇsen´ı. Nalezené v´ ysledné ˇreˇsen´ı tedy bude vˇzdy nezáporné. Pokud jde o rychlost jakou algoritmy dospˇej´ı k ˇreˇsen´ı, algoritmus Ψ má ˇ sen´ı je sloˇzitost O(mQ2 ) a algoritmus Ψ• má sloˇzitost O ((m + 1) P 2 R2 ) . Reˇ tedy nalezeno vˇzdy v polynomiáln´ım ˇcase. Pˇri praktické aplikaci na konkrétn´ı ˇ nalezl algoritmus Ψ ˇreˇsen´ı vˇzdy v ˇcase historická data z voleb do PS PCR niˇzˇs´ım, neˇz 1 vteˇrina, algoritmus Ψ• nalezl ˇreˇsen´ı v ˇrádu des´ıtek vteˇrin aˇz minut, nikdy ale nepˇrekroˇcil tˇr´ıminutovou hranici. 21

Vˇsechny tˇri poˇzadované vlastnosti námi navrhované algoritmy splˇ nuj´ı. Zastavme se ale jeˇstˇe u jedné d˚ uleˇzité vlastnosti a tou je jednoznaˇcnost ˇreˇsen´ı. Optimáln´ı ˇreˇsen´ı nemus´ı existovat vˇzdy jen jedno. Uvaˇzujme situaci, kdy jedna politická strana obdrˇz´ı pˇresnˇe 5% hlas˚ u a druhá pˇresnˇe zbyl´ ych 95% hlas˚ u. Alokujeme-li 10 mandát˚ u, bude v´ ystup algoritmu záviset na poˇrad´ı stran. Menˇs´ı stranˇe m˚ uˇze b´ yt alokován bud’ je’ den, nebo ˇza´dn´ y mandát a vˇetˇs´ı bud devˇet, nebo deset mandát˚ u. D˚ uvodem pro toto chován´ı je v´ ybˇer maxima v kroku 3. algoritmu Ψ, které nen´ı dáno jednoznaˇcnˇe a algoritmus je v takovém pˇr´ıpadˇe navrˇzen tak, aby vybral nejprve to maximum, které odpov´ıdá stranˇe s nejniˇzˇs´ım indexem. Tomuto jevu nen´ı moˇzné se zcela vyhnout a nevyhnou se mu ani aktuálnˇe pouˇz´ıvané metody, vˇcetnˇe d’Hondtova dˇelitele. Dalˇs´ı problém, kter´ y z této nejednoznaˇcnosti plyne je problém pˇriˇrazen´ı r˚ uzného poˇctu mandát˚ u stranám se shodn´ ym poˇctem z´ıskan´ ych hlas˚ u. Uvaˇzujme situaci, kdy kandiduj´ı pouze tˇri strany, dvˇe obdrˇz´ı 5% hlas˚ u a tˇret´ı zbyl´ ych 90%. Alokujeme-li opˇet právˇe 10 mandát˚ u, obdrˇz´ı nejvˇetˇs´ı strana 9 mandát˚ u a ostatn´ı dvˇe strany se musej´ı podˇelit o jeden mandát, kter´ y pˇripadne pouze jedné z nich. Protoˇze uspoˇrádán´ı stran i volebn´ıch obvod˚ u je dáno poˇctem hlas˚ u a nen´ı tedy ani otázkou náhody, ani libov˚ ule nˇejakého subjektu, zb´ yvá doˇreˇsit pouze situaci, kdy nˇekolik stran z´ıská ve volbách stejn´ y poˇcet hlas˚ u, resp. situaci, kdy stejn´ y poˇcet hlas˚ u je odevzdán v nˇekolika r˚ uzn´ ych volebn´ıch obvodech. Potom o jejich poˇrad´ı v rámci skupiny se shodn´ ym poˇctem hlas˚ u mus´ı rozhodnout los. Navrˇzené algoritmy ale jsou samy o sobˇe deterministické. Dodejme na závˇer této kapitoly, ˇze popsané, ne pˇr´ıliˇs ˇza´douc´ı chován´ı navrhovan´ ych algoritm˚ u nelze odstranit a zcela analogicky (vˇcetnˇe pouˇzit´ı losu) se s n´ım vyrovnávaj´ı i jiné volebn´ı systémy, vˇcetnˇe toho aktuálnˇe pouˇz´ıvaného ˇ ve volbách do PS PCR.

11

Porovn´ an´ı st´ avaj´ıc´ıch a navrˇ zen´ ych volebn´ıch syst´ em˚ u

Vˇsechny tˇri navrhované volebn´ı systémy maj´ı v´ yznam pouze tehdy, kdyˇz jsou volebn´ı obvody dostateˇcnˇe velké, aby v kaˇzdém z nich docházelo k alokaci alespoˇ n pˇeti mandát˚ u. Podle pouˇz´ıvané klasifikace volebn´ıch obvod˚ u (viz. http://cs.wikipedia.org/wiki/Volebn%C3%AD_obvod) by mˇelo j´ıt alespoˇ n o stˇrednˇe velké volebn´ı obvody. Pokud by naopak bylo volebn´ıch obvod˚ u hodnˇe a byly by kupˇr´ıkladu pouze jednomandátové, jako je tomu ˇ pak by navrhované volebn´ı systémy nemˇelo smysl u voleb do Senátu PCR, zavádˇet. 22

V´ ysledky alokace mandát˚ u prostˇrednictv´ım navrhovan´ ych algoritm˚ u jsme ˇ e národn´ı rady (kterou lze porovnali na datech z jednotliv´ ych voleb do Cesk´ ˇ a jednotliv´ ˇ které povaˇzovat za pˇredch˚ udkyni PS PCR) ych voleb do PS PCR, probˇehly po roce 1989. Jedná se o volby z let 1990, 1992, 1996, 1998, 2002, 2006 a 2010. Kompletn´ı data o tˇechto volbách ˇcerpáme z oficiáln´ıho inteˇ eho statistického u rentového zdroje Cesk´ ´ˇradu (viz. http://www.volby.cz). Porovnávali jsme vˇsechny tˇri navrˇzené algoritmy s aktuálnˇe platn´ ym volebn´ım systémem a s dalˇs´ımi osmnácti volebn´ımi systémy, které jsme vybrali náhodnˇe jako kombinace nejr˚ uznˇejˇs´ıch bˇeˇznˇe pouˇz´ıvan´ ych metod pˇrepoˇctu hlas˚ u na mandáty a to vˇse pˇri 5% uzav´ırac´ı klauzuli. Tˇechto osmnáct volebn´ıch systém˚ u tvoˇr´ı vzorek z mnoˇziny vˇsech moˇzn´ ych kombinac´ı metod pˇrepoˇctu hlas˚ u na mandáty, která obsahuje tis´ıce prvk˚ u. Náhodn´ y v´ ybˇer z této mnoˇziny byl proveden proto, ˇze porovnávat v´ ysledky tis´ıc˚ u volebn´ıch systém˚ u, které ˇcasto dávaj´ı stejné v´ ysledky, je v rozsahu tohoto textu nemoˇzné. Ke kaˇzdému z porovnávan´ ych volebn´ıch systém˚ u jsme spoˇc´ıtali vˇsechny tˇri m´ıry disproporcionality (1), (2) a (3). Kdykoliv v´ ypoˇcet m´ıry disproporcionality (3) nedával smysl vzhledem k dˇelen´ı nulou, v´ yslednou hodnotu disproporcionality jsme oznaˇcili jako NA (not applicable). Vˇsechny tˇri m´ıry disproporcionality jsme pouˇzili u kaˇzdého volebn´ıho systému tˇrikrát: 1. na alokaci mandát˚ u stranám, 2. na alokaci mandát˚ u volebn´ım obvod˚ um, 3. na alokaci mandát˚ u kombinaci stran a volebn´ıch obvod˚ u. Protoˇze za hlavn´ı pˇr´ınos n´ızké disproporcionality povaˇzujeme jistou rovnost mezi a priorn´ı silou jednotliv´ ych voliˇc˚ u a z toho vypl´ yvaj´ıc´ı spravedlivé rozdˇelen´ı mandát˚ u, jsou pro nás pochopitelnˇe ˇzádouc´ı niˇzˇs´ı hodnoty mˇer disproporcionality. Jednotlivé volebn´ı systémy, s nimiˇz námi navrˇzené algoritmy porovnáváme, vyuˇz´ıvaj´ı bˇeˇznˇe pouˇz´ıvan´ ych metod pˇrepoˇctu hlas˚ u na mandáty. Kaˇzdou metodu pˇrepoˇctu, kterou vyuˇz´ıvá nˇekter´ y z volebn´ıch systém˚ u, oznaˇcujeme zkratkou podle tabulky 2. Jednotlivé metody jsou bl´ıˇze popsány napˇr´ıklad v publikaci [Leb09]. Námi navrhované algoritmy znaˇc´ıme N1 (minimalizuj´ıc´ı m´ıru odchylky ρ), N2 (minimalizuj´ıc´ı m´ıru odchylky ψ) a N3 (minimalizuj´ıc´ı m´ıru odchylky ξ). Pˇredpokládáme dvoustupˇ nov´ y pˇrepoˇcet hlas˚ u na mandáty podobn´ y tomu, ˇ kter´ y se aktuálnˇe pouˇz´ıvá ve volbách do PS PCR. V prvn´ım stupni docház´ı k alokaci mandát˚ u na volebn´ı obvody a ve druhém v jednotliv´ ych volebn´ıch obvodech zvláˇst’ k alokaci mandát˚ u jednotliv´ ym politick´ ym subjekt˚ um. Metody 23

Metoda pˇrpoˇctu Haareova kv´ ota Hagenbach-Bischoffova kvóta Droopova kv´ ota Kv´ ota Imperiali Dˇelitel Imperiali Huntington˚ uv dˇelitel

Zkratka HA HB DK KI DI HU

Metoda pˇrpoˇctu Dˇelitel Sainte-Lagu¨ e d’Hondt˚ uv dˇelitel Modifikovan´ y dˇelitel Sainte-Lagu¨ e Pos´ılená kvóta Imperiali Dánsk´ y dˇelitel Metoda nejvˇetˇs´ıho zbytku

Zkratka SL DH MSL PKI DD Z

Tabulka 2: Metody pˇrepoˇctu hlas˚ u na mandáty pˇrepoˇctu HA, HB, DK, KI a PKI nemus´ı nutnˇe vést k alokaci vˇsech mandát˚ u a proto je nutné je doplnit nˇekterou ze zbyl´ ych metod, jejichˇz prostˇrednictv´ım se potom alokuj´ı zb´ yvaj´ıc´ı mandáty. Naopak metody pˇrepoˇctu DH, DI, DD, SL, MSL, Z a HU alokuj´ı vˇzdy vˇsechny mandáty. Proto je vˇzdy nutné metodu z prvn´ı skupiny doplnit metodou ze skupiny druhé. Tuto skuteˇcnost znaˇc´ıme symbolem ”+”. Pokud tedy napˇr´ıklad metoda Haareovy kvóty je doplnˇena metodou nejvˇetˇs´ıho zbytku, znaˇc´ıme v´ yslednou metodu pˇrepoˇctu HA+Z. Protoˇze nejprve docház´ı k alokaci mandát˚ u na volebn´ı obvody a teprve poté na politické subjekty, pˇriˇcemˇz pouˇzité metody pˇrepoˇctu nemus´ı b´ yt pˇri tˇechto dvou alokac´ıch totoˇzné, oddˇelujeme ve zkráceném zápisu prvn´ı ˇca´st (alokace mandát˚ u na volebn´ı obvody) od ˇca´sti druhé (alokace mandát˚ u na politické subjekty) znakem ”-”. Volebn´ı systém, kter´ y vyuˇz´ıvá k alokaci mandát˚ u na volebn´ı obvody Hagenbach-Bischoffovu kvótu doplnˇenou metodou nejvˇetˇs´ıho zbytku a poté v kaˇzdém volebn´ım obvodu k alokaci mandát˚ u na politické subjekty d’Hondtovu metodu, bychom oznaˇcili HB+ZDH. Protoˇze ale právˇe tento konkrétn´ı volebn´ı systém je aktuálnˇe pouˇz´ıván ˇ oznaˇcujeme jej v´ ve volbách do PS PCR yjimeˇcnˇe ACT. Vˇsechny ostatn´ı volebn´ı systémy ale jiˇz znaˇc´ıme podle popsaného schématu. Detailn´ı v´ ysledky porovnán´ı mˇer disproporcionalit jsou uvedeny v tabulkách v dodatku. Protoˇze m´ıra disproporcionality je mimojiné závislá i na poˇctu volebn´ıch obvod˚ u a poˇctu politick´ ych subjekt˚ u, které proˇsly pˇres uzav´ırac´ı klauzuli, nelze porovnávat pˇr´ımo jej´ı hodnoty dosaˇzené v r˚ uzn´ ych volbách. M´ısto toho uvád´ıme pr˚ umˇerné poˇrad´ı (pˇri vzestupném setˇr´ıdˇen´ı podle dosaˇzené m´ıry disproporcionality) jednotliv´ ych porovnávan´ ych volebn´ıch systém˚ u pˇres vˇsechny zkoumané volby. V tabulce 3 jsou uvedena pr˚ umˇerná poˇrad´ı volebn´ıch systém˚ u pˇri zkoumán´ı mˇer disproporcionality alokace mandát˚ u jednotliv´ ym politick´ ym subjekt˚ um, v tabulce 4 pr˚ umˇerná poˇrad´ı volebn´ıch systém˚ u pˇri zkoumán´ı mˇer disproporcionality alokace mandát˚ u jednotliv´ ym volebn´ım obvod˚ um a v tabulce 5 pr˚ umˇerná poˇrad´ı volebn´ıch systém˚ u pˇri zkoumán´ı mˇer disproporcionality alokace mandát˚ u jednotliv´ ym politick´ ym subjekt˚ um v jednotliv´ ych volebn´ıch obvodech.

24

Metoda N1 N2 N3 ACT DH-DH SL-SL HA+Z-DH HU-HU HA+Z-HU DD-DD DD-HU DD-DI DD-DH DH-DI DI-DI DK+DH-DK-DH DK+HU-SL KI+Z-HA+Z PKI+DI-PKI-DI SL-KI+Z SL-DH HB+DI-MSL

ρ 1,00 1,00 1,00 11,29 10,71 5,29 11,29 17,57 17,43 6,86 17,57 20,71 11,57 20,43 21,29 8,43 5,14 5,57 15,57 10,43 11,71 6,57

φ 1,00 1,00 1,00 11,14 10,43 5,00 11,14 17,00 17,14 6,86 17,57 20,43 11,57 20,29 21,00 9,14 4,86 5,43 15,14 10,71 11,57 5,86

ξ 1,29 1,00 1,00 11,14 10,57 5,29 11,14 17,57 17,43 7,29 17,57 20,71 11,43 20,43 21,29 8,86 5,00 5,86 15,29 10,43 11,57 5,86

Tabulka 3: Pr˚ umˇerné poˇrad´ı volebn´ıch systém˚ u pˇres vˇsechny analyzované ˇ volby do PS PCR (m´ıry disproporcionality alokace mandát˚ u politick´ ym subjekt˚ um)


ρ 1,00 1,00 1,00 5,86 4,00 7,57 5,86 11,14 5,86 12,29 12,29 12,29 12,29 4,00 14,57 5,86 8,29 4,57 4,00 7,57 7,57 12,86

φ 1,00 1,00 1,00 5,86 4,00 7,57 5,86 11,29 5,86 12,43 12,43 12,43 12,43 4,00 14,00 5,86 7,71 4,57 4,00 7,57 7,57 12,14

ξ 1,29 1,00 1,00 5,86 4,00 7,57 5,86 12,14 5,86 12,14 12,14 12,14 12,14 4,00 14,86 5,86 8,00 4,57 4,00 7,57 7,57 12,43

Tabulka 4: Pr˚ umˇerné poˇrad´ı volebn´ıch systém˚ u pˇres vˇsechny analyzované ˇ volby do PS PCR (m´ıry disproporcionality alokace mandát˚ u volebn´ım obvod˚ um)

25


ρ 3,14 3,14 4,17 10,71 10,14 4,14 10,71 17,14 17,43 7,14 18,00 20,71 13,00 20,57 21,29 7,43 3,86 2,43 15,43 10,43 11,43 7,29

φ 3,14 3,14 4,17 10,71 10,14 4,14 10,71 17,14 17,43 7,14 18,14 20,43 13,00 20,43 21,00 7,43 3,86 2,43 15,43 10,43 11,43 7,29

ξ 4,67 4,67 3,83 11,00 11,00 2,17 11,17 17,17 17,83 6,83 18,33 21,00 13,83 20,83 21,17 7,67 2,67 3,50 15,50 10,50 11,83 7,00

Tabulka 5: Pr˚ umˇerné poˇrad´ı volebn´ıch systém˚ u pˇres vˇsechny analyzované ˇ (m´ıry disproporcionality alokace mandát˚ volby do PS PCR u politick´ ym subjekt˚ um ve volebn´ıch obvodech)

26

12

Z´ avˇ er

V textu jsme navrhli tˇri algoritmy vedouc´ı k alokaci mandát˚ u politick´ ym subjekt˚ um v jednotliv´ ych volebn´ıch obvodech. Provedli jsme porovnán´ı tˇechto algoritm˚ u s náhodnˇe vybran´ ymi volebn´ımi systémy a volebn´ım systémem, kter´ y se aktuálnˇe pouˇz´ıvá a to na datech ze vˇsech historicky konan´ ych voleb ˇ ˇ do PS PCR a Ceské národn´ı rady od roku 1989 do roku 2011. Naˇse v´ ysledky ukazuj´ı, ˇze navrhované algoritmy vyuˇz´ıvaj´ıc´ı metod matematického programován´ı, vedou obecnˇe k niˇzˇs´ı m´ıˇre disproporcionality neˇz vˇsechny volebn´ı systémy, s nimiˇz jsme je porovnávali. Navrˇzené algoritmy vedou jak k niˇzˇs´ı m´ıˇre disproporcionality alokace mandát˚ u na politické subjekty, tak i k niˇzˇs´ı m´ıˇre disproporcionality alokace mandát˚ u jednotliv´ ym volebn´ım obvod˚ um, neˇz vˇsechny zkoumané alternativn´ı volebn´ı systémy. Nezávis´ı pˇritom pˇr´ıliˇs na tom, zda tuto m´ıru disproporcionality mˇeˇr´ıme pomoc´ı Gallagherova indexu, Loosemore-Hanbyho indexu, nebo Sainte-Lagu¨ e indexu. Nav´ıc je zachována uzav´ırac´ı klauzule a niˇzˇs´ı m´ıry disproporcionality tedy nen´ı dosaˇzeno na u ´kor vˇetˇs´ıho poˇctu stran, které se ˇ dostanou do PS PCR. Kromˇe alokace mandát˚ u na politické subjekty a alokace mandát˚ u na volebn´ı obvody zvláˇst’, zkoumáme i m´ıru disproporcionality alokace mandát˚ u na jejich kombinaci, tj. na alokaci mandát˚ u politick´ ym subjekt˚ um v jednotliv´ ych volebn´ıch obvodech. Navrˇzené algoritmy i v tomto pˇr´ıpadˇe dosahuj´ı velice n´ızk´ ych mˇer disproporcionality, nikoli vˇsak vˇzdy nejniˇzˇs´ıch ze vˇsech uvaˇzovan´ ych volebn´ıch systém˚ u. D˚ uvod pro tuto skuteˇcnost je ten, ˇze nˇekdy je moˇzné dosáhnout niˇzˇs´ı m´ıry disproporcionality alokace mandát˚ u politick´ ym subjekt˚ um v jednotliv´ ych volebn´ıch obvodech za cenu vyˇsˇs´ı m´ıry disproporcionality alokace mandát˚ u politick´ ym subjekt˚ um, nebo vyˇsˇs´ı m´ıry disproporcionality alokace mandát˚ u volebn´ım obvod˚ um. Algoritmy byly navrˇzeny tak, aby upˇrednostˇ novaly n´ızkou m´ıru disproporcionality alokace mandát˚ u na politické subjekty, pˇred n´ızkou m´ırou disproporcionality alokace mandát˚ u na politické subjekty v jednotliv´ ych volebn´ıch obvodech. Námi provedené d˚ ukazy ukazuj´ı, ˇze kaˇzd´ y ze tˇr´ı navrˇzen´ ych algoritm˚ u vede k optimáln´ı alokaci mandát˚ u na politické subjekty, resp. volebn´ı obvody z pohledu jemu pˇr´ısluˇsné m´ıry disproporcionality. Dokazujeme rovnˇeˇz, ˇze zavedené algoritmy vedou i k minimáln´ı moˇzné m´ıˇre disproporcionality alokace mandát˚ u politick´ ym subjekt˚ um v jednotliv´ ych volebn´ıch obvodech za pˇredpokladu, ˇze jsou dány poˇcty mandát˚ u pro kaˇzd´ y politick´ y subjekt i kaˇzd´ y volebn´ı obvod a za pˇredpokladu, ˇze tato minimáln´ı moˇzná m´ıra disproporcionality je dosaˇzena pro nezáporné ˇreˇsen´ı. Pokud by doˇslo k tomu, ˇze minimáln´ı m´ıry disproporcionality je dosaˇzeno pˇri alokaci záporného poˇctu mandát˚ u, námi navrˇzené algoritmy vedou obecnˇe pouze k suboptimáln´ımu 27

nezápornému ˇreˇsen´ı. Dva z navrhovan´ ych algoritm˚ u jsou pouˇzitelné obecnˇe, jsou dostateˇcnˇe rychlé a vedou k nalezen´ı jediného ˇreˇsen´ı. Mohou b´ yt, dle naˇseho m´ınˇen´ı, ˇ pˇrijaty jako volebn´ı sysémy pro volby do PS PCR. Tˇret´ı algoritmus je pouˇziteln´ y pouze tehdy, kdy ˇzádn´ y z kandiduj´ıc´ıch politick´ ych subjekt˚ u, které proˇsly pˇres uzav´ırac´ı klauzuli, neobdrˇzel v ˇza´dném z volebn´ıch obvod˚ u nulov´ y poˇcet platn´ ych hlas˚ u. Toto omezen´ı vˇsak nen´ı dáno algoritmem sam´ ym, ale m´ırou disproporcionality (Sainte-Lagu¨ e index), kterou minimalizuje.

Reference [Ben00]

Kenneth Benoit. Which electoral formula is the most proportional? a new look with new evidence. Political Analysis, 8:381–388, 2000.

[Col71]

J. S. Coleman. Control of collectivities and the power of a collectivity to act. Social Choice, B. Lieberman (ed.), pages 269–300, 1971.

[dCMP+ 87] Pietro Grilli di Cortona, Cecilia Manzi, Aline Pennisi, Federica Ricca, and Bruno Simeone. Evaluation and Optimization of Electoral Systems. Society for Industrial Mathematics, 1987. [Gal91]

M. Gallagher. Proportionality, disproportionality and electoral systems. Electoral Studies, 10:33–51, 1991.

[JL71]

V. J. Hanby J. Loosemore. The theoretical limits of maximum distortion: Some analytic expressions for electoral systems. British Journal of Political Science, 1:467–477, 1971.

[Kar08]

Alexander Karpov. Measurement of disproportionality in proportional representation systems. Mathematical and Computer Modelling, 48:1421–1438, 2008.

[Leb06]

T. Lebeda. Proporcionalita volebnich formuli pomernych systemu. Czech Sociological Review, 42:883–912, 2006.

[Leb09]

Tomas Lebeda. Volebni systemy pomerneho zastoupeni. Mechanismy, proporcionalita a politicke konsekvence. Nakladatelstvi Karolinum, Prague, 2009.

[Pen98]

A. Pennisi. Disproportionality indexes and robustness of proportional allocation methods. Electoral Studies, 17:3–19, 1998. 28

[vol]

http://www.volby.cz (date of access: June 2011).

[wik]

http://cs.wikipedia.org/wiki/volebn%C3%AD obvod (date of access: 25. 6. 2011).

29

13

Dodatek - detailn´ı v´ ysledky porovn´ an´ı

V této ˇca´sti uvád´ıme detailn´ı v´ ysledky porovnán´ı mˇer disproporcionality mezi ˇ jednotliv´ ymi volebn´ımi systémy na datech z jednotliv´ ych voleb do PS PCR. 1990 N1 N2 N3 ACT DH-DH SL-SL HA+Z-DH HU-HU HA+Z-HU DD-DD DD-HU DD-DI DD-DH DH-DI DI-DI DK+DH-DK-DH DK+HU-SL KI+Z-HA+Z PKI+DI-PKI-DI SL-KI+Z SL-DH HB+DI-MSL

ρ 0,528 0,528 0,528 86,899 17,278 7,695 86,899 169,776 169,776 7,326 169,776 282,187 86,899 246,816 246,816 40,021 7,695 13,653 169,776 86,899 86,899 17,278

φ 1,226 1,226 1,226 16,145 6,665 4,665 16,145 22,145 22,145 5,293 22,145 28,145 16,145 26,145 26,145 10,665 4,665 6,665 22,145 16,145 16,145 6,665

ξ 0,018 0,018 0,018 1,405 0,391 0,170 1,405 3,103 3,103 0,262 3,103 5,285 1,405 4,810 4,810 0,723 0,170 0,422 3,103 1,405 1,405 0,391

ˇ a Tabulka 6: Disproporcionalita alokace mandát˚ u politick´ ym subjekt˚ um (Cesk´ národn´ı rada 1990)

30

1992 N1 N2 N3 ACT DH-DH SL-SL HA+Z-DH HU-HU HA+Z-HU DD-DD DD-HU DD-DI DD-DH DH-DI DI-DI DK+DH-DK-DH DK+HU-SL KI+Z-HA+Z PKI+DI-PKI-DI SL-KI+Z SL-DH HB+DI-MSL

ρ 1,028 1,028 1,028 84,362 9,769 5,932 84,362 229,283 225,340 3,018 225,340 452,527 84,362 499,071 499,071 11,933 5,932 2,103 43,295 39,636 84,362 13,783

φ ξ 2,594 0,052 2,594 0,000 2,594 0,000 19,495 2,451 7,257 0,438 5,943 0,324 19,495 2,451 29,495 5,478 29,495 5,233 4,585 0,160 29,495 5,233 44,458 11,428 19,495 2,451 46,458 12,524 46,458 12,524 8,214 0,460 5,943 0,324 3,670 0,121 13,495 1,229 15,257 1,382 19,495 2,451 9,257 2,451

Tabulka 7: Disproporcionalita alokace mandát˚ u politick´ ym subjekt˚ um ˇ (Ceská národn´ı rada 1992)


ρ 0,527 0,527 0,527 32,084 39,065 3,081 32,084 107,851 127,024 6,502 127,024 451,176 32,084 407,895 436,876 5,934 3,081 3,081 41,383 14,387 32,084 4,074

φ ξ 1,577 0,017 1,577 0,017 1,577 0,017 11,577 1,015 13,577 1,250 3,768 0,143 11,577 1,015 23,577 3,408 25,577 3,851 4,833 0,270 25,577 3,851 47,577 13,159 11,577 1,015 45,577 11,762 47,577 12,676 5,048 0,259 3,768 0,143 3,768 0,143 13,577 1,376 7,577 0,572 11,577 1,015 3,768 0,103

Tabulka 8: Disproporcionalita alokace mandát˚ u politick´ ym subjekt˚ um (PS ˇ PCR 1996)

31


ρ 0,469 0,469 0,469 27,554 27,554 8,708 27,554 158,381 158,381 5,310 154,982 202,462 27,554 202,462 230,141 8,395 8,708 8,708 52,081 22,922 27,554 8,708

φ 1,384 1,384 1,384 11,143 11,143 5,128 11,143 27,143 27,143 4,857 27,143 31,143 11,143 31,143 33,143 5,384 5,128 5,128 15,143 9,384 11,143 5,128

ξ 0,016 0,016 0,016 0,817 0,817 0,199 0,817 4,397 4,397 0,143 4,377 5,633 0,817 5,633 6,495 0,250 0,199 0,199 1,585 0,724 0,817 0,199


2002 ρ φ ξ N1 0,242 0,792 0,007 N2 0,242 0,792 0,007 N3 0,242 0,792 0,007 ACT 9,477 5,938 0,211 DH-DH 9,477 5,938 0,211 SL-SL 1,511 2,062 0,031 HA+Z-DH 9,477 5,938 0,211 HU-HU 36,500 11,938 0,824 HA+Z-HU 64,377 15,938 1,437 DD-DD 6,153 4,062 0,136 DD-HU 63,749 15,938 1,364 DD-DI 156,333 23,938 3,434 DD-DH 15,995 7,938 0,339 DH-DI 164,961 23,938 3,752 DI-DI 177,589 23,938 4,178 DK+DH-DK-DH 4,119 3,938 0,086 DK+HU-SL 1,724 2,137 0,031 KI+Z-HA+Z 3,096 2,792 0,076 PKI+DI-PKI-DI 41,128 11,938 0,991 SL-KI+Z 15,995 7,938 0,339 SL-DH 15,995 7,938 0,339 HB+DI-MSL 0,870 1,420 0,023


32


ρ 0,718 0,718 0,718 122,368 122,368 12,202 122,368 318,689 315,703 22,646 345,704 675,257 122,368 714,272 714,272 22,791 12,202 4,460 150,627 84,842 122,368 14,531

φ 1,755 1,755 1,755 22,014 22,014 5,755 22,014 38,014 38,014 8,488 40,014 56,014 22,014 58,014 58,014 10,014 5,755 3,755 24,014 18,014 22,014 6,514

ξ 0,031 0,031 0,031 5,336 5,336 0,710 5,336 11,646 11,628 1,137 12,249 22,556 5,336 23,466 23,466 0,799 0,710 0,265 6,680 3,786 5,336 0,423


2010 ρ φ ξ N1 0,316 1,164 0,008 N2 0,316 1,164 0,008 N3 0,316 1,164 0,008 ACT 23,650 9,505 0,657 DH-DH 23,650 9,505 0,657 SL-SL 3,857 3,543 0,084 HA+Z-DH 23,650 9,505 0,657 HU-HU 86,259 19,180 2,475 HA+Z-HU 61,115 15,505 1,727 DD-DD 8,392 4,820 0,252 DD-HU 70,601 17,505 1,909 DD-DI 144,120 23,505 3,958 DD-DH 22,467 9,505 0,626 DH-DI 142,064 23,505 3,868 DI-DI 155,302 25,180 4,336 DK+DH-DK-DH 11,929 6,836 0,297 DK+HU-SL 1,040 1,887 0,031 KI+Z-HA+Z 5,171 3,981 0,129 PKI+DI-PKI-DI 50,392 13,505 1,449 SL-KI+Z 7,781 5,505 0,218 SL-DH 23,650 9,505 0,657 HB+DI-MSL 1,040 1,887 0,031


33


ρ 2,800 2,800 NA 23,001 17,930 16,155 23,001 38,273 38,273 20,601 43,239 58,191 27,967 50,155 47,003 18,882 16,155 16,764 38,273 23,001 23,001 17,930

φ 7,375 7,375 NA 19,867 16,817 15,816 19,867 24,893 24,893 17,818 26,893 30,473 21,867 28,473 26,588 17,009 15,816 16,175 24,893 19,867 19,867 16,817

ξ NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA

Tabulka 13: Disproporcionalita alokace mandát˚ u politick´ ym subjekt˚ um v ˇ jednotliv´ ych volebn´ıch obvodech (Ceská národn´ı rada 1990)


ρ 5,445 5,445 6,159 18,976 9,441 8,199 18,976 41,402 41,879 8,041 41,879 70,327 18,976 75,199 73,808 8,621 8,199 7,589 12,778 9,996 18,976 9,852

φ 15,375 15,375 16,088 24,357 19,093 18,100 24,357 34,737 35,213 17,942 35,213 47,398 24,357 49,398 49,398 18,522 18,100 17,490 20,508 19,676 24,357 19,504

ξ 3,871 3,871 3,817 7,551 4,313 3,842 7,657 14,044 14,102 4,031 14,102 22,267 7,657 23,694 22,124 4,127 3,948 4,041 5,695 4,868 7,657 4,490

Tabulka 14: Disproporcionalita alokace mandát˚ u politick´ ym subjekt˚ um v ˇ jednotliv´ ych volebn´ıch obvodech (Ceská národn´ı rada 1992)

34


ρ 5,015 5,015 5,015 7,264 8,202 4,127 7,264 19,851 22,204 4,466 22,204 68,689 7,264 62,475 65,944 4,444 4,127 4,105 8,436 5,342 7,264 4,412

φ ξ 12,620 1,773 12,620 1,773 12,620 1,773 14,869 2,769 15,807 3,147 11,732 1,452 14,869 2,769 24,650 7,274 26,650 8,065 12,071 1,642 26,650 8,065 47,662 21,085 14,869 2,769 45,662 18,984 47,662 20,338 12,049 1,488 11,732 1,452 11,710 1,458 16,040 3,729 12,946 1,835 14,869 2,769 12,017 1,614

Tabulka 15: Disproporcionalita alokace mandát˚ u politick´ ym subjekt˚ um v ˇ jednotliv´ ych volebn´ıch obvodech (PS PCR 1996)

35


ρ 5,027 5,027 5,280 8,516 8,516 4,607 8,516 27,223 27,223 5,383 26,000 33,099 9,238 32,172 35,852 6,618 4,607 4,607 11,372 7,805 8,516 4,607

φ ξ 11,965 1,459 11,965 1,459 12,218 1,447 15,454 2,246 15,454 2,246 11,545 1,265 15,454 2,246 28,375 6,773 28,375 6,773 12,321 1,411 28,109 6,781 31,928 8,994 16,176 2,388 31,928 8,652 33,928 10,094 13,556 1,733 11,545 1,265 11,545 1,265 18,310 3,856 14,743 2,141 15,454 2,246 11,545 1,265



ρ 6,018 6,018 6,018 6,384 6,384 6,532 6,384 9,048 10,614 6,644 10,238 20,523 6,858 20,900 24,077 6,287 5,851 5,805 9,081 6,858 6,858 6,922

φ 15,295 15,295 15,295 15,661 15,661 15,809 15,661 18,325 19,704 15,921 19,328 27,510 16,135 27,886 29,671 15,563 15,128 15,082 18,358 16,135 16,135 16,199

ξ 2,529 2,529 2,471 2,753 2,753 2,545 2,753 3,964 4,410 2,579 4,040 7,508 2,850 7,878 8,996 2,729 2,457 2,458 4,027 2,850 2,850 2,758


36


ρ 6,741 6,741 6,741 16,598 16,598 7,711 16,598 31,569 30,717 8,348 32,802 59,811 15,781 61,546 68,160 8,680 7,711 7,292 18,029 13,045 16,598 8,246

φ 18,779 18,779 18,779 27,381 27,381 19,748 27,381 39,076 38,898 20,385 40,854 56,354 27,337 58,089 58,089 20,718 19,748 19,329 28,813 24,310 27,381 20,283

ξ 5,227 5,227 5,003 10,921 10,921 5,139 10,921 16,667 16,695 5,950 17,479 29,503 11,018 30,101 29,192 7,338 5,139 5,213 11,931 9,534 10,921 7,100



ρ 7,097 7,097 7,097 9,068 9,068 6,566 9,068 14,284 13,049 7,013 13,446 20,490 9,974 19,721 22,373 7,111 7,283 6,432 10,029 7,556 9,068 7,283

φ 17,955 17,955 17,955 19,926 19,926 17,423 19,926 25,141 23,907 17,871 24,284 30,087 20,812 29,511 30,375 17,969 18,141 17,290 20,886 18,413 19,926 18,141

ξ 2,933 2,933 2,978 3,722 3,722 2,918 3,722 6,402 5,530 3,351 5,795 7,917 4,047 7,780 8,387 3,100 3,059 2,955 4,680 3,167 3,722 3,059


37


ρ 0,888 0,888 0,888 31,283 31,283 31,283 31,283 31,283 31,283 40,480 40,480 40,480 40,480 31,283 24,823 31,283 31,283 31,283 31,283 31,283 31,283 31,283

φ 2,422 2,422 2,422 13,067 13,067 13,067 13,067 13,067 13,067 15,067 15,067 15,067 15,067 13,067 12,024 13,067 13,067 13,067 13,067 13,067 13,067 13,067

ξ 0,044 0,037 0,037 1,016 1,016 1,016 1,016 1,016 1,016 1,351 1,351 1,351 1,351 1,016 0,866 1,016 1,016 1,016 1,016 1,016 1,016 1,016

ˇ a Tabulka 20: Disproporcionalita alokace mandát˚ u volebn´ım obvod˚ um (Cesk´ národn´ı rada 1990)


ρ 0,367 0,367 0,367 8,957 6,357 8,957 8,957 6,357 8,957 8,957 8,957 8,957 8,957 6,357 3,930 8,957 8,957 8,957 6,357 8,957 8,957 8,957

φ 1,297 1,297 1,297 6,831 4,831 6,831 6,831 4,831 6,831 6,831 6,831 6,831 6,831 4,831 4,632 6,831 6,831 6,831 4,831 6,831 6,831 6,831

ξ 0,016 0,016 0,016 0,294 0,185 0,294 0,294 0,185 0,294 0,294 0,294 0,294 0,294 0,185 0,167 0,294 0,294 0,294 0,185 0,294 0,294 0,294

ˇ a Tabulka 21: Disproporcionalita alokace mandát˚ u volebn´ım obvod˚ um (Cesk´ národn´ı rada 1992)

38


ρ 0,410 0,410 0,410 2,446 0,410 2,446 2,446 2,424 2,446 2,446 2,446 2,446 2,446 0,410 2,424 2,446 2,446 0,410 0,410 2,446 2,446 3,506

φ 1,721 1,721 1,721 3,271 1,721 3,271 3,271 3,112 3,271 3,271 3,271 3,271 3,271 1,721 3,112 3,271 3,271 1,721 1,721 3,271 3,271 3,721

ξ 0,019 0,019 0,019 0,092 0,019 0,092 0,092 0,087 0,092 0,092 0,092 0,092 0,092 0,019 0,087 0,092 0,092 0,019 0,019 0,092 0,092 0,175

Tabulka 22: Disproporcionalita alokace mandát˚ u volebn´ım obvod˚ um (PS ˇ PCR 1996)


ρ 0,652 0,652 0,652 2,510 2,510 2,510 2,510 2,510 2,510 3,558 3,558 3,558 3,558 2,510 5,034 2,510 2,510 2,510 2,510 2,510 2,510 2,510

φ 2,030 2,030 2,030 3,488 3,488 3,488 3,488 3,488 3,488 4,536 4,536 4,536 4,536 3,488 5,402 3,488 3,488 3,488 3,488 3,488 3,488 3,488

ξ 0,027 0,027 0,027 0,095 0,095 0,095 0,095 0,095 0,095 0,146 0,146 0,146 0,146 0,095 0,200 0,095 0,095 0,095 0,095 0,095 0,095 0,095


39


ρ 0,713 0,713 0,713 0,713 0,713 1,545 0,713 3,059 0,713 1,545 1,545 1,545 1,545 0,713 4,273 0,713 0,713 0,713 0,713 1,545 1,545 3,119

φ 2,779 2,779 2,779 2,779 2,779 3,611 2,779 5,125 2,779 3,611 3,611 3,611 3,611 2,779 6,339 2,779 2,779 2,779 2,779 3,611 3,611 4,609

ξ 0,059 0,059 0,059 0,059 0,059 0,095 0,059 0,321 0,059 0,095 0,095 0,095 0,095 0,059 0,407 0,059 0,059 0,059 0,059 0,095 0,095 0,299



ρ 0,834 0,834 0,834 0,993 0,993 0,993 0,993 2,179 0,993 0,834 0,834 0,834 0,834 0,993 9,547 0,993 0,993 0,993 0,993 0,993 0,993 0,993

φ 2,666 2,666 2,666 2,825 2,825 2,825 2,825 4,011 2,825 2,666 2,666 2,666 2,666 2,825 9,563 2,825 2,825 2,825 2,825 2,825 2,825 2,825

ξ 0,063 0,063 0,063 0,070 0,070 0,070 0,070 0,135 0,070 0,063 0,063 0,063 0,063 0,070 0,745 0,070 0,070 0,070 0,070 0,070 0,070 0,070


40


ρ 0,731 0,731 0,731 2,641 2,641 2,641 2,641 4,248 2,641 5,141 5,141 5,141 5,141 2,641 6,283 2,641 6,943 2,641 2,641 2,641 2,641 6,943

φ 2,247 2,247 2,247 4,157 4,157 4,157 4,157 5,695 4,157 6,157 6,157 6,157 6,157 4,157 5,921 4,157 6,157 4,157 4,157 4,157 4,157 6,157

ξ 0,047 0,047 0,047 0,161 0,161 0,161 0,161 0,437 0,161 0,321 0,321 0,321 0,321 0,161 0,494 0,161 0,348 0,161 0,161 0,161 0,161 0,348

Tabulka 26: Disproporcionalita alokace mandát˚ u volebn´ım obvod˚ um (PS ˇ 2010) PCR

41

IES Working Paper Series 2011 1. Roman Horváth, Jakub Matějů : How Are Inflation Targets Set? 2. Jana Procházková, Lenka Šťastná : Efficiency of Hospitals in the Czech Republic 3. Terezie Výprachtická : The Golden Rule of Public Finance and the Productivity of Public

Capital 4. Martina Mysíková : Income Inequalities within Couples in the Czech Republic and

European Countries 5. Veronika Holá, Petr Jakubík : Dopady změn parametrů pojištění vkladů v roce 2008 6. Vladimír Benáček, Eva Michalíková : The Factors of Growth of Small Family Businesses:

A Robust Estimation of the Behavioral Consistency in the Panel Data Models 7. Aleš Maršál : The Term Structure of Interest Rates in Small Open Economy DSGE Model 8. Robert Flasza, Milan Rippel, Jan Šolc : Modelling Long-Term Electricity Contracts at EEX 9. Jan Hlaváč : Financial performance of the Czech private pension scheme: Its current position and the comparison with other CEE countries 10. Tomáš Havránek, Zuzana Iršová, Karel Janda : Demand for Gasoline Is More PriceInelastic than Commonly Thought 11. Martina Mysíková : Personal Earnings Inequality in the Czech Republic 12. Ondřej Lopušník : Reflections on the reconciliation problem 13. Martin Gregor, Lenka Šťastná : The Decentralization Tradeoff for Complementary Spillovers 14. Lenka Šťastná, Martin Gregor : Local Government Efficiency: Evidence from the Czech Municipalities 15. Andrea Klimešová, Tomáš Václavík : Pricing of Gas Swing Options using Monte Carlo Methods 16. António Afonso, Jaromír Baxa, Michal Slavík : Fiscal developments and financial stress: a threshold VAR analysis 17. Karel Báťa : Equity Home Bias Among Czech Investors: Experimental Approach 18. Karel Janda : Credit Guarantees and Subsidies when Lender has a Market Power 19. Roman Horváth : Research & Development and Long-Term Economic Growth: A Bayesian Model Averaging Analysis 20. Petr Jakubík : Household Balance Sheets and Economic Crisis

21. Josef Brechler, Adam Geršl : Political Legislation Cycle in the Czech Republic 22. Jozef Baruník, Lukáš Vácha, Ladislav Krištoufek : Comovement of Central European 23. 24. 25. 26. 27. 28. 29. 30. 31.

stock markets using wavelet coherence: Evidence from high-frequency data Michal Skořepa : A convergence-sensitive optimum-currency-area index Marek Rusnák, Tomáš Havránek, Roman Horváth : How to Solve the Price Puzzle? A Meta-Analysis Marián Dinga, Vilma Dingová : Currency Union and Investment Flows: Estimating the Euro Effect on FDI Krenar Avdulaj : The Extreme Value Theory as a Tool to Measure Market Risk Ivo Jánský, Milan Rippel : Value at Risk forecasting with the ARMA-GARCH family of models in times of increased volatility Pavel Ryska, Jan Průša : Efficiency Wages in Heterogenous Labour Markets Peter Kukuk, Adam Geršl : Political Pressure on the National Bank of Slovakia Jiří Schwarz : Impact of Institutions on Cross-Border Price Dispersion Pavel Doležel : Volební systémy pro volby do Poslanecké sněmovny Parlamentu ČR založené na matematickém programování

All papers can be downloaded at: http://ies.fsv.cuni.cz



Univerzita Karlova v Praze, Fakulta sociálních věd Institut ekonomických studií [UK FSV – IES] Praha 1, Opletalova 26 E-mail : [email protected] http://ies.fsv.cuni.cz

Working Paper Volební systémy pro volby do Poslanecké sněmovny Parlamentu ČR založené na matematickém programování

Recommend Documents