{"entities":{"Q7361739":{"pageid":31520756,"ns":120,"title":"Item:Q7361739","lastrevid":105368444,"modified":"2026-10-07T13:37:30Z","type":"item","id":"Q7361739","labels":{"en":{"language":"en","value":"The Impossibility of Strategyproof Rank Aggregation"}},"descriptions":{"en":{"language":"en","value":"AFP entry SWF_Impossibility"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ba5515932041bdea36557a122a5569c83769371c","datavalue":{"value":"https://isa-afp.org/entries/SWF_Impossibility.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361739$9515ABD7-34C3-478B-9D49-985A7A0CD493","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ed0acfea66d72dabedf8248efd6bd273a34db1fe","datavalue":{"value":{"time":"+2026-01-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361739$94D06C8E-8A39-4DEB-957D-A934FF9B77EB","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"85859c7ab42dcb8b36208f2902b7ce0d86423a6f","datavalue":{"value":"Manuel Eberl","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361739$8AC804D3-D79D-4624-967E-ABB7545CB8E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"658707ce60fe264e97f0213bc47c6fec5e2b788c","datavalue":{"value":"Patrick Lederer","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361739$27618E0E-5F9B-4047-9AD3-A8477BE58CED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"049cf0f847e6047a2a69c000d5bd6f9b46af7a61","datavalue":{"value":{"text":"The Impossibility of Strategyproof Rank Aggregation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361739$1B32DE9A-E60A-4416-B70E-42046BECCFC2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cb75efaca159451156442f47e6db2bf575b92390","datavalue":{"value":"In Social Choice Theory, a social welfare function (SWF) is a function that takes a collection of individual preferences on some set of alternatives and returns an aggregated preference relation. More formally: Consider finite sets of agents $N=\\{1,\\ldots,n\\}$ and alternatives $A=\\{x_1,\\ldots,x_m\\}$. The input of an SWF is an $n$-tuple of rankings (i.e. linear orders) of $A$, and its output is a ranking of $A$ as well. Various desirable properties on SWFs can be defined: Anonymity: The SWF is invariant under permutation of the agents. Unanimity: If all voters prefer $x$ over $y$, then $x$ is preferred over $y$ in the output ranking as well. Majority consistency: If there exists a ranking $x_1, \\ldots, x_{m}$ such that for every $i < j$, the alternative $x_i$ is preferred over $x_j$ by more than half of the agents, that ranking must be returned. Kemeny strategyproofness: Strategic voting is not possible for a single agent, i.e. no agent can achieve a result more aligned with their own preferences by lying about them. This entry contains two impossibility results for SWFs with $m$ alternatives and $n$ agents: There exists no anonymous, unanimous, and Kemeny-strategyproof SWF for $m \\geq 5$ and $n$ even or for $m = 4$ and $n$ a multiple of 4. There exists no majority-consistent and Kemeny-strategyproof SWF for $m = 4$ and $n \\geq 3$ or $m \\geq 4$ and $n \\in \\{9,11,13,15\\}\\cup\\{17,\\ldots\\}$ For some of the base cases, SAT solving is used by letting specialised automation prove a large number of clauses, translating to the DIMACS format, and importing a proof pre-generated by an external SAT solver using Lammich's GRAT format.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361739$4C3063CD-4D33-474B-8966-DB3E9816E366","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"191734449ceba4bc2a76e944da27595387f6a747","datavalue":{"value":{"entity-type":"item","numeric-id":3194802,"id":"Q3194802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361739$E8E9CA0E-D11F-40FC-B9FB-9A640789B833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb081c24d3f308759ffc5be25d93bb06a52b464f","datavalue":{"value":{"entity-type":"item","numeric-id":3192088,"id":"Q3192088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361739$0855EAF1-6F51-4927-A15A-2FCFE3AE3B7B","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361739$839D03B3-6B43-4C05-8AA8-70D8BE9FEA31","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"23b35e6ffc791e9d46a75ab0d481fa4c8ff08b1f","datavalue":{"value":{"entity-type":"item","numeric-id":7361285,"id":"Q7361285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361739$F58762EB-EF6A-47C2-A12F-578433982DE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"57eeb3b04ded3edf35853c1054a458e38b1f5b77","datavalue":{"value":{"entity-type":"item","numeric-id":7361572,"id":"Q7361572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361739$9E22305D-CCBC-4D98-8EC9-050CA816AC7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"e16c709524206234166dabd2c2b7202ee37ec525","datavalue":{"value":{"entity-type":"item","numeric-id":7361034,"id":"Q7361034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361739$64D21189-C80D-4CB9-AA17-2C31B0BE1AC8","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"a72569ac3fa7d166ec3d63a25d7f4970dd09f6f6","datavalue":{"value":{"entity-type":"item","numeric-id":7360825,"id":"Q7360825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361739$468DE81A-F52F-440A-BD3A-16ECC11DAF01","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361739$6ABC44F5-0F18-4E81-AE3F-990AC3F773E3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Impossibility of Strategyproof Rank Aggregation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_Impossibility_of_Strategyproof_Rank_Aggregation"}}}}}