liquid_feedback_core

changeset 426:c83b2ac5477b

Use a composite type of two INT8's to describe the strength of a link for the Schulze method (necessary for tie-breaking of the links); Removed "no_reverse_beat_path" option
author jbe
date Wed May 21 22:01:43 2014 +0200 (2014-05-21)
parents 514eacf18e36
children 97f85b51e3d9
files core.sql test.sql
line diff
     1.1 --- a/core.sql	Mon Apr 14 01:09:54 2014 +0200
     1.2 +++ b/core.sql	Wed May 21 22:01:43 2014 +0200
     1.3 @@ -386,7 +386,6 @@
     1.4          "indirect_majority_strict"      BOOLEAN NOT NULL DEFAULT TRUE,
     1.5          "indirect_majority_positive"    INT4    NOT NULL DEFAULT 0,
     1.6          "indirect_majority_non_negative" INT4   NOT NULL DEFAULT 0,
     1.7 -        "no_reverse_beat_path"          BOOLEAN NOT NULL DEFAULT FALSE,
     1.8          "no_multistage_majority"        BOOLEAN NOT NULL DEFAULT FALSE,
     1.9          CONSTRAINT "timing" CHECK (
    1.10            ( "polling" = FALSE AND
    1.11 @@ -428,8 +427,7 @@
    1.12  COMMENT ON COLUMN "policy"."indirect_majority_strict"       IS 'If TRUE, then the indirect majority must be strictly greater than "indirect_majority_num"/"indirect_majority_den", otherwise it may also be equal.';
    1.13  COMMENT ON COLUMN "policy"."indirect_majority_positive"     IS 'Absolute number of votes in favor of the winner neccessary in a beat path to the status quo for an initaitive to be attainable as winner';
    1.14  COMMENT ON COLUMN "policy"."indirect_majority_non_negative" IS 'Absolute number of sum of votes in favor and abstentions in a beat path to the status quo for an initiative to be attainable as winner';
    1.15 -COMMENT ON COLUMN "policy"."no_reverse_beat_path" IS 'EXPERIMENTAL FEATURE: Causes initiatives with "reverse_beat_path" flag to not be "eligible", thus disallowing them to be winner. See comment on column "initiative"."reverse_beat_path". This option ensures both that a winning initiative is never tied in a (weak) condorcet paradox with the status quo and a winning initiative always beats the status quo directly with a simple majority.';
    1.16 -COMMENT ON COLUMN "policy"."no_multistage_majority" IS 'EXPERIMENTAL FEATURE: Causes initiatives with "multistage_majority" flag to not be "eligible", thus disallowing them to be winner. See comment on column "initiative"."multistage_majority". This disqualifies initiatives which could cause an instable result. An instable result in this meaning is a result such that repeating the ballot with same preferences but with the winner of the first ballot as status quo would lead to a different winner in the second ballot. If there are no direct majorities required for the winner, or if in direct comparison only simple majorities are required and "no_reverse_beat_path" is true, then results are always stable and this flag does not have any effect on the winner (but still affects the "eligible" flag of an "initiative").';
    1.17 +COMMENT ON COLUMN "policy"."no_multistage_majority" IS 'EXPERIMENTAL FEATURE: Causes initiatives with "multistage_majority" flag to not be "eligible", thus disallowing them to be winner. See comment on column "initiative"."multistage_majority". This disqualifies initiatives which could cause an instable result. An instable result in this meaning is a result such that repeating the ballot with same preferences but with the winner of the first ballot as status quo would lead to a different winner in the second ballot.';
    1.18  
    1.19  
    1.20  CREATE TABLE "unit" (
    1.21 @@ -669,7 +667,6 @@
    1.22          "schulze_rank"          INT4,
    1.23          "better_than_status_quo" BOOLEAN,
    1.24          "worse_than_status_quo" BOOLEAN,
    1.25 -        "reverse_beat_path"     BOOLEAN,
    1.26          "multistage_majority"   BOOLEAN,
    1.27          "eligible"              BOOLEAN,
    1.28          "winner"                BOOLEAN,
    1.29 @@ -688,7 +685,7 @@
    1.30              "direct_majority" ISNULL AND "indirect_majority" ISNULL AND
    1.31              "schulze_rank" ISNULL AND
    1.32              "better_than_status_quo" ISNULL AND "worse_than_status_quo" ISNULL AND
    1.33 -            "reverse_beat_path" ISNULL AND "multistage_majority" ISNULL AND
    1.34 +            "multistage_majority" ISNULL AND
    1.35              "eligible" ISNULL AND "winner" ISNULL AND "rank" ISNULL ) ),
    1.36          CONSTRAINT "better_excludes_worse" CHECK (NOT ("better_than_status_quo" AND "worse_than_status_quo")),
    1.37          CONSTRAINT "minimum_requirement_to_be_eligible" CHECK (
    1.38 @@ -728,9 +725,8 @@
    1.39  COMMENT ON COLUMN "initiative"."schulze_rank"           IS 'Schulze-Ranking';
    1.40  COMMENT ON COLUMN "initiative"."better_than_status_quo" IS 'TRUE, if initiative has a schulze-ranking better than the status quo';
    1.41  COMMENT ON COLUMN "initiative"."worse_than_status_quo"  IS 'TRUE, if initiative has a schulze-ranking worse than the status quo (DEPRECATED, since schulze-ranking is unique per issue; use "better_than_status_quo"=FALSE)';
    1.42 -COMMENT ON COLUMN "initiative"."reverse_beat_path"      IS 'TRUE, if there is a beat path (may include ties) from this initiative to the status quo';
    1.43  COMMENT ON COLUMN "initiative"."multistage_majority"    IS 'TRUE, if either (a) this initiative has no better rank than the status quo, or (b) there exists a better ranked initiative X, which directly beats this initiative, and either more voters prefer X to this initiative than voters preferring X to the status quo or less voters prefer this initiative to X than voters preferring the status quo to X';
    1.44 -COMMENT ON COLUMN "initiative"."eligible"               IS 'Initiative has a "direct_majority" and an "indirect_majority", is "better_than_status_quo" and depending on selected policy the initiative has no "reverse_beat_path" or "multistage_majority"';
    1.45 +COMMENT ON COLUMN "initiative"."eligible"               IS 'Initiative has a "direct_majority" and an "indirect_majority", is "better_than_status_quo" and depending on selected policy the initiative has no "multistage_majority"';
    1.46  COMMENT ON COLUMN "initiative"."winner"                 IS 'Winner is the "eligible" initiative with best "schulze_rank"';
    1.47  COMMENT ON COLUMN "initiative"."rank"                   IS 'Unique ranking for all "admitted" initiatives per issue; lower rank is better; a winner always has rank 1, but rank 1 does not imply that an initiative is winner; initiatives with "direct_majority" AND "indirect_majority" always have a better (lower) rank than other initiatives';
    1.48  
    1.49 @@ -3864,24 +3860,28 @@
    1.50  
    1.51  
    1.52  CREATE FUNCTION "secondary_link_strength"
    1.53 -  ( "initiative_id1_p" "initiative"."id"%TYPE,
    1.54 -    "initiative_id2_p" "initiative"."id"%TYPE,
    1.55 +  ( "initiative1_ord_p" INT4,
    1.56 +    "initiative2_ord_p" INT4,
    1.57      "tie_breaking_p"   "tie_breaking" )
    1.58    RETURNS INT8
    1.59    LANGUAGE 'plpgsql' IMMUTABLE AS $$
    1.60      BEGIN
    1.61 -      IF "initiative_id1_p" = "initiative_id2_p" THEN
    1.62 +      IF "initiative1_ord_p" = "initiative2_ord_p" THEN
    1.63          RAISE EXCEPTION 'Identical initiative ids passed to "secondary_link_strength" function (should not happen)';
    1.64        END IF;
    1.65        RETURN (
    1.66 -        CASE WHEN "initiative_id1_p" < "initiative_id2_p" THEN
    1.67 -          1::INT8 << 62
    1.68 -        ELSE 0 END
    1.69 -        +
    1.70 -        CASE WHEN "tie_breaking_p" = 'variant2'::"tie_breaking" THEN
    1.71 -          ("initiative_id2_p"::INT8 << 31) - "initiative_id1_p"::INT8
    1.72 +        CASE WHEN "tie_breaking_p" = 'simple'::"tie_breaking" THEN
    1.73 +          0
    1.74          ELSE
    1.75 -          "initiative_id2_p"::INT8 - ("initiative_id1_p"::INT8 << 31)
    1.76 +          CASE WHEN "initiative1_ord_p" < "initiative2_ord_p" THEN
    1.77 +            1::INT8 << 62
    1.78 +          ELSE 0 END
    1.79 +          +
    1.80 +          CASE WHEN "tie_breaking_p" = 'variant2'::"tie_breaking" THEN
    1.81 +            ("initiative2_ord_p"::INT8 << 31) - "initiative1_ord_p"::INT8
    1.82 +          ELSE
    1.83 +            "initiative2_ord_p"::INT8 - ("initiative1_ord_p"::INT8 << 31)
    1.84 +          END
    1.85          END
    1.86        );
    1.87      END;
    1.88 @@ -3890,18 +3890,24 @@
    1.89  COMMENT ON FUNCTION "secondary_link_strength"(INT4, INT4, "tie_breaking") IS 'Calculates a secondary criterion for the defeat strength (tie-breaking of the links)';
    1.90  
    1.91  
    1.92 +CREATE TYPE "link_strength" AS (
    1.93 +        "primary"               INT8,
    1.94 +        "secondary"             INT8 );
    1.95 +
    1.96 +
    1.97 +
    1.98  CREATE FUNCTION "calculate_ranks"("issue_id_p" "issue"."id"%TYPE)
    1.99    RETURNS VOID
   1.100    LANGUAGE 'plpgsql' VOLATILE AS $$
   1.101      DECLARE
   1.102        "issue_row"         "issue"%ROWTYPE;
   1.103        "policy_row"        "policy"%ROWTYPE;
   1.104 -      "dimension_v"       INTEGER;
   1.105 +      "dimension_v"       INT4;
   1.106        "vote_matrix"       INT4[][];  -- absolute votes
   1.107 -      "matrix"            INT8[][];  -- defeat strength / best paths
   1.108 -      "i"                 INTEGER;
   1.109 -      "j"                 INTEGER;
   1.110 -      "k"                 INTEGER;
   1.111 +      "matrix"            "link_strength"[][];  -- defeat strength / best paths
   1.112 +      "i"                 INT4;
   1.113 +      "j"                 INT4;
   1.114 +      "k"                 INT4;
   1.115        "battle_row"        "battle"%ROWTYPE;
   1.116        "rank_ary"          INT4[];
   1.117        "rank_v"            INT4;
   1.118 @@ -3947,11 +3953,18 @@
   1.119          "j" := 1;
   1.120          LOOP
   1.121            IF "i" != "j" THEN
   1.122 -            "matrix"["i"]["j"] := "defeat_strength"(
   1.123 -              "vote_matrix"["i"]["j"],
   1.124 -              "vote_matrix"["j"]["i"],
   1.125 -              "policy_row"."defeat_strength"
   1.126 -            );
   1.127 +            "matrix"["i"]["j"] := (
   1.128 +              "defeat_strength"(
   1.129 +                "vote_matrix"["i"]["j"],
   1.130 +                "vote_matrix"["j"]["i"],
   1.131 +                "policy_row"."defeat_strength"
   1.132 +              ),
   1.133 +              "secondary_link_strength"(
   1.134 +                "i",
   1.135 +                "j",
   1.136 +                "policy_row"."tie_breaking"
   1.137 +              )
   1.138 +            )::"link_strength";
   1.139            END IF;
   1.140            EXIT WHEN "j" = "dimension_v";
   1.141            "j" := "j" + 1;
   1.142 @@ -4059,7 +4072,6 @@
   1.143            "better_than_status_quo" = "rank_ary"["i"] < "rank_ary"[1],
   1.144            "worse_than_status_quo"  = "rank_ary"["i"] > "rank_ary"[1],
   1.145            "multistage_majority"    = "rank_ary"["i"] >= "rank_ary"[1],
   1.146 -          "reverse_beat_path"      = "matrix"[1]["i"] >= 0,
   1.147            "eligible"               = FALSE,
   1.148            "winner"                 = FALSE,
   1.149            "rank"                   = NULL  -- NOTE: in cases of manual reset of issue state
   1.150 @@ -4138,10 +4150,7 @@
   1.151          AND "initiative"."better_than_status_quo"
   1.152          AND (
   1.153            "policy_row"."no_multistage_majority" = FALSE OR
   1.154 -          "initiative"."multistage_majority" = FALSE )
   1.155 -        AND (
   1.156 -          "policy_row"."no_reverse_beat_path" = FALSE OR
   1.157 -          "initiative"."reverse_beat_path" = FALSE );
   1.158 +          "initiative"."multistage_majority" = FALSE );
   1.159        -- mark final winner:
   1.160        UPDATE "initiative" SET "winner" = TRUE
   1.161          FROM (
     2.1 --- a/test.sql	Mon Apr 14 01:09:54 2014 +0200
     2.2 +++ b/test.sql	Wed May 21 22:01:43 2014 +0200
     2.3 @@ -44,7 +44,7 @@
     2.4      "issue_quorum_num", "issue_quorum_den",
     2.5      "initiative_quorum_num", "initiative_quorum_den",
     2.6      "direct_majority_num", "direct_majority_den", "direct_majority_strict",
     2.7 -    "no_reverse_beat_path", "no_multistage_majority"
     2.8 +    "no_multistage_majority"
     2.9    ) VALUES (
    2.10      1,
    2.11      'Default policy',
    2.12 @@ -52,7 +52,7 @@
    2.13      25, 100,
    2.14      20, 100,
    2.15      1, 2, TRUE,
    2.16 -    TRUE, FALSE );
    2.17 +    FALSE );
    2.18  
    2.19  CREATE FUNCTION "time_warp"() RETURNS VOID
    2.20    LANGUAGE 'plpgsql' VOLATILE AS $$

Impressum / About Us