# HG changeset patch # User jbe # Date 1348954897 -7200 # Node ID 548cec6b7a79fb5a9eb0dc1a03a482d868d04cdd # Parent 7cad34b945aca7ba9a6fdd16ed2c7247abfbcf6d Better tie-breaking diff -r 7cad34b945ac -r 548cec6b7a79 core.sql --- a/core.sql Tue Sep 25 13:54:24 2012 +0200 +++ b/core.sql Sat Sep 29 23:41:37 2012 +0200 @@ -7,7 +7,7 @@ BEGIN; CREATE VIEW "liquid_feedback_version" AS - SELECT * FROM (VALUES ('2.1.0', 2, 1, 0)) + SELECT * FROM (VALUES ('2.2.0', 2, 2, 0)) AS "subquery"("string", "major", "minor", "revision"); @@ -329,6 +329,11 @@ COMMENT ON COLUMN "session"."lang" IS 'Language code of the selected language'; +CREATE TYPE "schulze_variant" AS ENUM ('absolute_strength', 'tuple_strength', 'partial_tie_breaking', 'tie_breaking_with_negative_strength'); + +COMMENT ON TYPE "schulze_variant" IS 'Variant of schulze method, which differ by complexity; greater values have a higher complexity'; + + CREATE TABLE "policy" ( "id" SERIAL4 PRIMARY KEY, "index" INT4 NOT NULL, @@ -356,6 +361,7 @@ "indirect_majority_non_negative" INT4 NOT NULL DEFAULT 0, "no_reverse_beat_path" BOOLEAN NOT NULL DEFAULT TRUE, "no_multistage_majority" BOOLEAN NOT NULL DEFAULT FALSE, + "schulze_variant" "schulze_variant" NOT NULL DEFAULT 'tie_breaking_with_negative_strength', CONSTRAINT "timing" CHECK ( ( "polling" = FALSE AND "admission_time" NOTNULL AND "discussion_time" NOTNULL AND @@ -671,13 +677,13 @@ COMMENT ON COLUMN "initiative"."negative_votes" IS 'Calculated from table "direct_voter"'; COMMENT ON COLUMN "initiative"."direct_majority" IS 'TRUE, if "positive_votes"/("positive_votes"+"negative_votes") is strictly greater or greater-equal than "direct_majority_num"/"direct_majority_den", and "positive_votes" is greater-equal than "direct_majority_positive", and ("positive_votes"+abstentions) is greater-equal than "direct_majority_non_negative"'; COMMENT ON COLUMN "initiative"."indirect_majority" IS 'Same as "direct_majority", but also considering indirect beat paths'; -COMMENT ON COLUMN "initiative"."schulze_rank" IS 'Schulze-Ranking without tie-breaking'; -COMMENT ON COLUMN "initiative"."better_than_status_quo" IS 'TRUE, if initiative has a schulze-ranking better than the status quo (without tie-breaking)'; -COMMENT ON COLUMN "initiative"."worse_than_status_quo" IS 'TRUE, if initiative has a schulze-ranking worse than the status quo (without tie-breaking)'; +COMMENT ON COLUMN "initiative"."schulze_rank" IS 'Schulze-Ranking'; +COMMENT ON COLUMN "initiative"."better_than_status_quo" IS 'TRUE, if initiative has a schulze-ranking better than the status quo'; +COMMENT ON COLUMN "initiative"."worse_than_status_quo" IS 'TRUE, if initiative has a schulze-ranking worse than the status quo'; 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'; 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'; 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"'; -COMMENT ON COLUMN "initiative"."winner" IS 'Winner is the "eligible" initiative with best "schulze_rank" and in case of ties with lowest "id"'; +COMMENT ON COLUMN "initiative"."winner" IS 'Winner is the "eligible" initiative with best "schulze_rank" and in case of unresolved ties with lowest "id"'; 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'; @@ -3848,22 +3854,47 @@ 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.'; +CREATE FUNCTION "impossible_defeat_strength"() + RETURNS INT8 + LANGUAGE 'plpgsql' IMMUTABLE AS $$ + BEGIN + RETURN -1::INT8 << 63; + END; + $$; + +COMMENT ON FUNCTION "impossible_defeat_strength"() IS 'An INT8 value lower than any other value returned by function "defeat_strength"(INT4, INT4)'; + + CREATE FUNCTION "defeat_strength" - ( "positive_votes_p" INT4, "negative_votes_p" INT4 ) + ( "schulze_variant_p" "schulze_variant", + "positive_votes_p" INT4, + "negative_votes_p" INT4 ) RETURNS INT8 LANGUAGE 'plpgsql' IMMUTABLE AS $$ BEGIN - IF "positive_votes_p" > "negative_votes_p" THEN - RETURN ("positive_votes_p"::INT8 << 31) - "negative_votes_p"::INT8; - ELSIF "positive_votes_p" = "negative_votes_p" THEN - RETURN 0; + IF "schulze_variant_p" >= 'tuple_strength'::"schulze_variant" THEN + IF "positive_votes_p" > "negative_votes_p" THEN + RETURN ("positive_votes_p"::INT8 << 31) - "negative_votes_p"::INT8; + ELSIF "positive_votes_p" = "negative_votes_p" THEN + RETURN 0::INT8; + ELSE + IF "schulze_variant_p" >= 'tie_breaking_with_negative_strength'::"schulze_variant" THEN + RETURN "positive_votes_p"::INT8 - ("negative_votes_p"::INT8 << 31); + ELSE + RETURN "impossible_defeat_strength"(); + END IF; + END IF; ELSE - RETURN -1; + IF "positive_votes_p" > "negative_votes_p" THEN + RETURN "positive_votes_p"::INT8; + ELSE + RETURN 0::INT8; + END IF; END IF; END; $$; -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'; +COMMENT ON FUNCTION "defeat_strength"("schulze_variant", 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. A tie has a strength of zero.'; CREATE FUNCTION "calculate_ranks"("issue_id_p" "issue"."id"%TYPE) @@ -3873,11 +3904,17 @@ "issue_row" "issue"%ROWTYPE; "policy_row" "policy"%ROWTYPE; "dimension_v" INTEGER; - "vote_matrix" INT4[][]; -- absolute votes - "matrix" INT8[][]; -- defeat strength / best paths + "vote_matrix" INT4[][]; -- absolute votes + "direct_matrix" INT8[][]; -- direct defeat strength + "path_matrix" INT8[][]; -- defeat strength of best path + "compare_matrix" BOOLEAN[][]; -- binary relation to create schulze-rank + "forbidden_matrix" BOOLEAN[][]; -- forbidden links for tie-breaking + "modified_matrix" INT8[][]; -- defeat strength after tie-breaking "i" INTEGER; "j" INTEGER; "k" INTEGER; + "m" INTEGER; + "n" INTEGER; "battle_row" "battle"%ROWTYPE; "rank_ary" INT4[]; "rank_v" INT4; @@ -3917,15 +3954,16 @@ IF "i" != "dimension_v" OR "j" != "dimension_v" + 1 THEN RAISE EXCEPTION 'Wrong battle count (should not happen)'; END IF; - -- Store defeat strengths in "matrix" using "defeat_strength" + -- Store defeat strengths in "path_matrix" using "defeat_strength" -- function: - "matrix" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]); + "direct_matrix" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]); "i" := 1; LOOP "j" := 1; LOOP IF "i" != "j" THEN - "matrix"["i"]["j"] := "defeat_strength"( + "direct_matrix"["i"]["j"] := "defeat_strength"( + "policy_row"."schulze_variant", "vote_matrix"["i"]["j"], "vote_matrix"["j"]["i"] ); @@ -3937,6 +3975,7 @@ "i" := "i" + 1; END LOOP; -- Find best paths: + "path_matrix" := "direct_matrix"; "i" := 1; LOOP "j" := 1; @@ -3945,13 +3984,13 @@ "k" := 1; LOOP IF "i" != "k" AND "j" != "k" THEN - IF "matrix"["j"]["i"] < "matrix"["i"]["k"] THEN - IF "matrix"["j"]["i"] > "matrix"["j"]["k"] THEN - "matrix"["j"]["k"] := "matrix"["j"]["i"]; + IF "path_matrix"["j"]["i"] < "path_matrix"["i"]["k"] THEN + IF "path_matrix"["j"]["i"] > "path_matrix"["j"]["k"] THEN + "path_matrix"["j"]["k"] := "path_matrix"["j"]["i"]; END IF; ELSE - IF "matrix"["i"]["k"] > "matrix"["j"]["k"] THEN - "matrix"["j"]["k"] := "matrix"["i"]["k"]; + IF "path_matrix"["i"]["k"] > "path_matrix"["j"]["k"] THEN + "path_matrix"["j"]["k"] := "path_matrix"["i"]["k"]; END IF; END IF; END IF; @@ -3965,6 +4004,131 @@ EXIT WHEN "i" = "dimension_v"; "i" := "i" + 1; END LOOP; + -- initial calculation of binary relation: + "compare_matrix" := array_fill(NULL::BOOLEAN, ARRAY["dimension_v", "dimension_v"]); + "i" := 1; + LOOP + "j" := 1; + LOOP + IF "i" != "j" THEN + IF "path_matrix"["i"]["j"] > "path_matrix"["j"]["i"] THEN + "compare_matrix"["i"]["j"] = TRUE; + "compare_matrix"["j"]["i"] = FALSE; + ELSIF "path_matrix"["i"]["j"] < "path_matrix"["j"]["i"] THEN + "compare_matrix"["i"]["j"] = FALSE; + "compare_matrix"["j"]["i"] = TRUE; + END IF; + END IF; + EXIT WHEN "j" = "dimension_v"; + "j" := "j" + 1; + END LOOP; + EXIT WHEN "i" = "dimension_v"; + "i" := "i" + 1; + END LOOP; + -- tie-breaking: + IF "policy_row"."schulze_variant" >= 'partial_tie_breaking'::"schulze_variant" THEN + "modified_matrix" := array_fill(NULL::INT8, ARRAY["dimension_v", "dimension_v"]); + "forbidden_matrix" := array_fill(NULL::BOOLEAN, ARRAY["dimension_v", "dimension_v"]); + "m" := 1; + LOOP + "n" := "m" + 1; + LOOP + IF "compare_matrix"["m"]["n"] ISNULL THEN + "i" := 1; + LOOP + "j" := 1; + LOOP + IF "i" != "j" THEN + "forbidden_matrix"["i"]["j"] := FALSE; + "modified_matrix"["i"]["j"] := "path_matrix"["i"]["j"]; + END IF; + EXIT WHEN "j" = "dimension_v"; + "j" := "j" + 1; + END LOOP; + EXIT WHEN "i" = "dimension_v"; + "i" := "i" + 1; + END LOOP; + LOOP + "i" := 1; + LOOP + "j" := 1; + LOOP + IF "i" != "j" THEN + IF "modified_matrix"["m"]["n"] = "direct_matrix"["i"]["j"] THEN + "forbidden_matrix"["i"]["j"] := TRUE; + END IF; + END IF; + EXIT WHEN "j" = "dimension_v"; + "j" := "j" + 1; + END LOOP; + EXIT WHEN "i" = "dimension_v"; + "i" := "i" + 1; + END LOOP; + "i" := 1; + LOOP + "j" := 1; + LOOP + IF "i" != "j" THEN + IF "forbidden_matrix"["i"]["j"] THEN + "modified_matrix"["i"]["j"] := "impossible_defeat_strength"(); + ELSE + "modified_matrix"["i"]["j"] := "direct_matrix"["i"]["j"]; + END IF; + END IF; + EXIT WHEN "j" = "dimension_v"; + "j" := "j" + 1; + END LOOP; + EXIT WHEN "i" = "dimension_v"; + "i" := "i" + 1; + END LOOP; + "i" := 1; + LOOP + "j" := 1; + LOOP + IF "i" != "j" THEN + "k" := 1; + LOOP + IF "i" != "k" AND "j" != "k" THEN + IF "modified_matrix"["j"]["i"] < "modified_matrix"["i"]["k"] THEN + IF "modified_matrix"["j"]["i"] > "modified_matrix"["j"]["k"] THEN + "modified_matrix"["j"]["k"] := "modified_matrix"["j"]["i"]; + END IF; + ELSE + IF "modified_matrix"["i"]["k"] > "modified_matrix"["j"]["k"] THEN + "modified_matrix"["j"]["k"] := "modified_matrix"["i"]["k"]; + END IF; + END IF; + END IF; + EXIT WHEN "k" = "dimension_v"; + "k" := "k" + 1; + END LOOP; + END IF; + EXIT WHEN "j" = "dimension_v"; + "j" := "j" + 1; + END LOOP; + EXIT WHEN "i" = "dimension_v"; + "i" := "i" + 1; + END LOOP; + IF "modified_matrix"["m"]["n"] > "modified_matrix"["n"]["m"] THEN + "compare_matrix"["m"]["n"] := TRUE; + "compare_matrix"["n"]["m"] := FALSE; + EXIT; + ELSIF "modified_matrix"["m"]["n"] < "modified_matrix"["n"]["m"] THEN + "compare_matrix"["m"]["n"] := FALSE; + "compare_matrix"["n"]["m"] := TRUE; + EXIT; + ELSIF "modified_matrix"["m"]["n"] = "impossible_defeat_strength"() THEN + EXIT; + END IF; + END LOOP; + END IF; + EXIT WHEN "n" = "dimension_v"; + "n" := "n" + 1; + END LOOP; + EXIT WHEN "m" = "dimension_v" - 1; + "m" := "m" + 1; + END LOOP; + END IF; -- Determine order of winners: "rank_ary" := array_fill(NULL::INT4, ARRAY["dimension_v"]); "rank_v" := 1; @@ -3979,7 +4143,7 @@ IF "i" != "j" AND "rank_ary"["j"] ISNULL AND - "matrix"["j"]["i"] > "matrix"["i"]["j"] + "compare_matrix"["j"]["i"] THEN -- someone else is better EXIT; @@ -4039,7 +4203,7 @@ "better_than_status_quo" = "rank_ary"["i"] < "rank_ary"["dimension_v"], "worse_than_status_quo" = "rank_ary"["i"] > "rank_ary"["dimension_v"], "multistage_majority" = "rank_ary"["i"] >= "rank_ary"["dimension_v"], - "reverse_beat_path" = "matrix"["dimension_v"]["i"] >= 0, + "reverse_beat_path" = "path_matrix"["dimension_v"]["i"] >= 0, "eligible" = FALSE, "winner" = FALSE, "rank" = NULL -- NOTE: in cases of manual reset of issue state diff -r 7cad34b945ac -r 548cec6b7a79 test.sql --- a/test.sql Tue Sep 25 13:54:24 2012 +0200 +++ b/test.sql Sat Sep 29 23:41:37 2012 +0200 @@ -41,7 +41,8 @@ "issue_quorum_num", "issue_quorum_den", "initiative_quorum_num", "initiative_quorum_den", "direct_majority_num", "direct_majority_den", "direct_majority_strict", - "no_reverse_beat_path", "no_multistage_majority" + "no_reverse_beat_path", "no_multistage_majority", + "schulze_variant" ) VALUES ( 1, 'Default policy', @@ -49,7 +50,8 @@ 25, 100, 20, 100, 1, 2, TRUE, - TRUE, FALSE ); + TRUE, FALSE, + 'tie_breaking_with_negative_strength'::"schulze_variant" ); CREATE FUNCTION "time_warp"() RETURNS VOID LANGUAGE 'plpgsql' VOLATILE AS $$ @@ -118,10 +120,37 @@ (18, 'unit', 1, 19), (23, 'unit', 1, 22); +-- no delegations in area #1 +INSERT INTO "delegation" + ("truster_id", "scope", "area_id", "trustee_id") VALUES + ( 1, 'area', 1, NULL), + ( 2, 'area', 1, NULL), + ( 3, 'area', 1, NULL), + ( 4, 'area', 1, NULL), + ( 5, 'area', 1, NULL), + ( 6, 'area', 1, NULL), + ( 7, 'area', 1, NULL), + ( 8, 'area', 1, NULL), + ( 9, 'area', 1, NULL), + (10, 'area', 1, NULL), + (11, 'area', 1, NULL), + (12, 'area', 1, NULL), + (13, 'area', 1, NULL), + (14, 'area', 1, NULL), + (15, 'area', 1, NULL), + (16, 'area', 1, NULL), + (17, 'area', 1, NULL), + (18, 'area', 1, NULL), + (19, 'area', 1, NULL), + (20, 'area', 1, NULL), + (21, 'area', 1, NULL), + (22, 'area', 1, NULL), + (23, 'area', 1, NULL); + -- delegations for topics INSERT INTO "delegation" ("area_id", "truster_id", "scope", "trustee_id") VALUES - (1, 3, 'area', 17), + --(1, 3, 'area', 17), (2, 5, 'area', 10), (2, 9, 'area', 10), (3, 4, 'area', 14), @@ -236,6 +265,25 @@ (6, 9, 9), (6, 10, 10), (6, 11, 11); + +INSERT INTO "issue" ("area_id", "policy_id") VALUES + (1, 1); -- id 3 + +INSERT INTO "initiative" ("issue_id", "name") VALUES + (3, 'First initiative'), -- id 12 + (3, 'Second initiative'); -- id 13 + +INSERT INTO "draft" ("initiative_id", "author_id", "content") VALUES + (12, 1, 'Lorem ipsum...'), -- id 12 + (13, 2, 'Lorem ipsum...'); -- id 13 + +INSERT INTO "initiator" ("initiative_id", "member_id") VALUES + (12, 1), + (13, 2); + +INSERT INTO "supporter" ("initiative_id", "member_id") VALUES + (12, 1), + (13, 2); SELECT "time_warp"(); SELECT "time_warp"(); @@ -402,6 +450,25 @@ (20, 2, 10, -1), (20, 2, 11, 3); +INSERT INTO "direct_voter" ("member_id", "issue_id") VALUES + ( 1, 3), + ( 2, 3), + ( 3, 3), + ( 4, 3), + ( 5, 3); + +INSERT INTO "vote" ("member_id", "issue_id", "initiative_id", "grade") VALUES + (1, 3, 12, 1), + (1, 3, 13, 1), + (2, 3, 12, 1), + (2, 3, 13, 1), + (3, 3, 12, 0), + (3, 3, 13, 1), + (4, 3, 12, 0), + (4, 3, 13, -1), + (5, 3, 12, -1), + (5, 3, 13, -1); + SELECT "time_warp"(); DROP FUNCTION "time_warp"();