liquid_feedback_core

changeset 30:d386cd067983 beta20

Better handling of ties (changes in computation of rankings and final winner in certain cases)

- Calculate strengths of pairwise defeats primarily by absolute number of votes for winner and secondarily by absolute number of votes for loser
- Different treatment of edge cases in function "vote_ratio"(...)
author jbe
date Sat Feb 20 15:08:31 2010 +0100 (2010-02-20)
parents 8da6fcea359b
children 6d634325a604
files core.sql
line diff
     1.1 --- a/core.sql	Tue Feb 09 14:46:20 2010 +0100
     1.2 +++ b/core.sql	Sat Feb 20 15:08:31 2010 +0100
     1.3 @@ -6,7 +6,7 @@
     1.4  BEGIN;
     1.5  
     1.6  CREATE VIEW "liquid_feedback_version" AS
     1.7 -  SELECT * FROM (VALUES ('beta19', NULL, NULL, NULL))
     1.8 +  SELECT * FROM (VALUES ('beta20', NULL, NULL, NULL))
     1.9    AS "subquery"("string", "major", "minor", "revision");
    1.10  
    1.11  
    1.12 @@ -1851,12 +1851,15 @@
    1.13      "negative_votes_p" "initiative"."negative_votes"%TYPE )
    1.14    RETURNS FLOAT8
    1.15    LANGUAGE 'plpgsql' STABLE AS $$
    1.16 -    DECLARE
    1.17 -      "total_v" INT4;
    1.18      BEGIN
    1.19 -      "total_v" := "positive_votes_p" + "negative_votes_p";
    1.20 -      IF "total_v" > 0 THEN
    1.21 -        RETURN "positive_votes_p"::FLOAT8 / "total_v"::FLOAT8;
    1.22 +      IF "positive_votes_p" > 0 AND "negative_votes_p" > 0 THEN
    1.23 +        RETURN
    1.24 +          "positive_votes_p"::FLOAT8 /
    1.25 +          ("positive_votes_p" + "negative_votes_p")::FLOAT8;
    1.26 +      ELSIF "positive_votes_p" > 0 THEN
    1.27 +        RETURN "positive_votes_p";
    1.28 +      ELSIF "negative_votes_p" > 0 THEN
    1.29 +        RETURN 1 - "negative_votes_p";
    1.30        ELSE
    1.31          RETURN 0.5;
    1.32        END IF;
    1.33 @@ -1866,7 +1869,7 @@
    1.34  COMMENT ON FUNCTION "vote_ratio"
    1.35    ( "initiative"."positive_votes"%TYPE,
    1.36      "initiative"."negative_votes"%TYPE )
    1.37 -  IS 'Ratio of positive votes to sum of positive and negative votes; 0.5, if there are neither positive nor negative votes';
    1.38 +  IS 'Returns a number, which can be used for comparison of initiatives based on count of approvals and disapprovals. Greater numbers indicate a better result. This function is NOT injective.';
    1.39  
    1.40  
    1.41  
    1.42 @@ -2729,8 +2732,26 @@
    1.43    IS 'Closes the voting on an issue, and calculates positive and negative votes for each initiative; The ranking is not calculated yet, to keep the (locking) transaction short.';
    1.44  
    1.45  
    1.46 -CREATE FUNCTION "init_array"("dim_p" INTEGER)
    1.47 -  RETURNS INT4[]
    1.48 +CREATE FUNCTION "defeat_strength"
    1.49 +  ( "positive_votes_p" INT4, "negative_votes_p" INT4 )
    1.50 +  RETURNS INT8
    1.51 +  LANGUAGE 'plpgsql' IMMUTABLE AS $$
    1.52 +    BEGIN
    1.53 +      IF "positive_votes_p" > "negative_votes_p" THEN
    1.54 +        RETURN ("positive_votes_p"::INT8 << 31) - "negative_votes_p"::INT8;
    1.55 +      ELSIF "positive_votes_p" = "negative_votes_p" THEN
    1.56 +        RETURN 0;
    1.57 +      ELSE
    1.58 +        RETURN -1;
    1.59 +      END IF;
    1.60 +    END;
    1.61 +  $$;
    1.62 +
    1.63 +COMMENT ON FUNCTION "defeat_strength"(INT4, INT4) IS 'Calculates defeat strength (INT8!) of a pairwise defeat primarily by the absolute number of votes for the winner and secondarily by the absolute number of votes for the loser';
    1.64 +
    1.65 +
    1.66 +CREATE FUNCTION "array_init_string"("dim_p" INTEGER)
    1.67 +  RETURNS TEXT
    1.68    LANGUAGE 'plpgsql' IMMUTABLE AS $$
    1.69      DECLARE
    1.70        "i"          INTEGER;
    1.71 @@ -2745,18 +2766,18 @@
    1.72            "ary_text_v" := "ary_text_v" || ',NULL';
    1.73          END LOOP;
    1.74          "ary_text_v" := "ary_text_v" || '}';
    1.75 -        RETURN "ary_text_v"::INT4[][];
    1.76 +        RETURN "ary_text_v";
    1.77        ELSE
    1.78          RAISE EXCEPTION 'Dimension needs to be at least 1.';
    1.79        END IF;
    1.80      END;
    1.81    $$;
    1.82  
    1.83 -COMMENT ON FUNCTION "init_array"(INTEGER) IS 'Needed for PostgreSQL < 8.4, due to missing "array_fill" function';
    1.84 -
    1.85 -
    1.86 -CREATE FUNCTION "init_square_matrix"("dim_p" INTEGER)
    1.87 -  RETURNS INT4[][]
    1.88 +COMMENT ON FUNCTION "array_init_string"(INTEGER) IS 'Needed for PostgreSQL < 8.4, due to missing "array_fill" function';
    1.89 +
    1.90 +
    1.91 +CREATE FUNCTION "square_matrix_init_string"("dim_p" INTEGER)
    1.92 +  RETURNS TEXT
    1.93    LANGUAGE 'plpgsql' IMMUTABLE AS $$
    1.94      DECLARE
    1.95        "i"          INTEGER;
    1.96 @@ -2780,14 +2801,14 @@
    1.97            "ary_text_v" := "ary_text_v" || ',' || "row_text_v";
    1.98          END LOOP;
    1.99          "ary_text_v" := "ary_text_v" || '}';
   1.100 -        RETURN "ary_text_v"::INT4[][];
   1.101 +        RETURN "ary_text_v";
   1.102        ELSE
   1.103          RAISE EXCEPTION 'Dimension needs to be at least 1.';
   1.104        END IF;
   1.105      END;
   1.106    $$;
   1.107  
   1.108 -COMMENT ON FUNCTION "init_square_matrix"(INTEGER) IS 'Needed for PostgreSQL < 8.4, due to missing "array_fill" function';
   1.109 +COMMENT ON FUNCTION "square_matrix_init_string"(INTEGER) IS 'Needed for PostgreSQL < 8.4, due to missing "array_fill" function';
   1.110  
   1.111  
   1.112  CREATE FUNCTION "calculate_ranks"("issue_id_p" "issue"."id"%TYPE)
   1.113 @@ -2795,7 +2816,8 @@
   1.114    LANGUAGE 'plpgsql' VOLATILE AS $$
   1.115      DECLARE
   1.116        "dimension_v"     INTEGER;
   1.117 -      "matrix"          INT4[][];
   1.118 +      "vote_matrix"     INT4[][];  -- absolute votes
   1.119 +      "matrix"          INT8[][];  -- defeat strength / best paths
   1.120        "i"               INTEGER;
   1.121        "j"               INTEGER;
   1.122        "k"               INTEGER;
   1.123 @@ -2807,22 +2829,22 @@
   1.124        "initiative_id_v" "initiative"."id"%TYPE;
   1.125      BEGIN
   1.126        PERFORM NULL FROM "issue" WHERE "id" = "issue_id_p" FOR UPDATE;
   1.127 -      -- Prepare matrix for Schulze-Method:
   1.128        SELECT count(1) INTO "dimension_v" FROM "initiative"
   1.129          WHERE "issue_id" = "issue_id_p" AND "agreed";
   1.130        IF "dimension_v" = 1 THEN
   1.131          UPDATE "initiative" SET "rank" = 1
   1.132            WHERE "issue_id" = "issue_id_p" AND "agreed";
   1.133        ELSIF "dimension_v" > 1 THEN
   1.134 -        "matrix" := "init_square_matrix"("dimension_v");  -- TODO: replace by "array_fill" function (PostgreSQL 8.4)
   1.135 +        -- Create "vote_matrix" with absolute number of votes in pairwise
   1.136 +        -- comparison:
   1.137 +        "vote_matrix" := "square_matrix_init_string"("dimension_v");  -- TODO: replace by "array_fill" function (PostgreSQL 8.4)
   1.138          "i" := 1;
   1.139          "j" := 2;
   1.140 -        -- Fill matrix with data from "battle" view
   1.141          FOR "battle_row" IN
   1.142            SELECT * FROM "battle" WHERE "issue_id" = "issue_id_p"
   1.143            ORDER BY "winning_initiative_id", "losing_initiative_id"
   1.144          LOOP
   1.145 -          "matrix"["i"]["j"] := "battle_row"."count";
   1.146 +          "vote_matrix"["i"]["j"] := "battle_row"."count";
   1.147            IF "j" = "dimension_v" THEN
   1.148              "i" := "i" + 1;
   1.149              "j" := 1;
   1.150 @@ -2836,25 +2858,23 @@
   1.151          IF "i" != "dimension_v" OR "j" != "dimension_v" + 1 THEN
   1.152            RAISE EXCEPTION 'Wrong battle count (should not happen)';
   1.153          END IF;
   1.154 -        -- Delete losers from matrix:
   1.155 +        -- Store defeat strengths in "matrix" using "defeat_strength"
   1.156 +        -- function:
   1.157 +        "matrix" := "square_matrix_init_string"("dimension_v");  -- TODO: replace by "array_fill" function (PostgreSQL 8.4)
   1.158          "i" := 1;
   1.159          LOOP
   1.160 -          "j" := "i" + 1;
   1.161 +          "j" := 1;
   1.162            LOOP
   1.163              IF "i" != "j" THEN
   1.164 -              IF "matrix"["i"]["j"] < "matrix"["j"]["i"] THEN
   1.165 -                "matrix"["i"]["j"] := 0;
   1.166 -              ELSIF matrix[j][i] < matrix[i][j] THEN
   1.167 -                "matrix"["j"]["i"] := 0;
   1.168 -              ELSE
   1.169 -                "matrix"["i"]["j"] := 0;
   1.170 -                "matrix"["j"]["i"] := 0;
   1.171 -              END IF;
   1.172 +              "matrix"["i"]["j"] := "defeat_strength"(
   1.173 +                "vote_matrix"["i"]["j"],
   1.174 +                "vote_matrix"["j"]["i"]
   1.175 +              );
   1.176              END IF;
   1.177              EXIT WHEN "j" = "dimension_v";
   1.178              "j" := "j" + 1;
   1.179            END LOOP;
   1.180 -          EXIT WHEN "i" = "dimension_v" - 1;
   1.181 +          EXIT WHEN "i" = "dimension_v";
   1.182            "i" := "i" + 1;
   1.183          END LOOP;
   1.184          -- Find best paths:
   1.185 @@ -2887,7 +2907,7 @@
   1.186            "i" := "i" + 1;
   1.187          END LOOP;
   1.188          -- Determine order of winners:
   1.189 -        "rank_ary" := "init_array"("dimension_v");  -- TODO: replace by "array_fill" function (PostgreSQL 8.4)
   1.190 +        "rank_ary" := "array_init_string"("dimension_v");  -- TODO: replace by "array_fill" function (PostgreSQL 8.4)
   1.191          "rank_v" := 1;
   1.192          "done_v" := 0;
   1.193          LOOP

Impressum / About Us