{"entities":{"Q452827":{"pageid":454594,"ns":120,"title":"Item:Q452827","lastrevid":61944513,"modified":"2026-04-11T02:43:16Z","type":"item","id":"Q452827","labels":{"en":{"language":"en","value":"The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6083221"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$E901176A-094D-4775-A42E-4A4805B293A1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7596aab7349a8fe3df070a4e8b85ebdd4d9d61d9","datavalue":{"value":{"text":"The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q452827$D4278C4B-97B1-4A4C-9C07-96BCB4E62858","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"443e1b7ceeb9e2b7d62286064b41287c60eb4c06","datavalue":{"value":"1265.05015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452827$EC24F132-6EE5-44DC-992E-1D5956BCD3BC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5594791a57b5299ec0b07582be3ae5a61bacab56","datavalue":{"value":{"entity-type":"item","numeric-id":452826,"id":"Q452826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$30806294-0987-4389-950D-FEDF392363BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b30ea4be0bda84f0ec06cd91b0280b36fe9cbe91","datavalue":{"value":{"entity-type":"item","numeric-id":430832,"id":"Q430832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$7E300ADD-8BE5-4343-8FEB-0364C30B4FEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"95e03469b8abf1198e8e71d89e5f9540ea9718d3","datavalue":{"value":{"entity-type":"item","numeric-id":185102,"id":"Q185102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$1FA38C13-4938-4FC9-A990-97373BE86FDE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$0208BC94-B83F-4090-B0B2-2DD01A931BFD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"67ab5997c5787a1d1df744683e2ae7c1996b5996","datavalue":{"value":{"time":"+2012-09-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q452827$AF391CCF-5EEF-4DA7-A7AE-A178E3037C64","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"47fd2f401babee438c9411e676d666e60b97606c","datavalue":{"value":"https://arxiv.org/abs/0911.0517","type":"string"},"datatype":"url"},"type":"statement","id":"Q452827$58398CB0-8F83-4C61-AEA8-9795B958391C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2edf5bb39a9b8e727ce71682e3be46c55b476168","datavalue":{"value":"The paper is concerned with the manipulability of social choice functions. A social choice function is a function that operates on the rankings of a number of alternatives (say \\(q\\)) given by a number of voters (say \\(n\\)). It is manipulable if there is a voter that given the votes of the other voters can change his vote such that the outcome of the social choice function changes in his favour. A known Theorem of \\textit{A. Gibbard} [Econometrica 41, 587--601 (1973; Zbl 0325.90081)] and \\textit{M. A. Satterthwaite} [J. Econ. Theory 10, 187--217 (1975; Zbl 0315.90088)] states that any social choice function taking at least three values and not being a dictator function (i.e. the result of the choice function does not depend solely on the ranking of one voter only) is manipulable. This still leaves open questions concerning the complexity of finding a manipulator. In this paper the authors restrict theirselves to neutral choice functions, i.e. choice functions where the result does not depend on the names of the alternatives. They give lower bounds on the number of manipulation points in a neutral social choice function operating on more than four alternatives that is bounded away from the set of dictators. A rough lower bound is obtained by applying the Gibbard-Satterthwaite Theorem in combination with the method of cannonical paths. By refining the arguments finally a lower bound is reached that is polynomial in \\(1/q\\) showing that it is not too difficult to find manipulation points.","type":"string"},"datatype":"string"},"type":"statement","id":"Q452827$3D7B1E67-CC03-4ADA-9E0B-395D08B2FF6F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"82ee0e57d3fff232270389401ab1bbddfcf580b6","datavalue":{"value":{"entity-type":"item","numeric-id":592369,"id":"Q592369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$8EA6A10B-466E-4265-81D6-2A4C580D553C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452827$4ED98EAB-C412-4D00-B739-2DD24958FAD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c965de5e9a4b8d63068ca456eb6ad48746668aea","datavalue":{"value":"91B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452827$28DB4B85-00D0-49AA-895F-AB3962ECC213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824cfdf2b129d72f7287008060b5bf497f3b4f34","datavalue":{"value":"91B14","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452827$430CF57E-0D75-4B63-8488-45641D54A903","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"51b6d88bc172e80d98306e50298c500a36126c79","datavalue":{"value":"6083221","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452827$4C6C5920-05DD-4DFA-915A-38A9E5D5360C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8cf4bb625de430910848edaf1b02f03400c8c03f","datavalue":{"value":"social choice function","type":"string"},"datatype":"string"},"type":"statement","id":"Q452827$4707BB52-0ED3-470A-9A07-92A34FB092A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fdacefc867629918b68b0f82f5f86726fb20d41e","datavalue":{"value":"voting system","type":"string"},"datatype":"string"},"type":"statement","id":"Q452827$A2FA0AC5-EA63-4E91-9086-720723AD54AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"abdb80009ae8c3bddbe047bb3a79c15913e6e949","datavalue":{"value":"dictator","type":"string"},"datatype":"string"},"type":"statement","id":"Q452827$9D51FBD8-87D6-437B-A6AA-110C6EA01A64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1286954518fc0ab796d3e770c95cf6828fc3abec","datavalue":{"value":"manipulability","type":"string"},"datatype":"string"},"type":"statement","id":"Q452827$768B2F78-5606-4DA9-A2CA-76C3414E6D6B","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$EABDE244-4956-40FD-8FC7-0F34E4C6F421","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"373a0eb9dce34aa7867abcfed8c8a6778fdeb956","datavalue":{"value":"W2177286302","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452827$03D668DE-E7F3-4B78-9763-B23F6B581A01","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"be32dd08355b219aedae9f7f550e12f7b99bb0b6","datavalue":{"value":{"entity-type":"item","numeric-id":1120433,"id":"Q1120433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$094B8654-4494-4DE5-9A1B-6998B952E8A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5331d5ec5886443c0d80c3bfcf1631abc4665a76","datavalue":{"value":{"entity-type":"item","numeric-id":2457626,"id":"Q2457626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$431108BC-AB9F-47E1-9D40-4E06C58E2235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb51d202edc4bc3837632c901f7c7c61d30ea89c","datavalue":{"value":{"entity-type":"item","numeric-id":5897854,"id":"Q5897854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$D4D4EECF-A34E-4B7F-BA43-7310E7D4CFFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c70fd9026cd6411e893674389783cb361acfa96","datavalue":{"value":{"entity-type":"item","numeric-id":4090165,"id":"Q4090165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$BF21E2CC-5B2F-446F-AC4E-211DD146BA25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2609b2df0c96ae8ecc10f80b1112aaba3f058fa6","datavalue":{"value":{"entity-type":"item","numeric-id":4038711,"id":"Q4038711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$BF02B2E4-52F3-48CF-9063-3F1445109724","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c96446c4bde102daa1090c648f25a77145a8e394","datavalue":{"value":{"entity-type":"item","numeric-id":2365784,"id":"Q2365784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$92759838-7E03-4EAC-8A5C-DE2ABBAE5F06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2739206b76c02befb9f80c4ff7990435f1220e54","datavalue":{"value":{"entity-type":"item","numeric-id":1221568,"id":"Q1221568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$2F81102B-A0B1-48F3-861C-348F823EB6C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6058f7b186fa21835f7286abefe4dab3ecddfa75","datavalue":{"value":{"entity-type":"item","numeric-id":1431558,"id":"Q1431558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452827$FBD1A9D8-929F-44F2-B8D3-68A43D4A9827","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"85f0450d42e6b5f3ef4f1572c941ee8a5fa8020e","datavalue":{"value":"10.1007/S00493-012-2704-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452827$3AB65990-B121-4669-AFE5-263FBE47CB87","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b757c71805ddb157cb20827b0e75c2826300deb2","datavalue":{"value":{"entity-type":"item","numeric-id":3598403,"id":"Q3598403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6d5252a21936c31038503fc61f787565003c170","datavalue":{"value":{"amount":"+0.8335763","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q452827$A1D78F1A-1B2A-4D4C-83FE-80BB143B755A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbbdb8abe7f2c517c4f0ddcced4c8cb1fc6e11f4","datavalue":{"value":{"entity-type":"item","numeric-id":997202,"id":"Q997202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08380fbe81dec18bb076928028b2ae23b976e0c5","datavalue":{"value":{"amount":"+0.8249825","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q452827$BED08359-2F3A-413B-888F-837793F56096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e45145bbe08894dd4020adf9aa98689a38f3f8b","datavalue":{"value":{"entity-type":"item","numeric-id":2386337,"id":"Q2386337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8fcf9c3ff2199023a8990f323ac85d6cd5f0002a","datavalue":{"value":{"amount":"+0.8230159","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q452827$B79B40F1-E8F9-4D19-8810-08F59D4C84CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a91b8759387dcd3e74b4febbab056bff071daa1","datavalue":{"value":{"entity-type":"item","numeric-id":2367165,"id":"Q2367165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"832fca26979db6c885c61d13f7cc1cd376288ff5","datavalue":{"value":{"amount":"+0.8217749","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q452827$5268A2D6-610F-4686-A95F-AB45D9B449EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1f9bade8b6e3ffb3658134b610da87d37151f07","datavalue":{"value":{"entity-type":"item","numeric-id":1124505,"id":"Q1124505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac7d475422caec4dc14e1b4559583c7c16c8effd","datavalue":{"value":{"amount":"+0.8181299","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q452827$F0B305E8-D4A1-40DE-9C64-752259B2FAC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"443af4304b697f05ca89825f7616cf9e2b217f6c","datavalue":{"value":{"entity-type":"item","numeric-id":2334835,"id":"Q2334835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86adfde8fbbcdae16ac7301ae68835a2f4c70618","datavalue":{"value":{"amount":"+0.81605875","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q452827$66AC1292-DBEB-4A80-A268-B70C2401BB01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f83caf68adc9a3956d883861491f9e5f51ae5ca0","datavalue":{"value":{"entity-type":"item","numeric-id":1863937,"id":"Q1863937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b02af3414930e99e7a6e1f5ff49c9485fc63cb6a","datavalue":{"value":{"amount":"+0.81115836","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q452827$4F4729AD-3C7E-472C-819D-1DDD8B1102D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b32ae1199a81a15ee8f0c09e1309890300be4d0f","datavalue":{"value":{"entity-type":"item","numeric-id":334204,"id":"Q334204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb4e3a7aa8ac0d95c78dd7feb5990dfc1d5a3a3f","datavalue":{"value":{"amount":"+0.80964684","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q452827$BB8CCAAE-B42F-4E8A-8A3D-41013189F0CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"293ffd5f247c79ac7161f4c121467951733df2f3","datavalue":{"value":{"entity-type":"item","numeric-id":1824523,"id":"Q1824523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3be4161e1ab96a525a54743c61db4f00a815270a","datavalue":{"value":{"amount":"+0.8083863","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q452827$FF765708-CC04-449D-AEAF-CB77FF960444","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_geometry_of_manipulation_--_a_quantitative_proof_of_the_Gibbard-Satterthwaite_theorem"}}}}}