liquid_feedback_core

changeset 428:d0b4fa073ad3

Code cleanup regarding new tie-breaking
author jbe
date Thu May 22 04:35:26 2014 +0200 (2014-05-22)
parents 97f85b51e3d9
children a16072fc288a
files core.sql
line diff
     1.1 --- a/core.sql	Thu May 22 03:27:39 2014 +0200
     1.2 +++ b/core.sql	Thu May 22 04:35:26 2014 +0200
     1.3 @@ -415,8 +415,8 @@
     1.4  COMMENT ON COLUMN "policy"."issue_quorum_den"      IS 'Denominator of potential supporter quorum to be reached by one initiative of an issue to be "accepted" and enter issue state ''discussion''';
     1.5  COMMENT ON COLUMN "policy"."initiative_quorum_num" IS   'Numerator of satisfied supporter quorum  to be reached by an initiative to be "admitted" for voting';
     1.6  COMMENT ON COLUMN "policy"."initiative_quorum_den" IS 'Denominator of satisfied supporter quorum to be reached by an initiative to be "admitted" for voting';
     1.7 -COMMENT ON COLUMN "policy"."defeat_strength"       IS 'How pairwise defeats are measured for the Schulze method; see type "defeat_strength"';
     1.8 -COMMENT ON COLUMN "policy"."tie_breaking"          IS 'Tie-breaker for the Schulze method; see type "tie_breaking"';
     1.9 +COMMENT ON COLUMN "policy"."defeat_strength"       IS 'How pairwise defeats are measured for the Schulze method; see type "defeat_strength"; ''tuple'' is the recommended setting';
    1.10 +COMMENT ON COLUMN "policy"."tie_breaking"          IS 'Tie-breaker for the Schulze method; see type "tie_breaking"; ''variant1'' or ''variant2'' are recommended';
    1.11  COMMENT ON COLUMN "policy"."direct_majority_num"            IS 'Numerator of fraction of neccessary direct majority for initiatives to be attainable as winner';
    1.12  COMMENT ON COLUMN "policy"."direct_majority_den"            IS 'Denominator of fraction of neccessary direct majority for initaitives to be attainable as winner';
    1.13  COMMENT ON COLUMN "policy"."direct_majority_strict"         IS 'If TRUE, then the direct majority must be strictly greater than "direct_majority_num"/"direct_majority_den", otherwise it may also be equal.';
    1.14 @@ -3894,7 +3894,7 @@
    1.15          "primary"               INT8,
    1.16          "secondary"             INT8 );
    1.17  
    1.18 -COMMENT ON TYPE "link_strength" IS 'TODO';
    1.19 +COMMENT ON TYPE "link_strength" IS 'Type to store the defeat strength of a link between two candidates plus a secondary criterion to create unique link strengths between the candidates (needed for tie-breaking ''variant1'' and ''variant2'')';
    1.20  
    1.21  
    1.22  CREATE FUNCTION "find_best_paths"("matrix_d" "link_strength"[][])
    1.23 @@ -3941,7 +3941,7 @@
    1.24      END;
    1.25    $$;
    1.26  
    1.27 -COMMENT ON FUNCTION "find_best_paths"("link_strength"[][]) IS 'TODO';
    1.28 +COMMENT ON FUNCTION "find_best_paths"("link_strength"[][]) IS 'Computes the strengths of the best beat-paths from a square matrix';
    1.29  
    1.30  
    1.31  CREATE FUNCTION "calculate_ranks"("issue_id_p" "issue"."id"%TYPE)
    1.32 @@ -3973,7 +3973,7 @@
    1.33          FROM "policy" WHERE "id" = "issue_row"."policy_id";
    1.34        SELECT count(1) INTO "dimension_v"
    1.35          FROM "battle_participant" WHERE "issue_id" = "issue_id_p";
    1.36 -      -- Create "matrix_a" with absolute number of votes in pairwise
    1.37 +      -- create "matrix_a" with absolute number of votes in pairwise
    1.38        -- comparison:
    1.39        "matrix_a" := array_fill(NULL::INT4, ARRAY["dimension_v", "dimension_v"]);
    1.40        "i" := 1;
    1.41 @@ -3998,7 +3998,7 @@
    1.42        IF "i" != "dimension_v" OR "j" != "dimension_v" + 1 THEN
    1.43          RAISE EXCEPTION 'Wrong battle count (should not happen)';
    1.44        END IF;
    1.45 -      -- Store direct defeat strengths in "matrix_d" using "defeat_strength"
    1.46 +      -- store direct defeat strengths in "matrix_d" using "defeat_strength"
    1.47        -- and "secondary_link_strength" functions:
    1.48        "matrix_d" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]);
    1.49        "i" := 1;
    1.50 @@ -4025,9 +4025,9 @@
    1.51          EXIT WHEN "i" = "dimension_v";
    1.52          "i" := "i" + 1;
    1.53        END LOOP;
    1.54 -      -- Find best paths:
    1.55 +      -- find best paths:
    1.56        "matrix_p" := "find_best_paths"("matrix_d");
    1.57 -      -- Create partial order:
    1.58 +      -- create partial order:
    1.59        "matrix_b" := array_fill(NULL::BOOLEAN, ARRAY["dimension_v", "dimension_v"]);
    1.60        "i" := 1;
    1.61        LOOP
    1.62 @@ -4048,16 +4048,24 @@
    1.63          EXIT WHEN "i" = "dimension_v" - 1;
    1.64          "i" := "i" + 1;
    1.65        END LOOP;
    1.66 -      -- Tie-breaking:
    1.67 +      -- tie-breaking by forbidding shared weakest links in beat-paths
    1.68 +      -- (unless "tie_breaking" is set to 'simple', in which case tie-breaking
    1.69 +      -- is performed later by initiative id):
    1.70        IF "policy_row"."tie_breaking" != 'simple'::"tie_breaking" THEN
    1.71          "m" := 1;
    1.72          LOOP
    1.73            "n" := "m" + 1;
    1.74            LOOP
    1.75 +            -- only process those candidates m and n, which are tied:
    1.76              IF "matrix_b"["m"]["n"] ISNULL THEN
    1.77 +              -- start with beat-paths prior tie-breaking:
    1.78                "matrix_t" := "matrix_p";
    1.79 +              -- start with all links allowed:
    1.80                "matrix_f" := array_fill(FALSE, ARRAY["dimension_v", "dimension_v"]);
    1.81                LOOP
    1.82 +                -- determine (and forbid) that link that is the weakest link
    1.83 +                -- in both the best path from candidate m to candidate n and
    1.84 +                -- from candidate n to candidate m:
    1.85                  "i" := 1;
    1.86                  <<forbid_one_link>>
    1.87                  LOOP
    1.88 @@ -4067,7 +4075,7 @@
    1.89                        IF "matrix_d"["i"]["j"] = "matrix_t"["m"]["n"] THEN
    1.90                          "matrix_f"["i"]["j"] := TRUE;
    1.91                          -- exit for performance reasons,
    1.92 -                        -- as only one link will be found:
    1.93 +                        -- as exactly one link will be found:
    1.94                          EXIT forbid_one_link;
    1.95                        END IF;
    1.96                      END IF;
    1.97 @@ -4075,10 +4083,11 @@
    1.98                      "j" := "j" + 1;
    1.99                    END LOOP;
   1.100                    IF "i" = "dimension_v" THEN
   1.101 -                    RAISE EXCEPTION 'Schulze tie-breaking does not compute (should not happen)';
   1.102 +                    RAISE EXCEPTION 'Did not find shared weakest link for tie-breaking (should not happen)';
   1.103                    END IF;
   1.104                    "i" := "i" + 1;
   1.105                  END LOOP;
   1.106 +                -- calculate best beat-paths while ignoring forbidden links:
   1.107                  "i" := 1;
   1.108                  LOOP
   1.109                    "j" := 1;
   1.110 @@ -4086,7 +4095,7 @@
   1.111                      IF "i" != "j" THEN
   1.112                        "matrix_t"["i"]["j"] := CASE
   1.113                           WHEN "matrix_f"["i"]["j"]
   1.114 -                         THEN (-1::INT8) << 63
   1.115 +                         THEN (-1::INT8) << 63  -- worst possible value
   1.116                           ELSE "matrix_d"["i"]["j"] END;
   1.117                      END IF;
   1.118                      EXIT WHEN "j" = "dimension_v";
   1.119 @@ -4096,6 +4105,7 @@
   1.120                    "i" := "i" + 1;
   1.121                  END LOOP;
   1.122                  "matrix_t" := "find_best_paths"("matrix_t");
   1.123 +                -- extend partial order, if tie-breaking was successful:
   1.124                  IF "matrix_t"["m"]["n"] > "matrix_t"["n"]["m"] THEN
   1.125                    "matrix_b"["m"]["n"] := TRUE;
   1.126                    "matrix_b"["n"]["m"] := FALSE;
   1.127 @@ -4114,11 +4124,12 @@
   1.128            "m" := "m" + 1;
   1.129          END LOOP;
   1.130        END IF;
   1.131 -      -- Determine order of winners:
   1.132 +      -- store a unique ranking in "rank_ary":
   1.133        "rank_ary" := array_fill(NULL::INT4, ARRAY["dimension_v"]);
   1.134        "rank_v" := 1;
   1.135        LOOP
   1.136          "i" := 1;
   1.137 +        <<assign_next_rank>>
   1.138          LOOP
   1.139            IF "rank_ary"["i"] ISNULL THEN
   1.140              "j" := 1;
   1.141 @@ -4134,14 +4145,13 @@
   1.142                  -- someone else is better
   1.143                  EXIT;
   1.144                END IF;
   1.145 -              "j" := "j" + 1;
   1.146 -              IF "j" = "dimension_v" + 1 THEN
   1.147 +              IF "j" = "dimension_v" THEN
   1.148                  -- noone is better
   1.149                  "rank_ary"["i"] := "rank_v";
   1.150 -                EXIT;
   1.151 +                EXIT assign_next_rank;
   1.152                END IF;
   1.153 +              "j" := "j" + 1;
   1.154              END LOOP;
   1.155 -            EXIT WHEN "j" = "dimension_v" + 1;
   1.156            END IF;
   1.157            "i" := "i" + 1;
   1.158            IF "i" > "dimension_v" THEN

Impressum / About Us