{"entities":{"Q2668498":{"pageid":2679241,"ns":120,"title":"Item:Q2668498","lastrevid":57986625,"modified":"2026-04-03T08:38:30Z","type":"item","id":"Q2668498","labels":{"en":{"language":"en","value":"Central limit theorem for majority dynamics: bribing three voters suffices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7485073"}},"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":"Q2668498$D3FF1AA4-56A6-44F3-8C83-7BAE49D345E2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"aef7209051721c165abc337cc8b00920da485859","datavalue":{"value":{"text":"Central limit theorem for majority dynamics: bribing three voters suffices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2668498$2C0795B7-6B1C-4253-8B31-4C10F4ECC75D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c6592790612c7ecd23a4f1764dbdb264c293de94","datavalue":{"value":"1489.60037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668498$BA495A7D-712D-4EF8-9212-B2AA3E557CF9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7b3c8a49523bea8c56ac6f31711e65bf27b124a5","datavalue":{"value":{"entity-type":"item","numeric-id":1650023,"id":"Q1650023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$D3A27A71-7274-4469-8984-0A5C5E85B975","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0bd858ef78cf376c53d5941213221f9f3b714286","datavalue":{"value":{"entity-type":"item","numeric-id":1621422,"id":"Q1621422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$D0AB20C4-BFD4-4860-B06F-815A370F37D4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0a7f38bff7197b9d5228d1d2cd340d5028d13b61","datavalue":{"value":{"entity-type":"item","numeric-id":61365,"id":"Q61365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$23D86EB9-175D-4BDF-AE99-F9E979786200","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5783a1d8b5962f0874bec2519202727b162b8e9","datavalue":{"value":{"time":"+2022-03-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2668498$25C67EC3-DA26-4122-984C-A1CC593BB7F5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"52d6c86e338fd517c0fc65785653a28517658640","datavalue":{"value":"https://arxiv.org/abs/2010.08172","type":"string"},"datatype":"url"},"type":"statement","id":"Q2668498$A11A6DA3-051A-48B8-B2DD-35935B2BB515","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e413990a385c695e9c8e97c5dff2b41be5f3f9c7","datavalue":{"value":"The theme of this paper is the analysis of majority dynamics on a random graph \\(G(n,p)\\), the binomial random graph on \\(n\\) vertices where each edge is present independently with probability \\(p\\). Majority dynamics is a synchronous process on the vertex set of a graph, where each vertex has two states \\(red\\) and \\(blue\\). The vertices are initially assigned there states and subsequently at each round, each vertex adopt the state of the majority of its neighbours (retaining its state in the case of a tie). The main theorem of the paper is a central limit theorem for the number of vertices which are \\(red\\) after the first round. This holds under certain assumptions on the difference \\(\\Delta\\) between the number of vertices that have been assigned \\(red\\) and the number of vertices that have been assigned \\(blues\\) initially. These assumptions hold, in particular, if \\(\\Delta p = O(\\sqrt{np(1-p})\\). Now, the central limit theorem implies that the number of vertices in \\(red\\) after one set is away from \\(n/2\\) with high probability. This, in turn, has implications on the evolution of majority dynamics. The authors provide sharpener bounds on the number of rounds needed until the process reaches unanimity: if \\(p = \\Omega(n^{-1/2})\\), at most four rounds are needed, but if \\(p = \\Omega (n^{-1/3})\\), at most three rounds are needed, whereas if \\(p\\) is close to 1 then at most two rounds are needed. A second application is a bound on the difference between the probabilities that the state at unanimity is \\(red\\) and the state at unanimity is \\(blue\\). The authors prove that if \\(\\Delta \\geq 3\\) (that is, there are at least 3 more red vertices than blue ones), then this difference is more than \\(1/2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2668498$BA7C4D13-5147-48FB-AB2F-BBD0B3370F0C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eee5ba7f50bd271f0d45cb8360d5c0d385d238ae","datavalue":{"value":{"entity-type":"item","numeric-id":490411,"id":"Q490411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$83F50AED-6AB6-4B8B-87D8-9B0D04C2C35B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"06501b652e368cc105ad78a5eac217e38c314cda","datavalue":{"value":"60F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668498$03AA661E-8758-4519-AF63-B4F5C1B17CFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668498$DA784886-19ED-489C-B4A4-9EE3F49835DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668498$FF529B88-8727-45D6-B8DB-7C08E2C173AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668498$9919A765-8A8C-4CEE-917A-7C6FF33A4B2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668498$9CF54007-2449-4D80-991B-05983A5EC4B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"757065528c65766745f2b30c6100b6592b67386c","datavalue":{"value":"7485073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668498$34E8E33B-1561-477D-AF5D-BA44C5FBE953","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c437ddb4614015ce261a7f9c77441c192c5d1fc3","datavalue":{"value":"majority dynamics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2668498$F319E469-451A-438F-A0E2-873D52295ECE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2668498$5188F714-46C1-426E-A846-08497FB432FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1196a5aae758f1f31a1e5375742e0ae7bf556dc4","datavalue":{"value":"central limit theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2668498$F4CABB16-68EC-40F5-8DA8-6E8BC8529996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d13c32acaec0f55aa8967614669667bc52cd8f80","datavalue":{"value":"Fourier analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q2668498$ABC97B9F-600E-4D7E-A321-28F424DD2BC5","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"32de3c69389f87ae089649462414d6c6041c0076","datavalue":{"value":"Q113863846","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668498$AC5191B6-6802-47EA-920B-135BBAEBC00B","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":"Q2668498$FB026E2D-D7A6-40ED-9AD9-7418342BA4E3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d8e86f8e2db85ad69a9ad81976d87189d3dea9c8","datavalue":{"value":"W4226049447","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668498$E0D0EFE1-B2E3-4F2C-AA06-F133E59F83A4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"75212c0824b25b88fd0835220459ca70ff5fb66e","datavalue":{"value":{"entity-type":"item","numeric-id":476295,"id":"Q476295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$08DE3821-DF85-427C-9AB9-F9E077078ACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89ad2976b7b20b1ef2a98eedbf9c7cd827ba1327","datavalue":{"value":{"entity-type":"item","numeric-id":4219778,"id":"Q4219778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$C15D0882-8229-490E-B08E-3031ED887BFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"819087ab375ee3b5d842277bc8e9fffc2495d7fd","datavalue":{"value":{"entity-type":"item","numeric-id":3419621,"id":"Q3419621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$9BAA3EDA-5CF5-443C-8DD4-9A518017BD41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dc88ca020b08395542a1570e58236a96c477b0f","datavalue":{"value":{"entity-type":"item","numeric-id":737177,"id":"Q737177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$AFA45B9A-5859-4BCC-899B-54B3E5C18C38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3346612bec2c519b9a8166d7f96d9a3d4f1105fa","datavalue":{"value":{"entity-type":"item","numeric-id":1863055,"id":"Q1863055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$FF2C5A72-682F-4592-8D0A-DDF8121830BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3020041010eb027c66e342bfef639adcbfefd9ac","datavalue":{"value":{"entity-type":"item","numeric-id":2941798,"id":"Q2941798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$D223AE2C-7C30-47BE-BF41-EA1920020487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e9f3f2ad2726a66375a54b7879bdd2bc1a7347e","datavalue":{"value":{"entity-type":"item","numeric-id":3386530,"id":"Q3386530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$0726D9CF-0DB9-4B8D-AC15-C56E15E49CBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d4813efb7ced1629b4aecac1913fe1aa3cfaa0c","datavalue":{"value":{"entity-type":"item","numeric-id":5739013,"id":"Q5739013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$07AF5557-E4B8-4D06-A23C-FEADDF3E2152","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"351811d5405b7218b1b3b978484bd8055c0bb8a7","datavalue":{"value":{"entity-type":"item","numeric-id":2294715,"id":"Q2294715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$FECF435B-7AB3-4281-AC9F-9FE30332D29B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae617289d65eb0fc29f699efe14aaa35ed5b7ac6","datavalue":{"value":{"entity-type":"item","numeric-id":1974519,"id":"Q1974519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$B79FCF26-FFCC-4A49-A6B2-2EEB04C1FA3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e3965090100d7ebe690c3d08b5eafc93d604ebb","datavalue":{"value":{"entity-type":"item","numeric-id":1145126,"id":"Q1145126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$F493460C-DFEC-4738-9C60-8BAEB5F48EDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d852aa4510f13f25aa3497fcd0c95ad2f6f8281","datavalue":{"value":{"entity-type":"item","numeric-id":655579,"id":"Q655579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$A6A433E1-DBA5-42F3-9F3C-0E200F861703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"574a6599f545ec08b9afa71a7573eae29e700904","datavalue":{"value":{"entity-type":"item","numeric-id":5166888,"id":"Q5166888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$8F7070AF-CFCA-4337-9613-8CD1C8686344","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29e9dc966b60c3a195ba5206f76d8b506f1fd96e","datavalue":{"value":{"entity-type":"item","numeric-id":3400007,"id":"Q3400007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$D34E4FC5-381D-4983-AFC7-C253CF8DE328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56aa0a6553c9bd7bb931ba5fe2767b186a8b18d9","datavalue":{"value":{"entity-type":"item","numeric-id":2339621,"id":"Q2339621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$CFB08AF3-4C70-4C03-8857-ADDD857939FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64b43c93ecdc1d6ac4a38a98e1db3e30611cf180","datavalue":{"value":{"entity-type":"item","numeric-id":2306607,"id":"Q2306607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$CB1F9FE6-28A5-4270-8475-82436DCB6533","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9be9ca5f3744db1f7339cc547b9f6d5808a85ead","datavalue":{"value":{"entity-type":"item","numeric-id":2416425,"id":"Q2416425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668498$59B863D2-6689-4677-9F95-830D9D8D8527","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"26b88d50fa66273aedb166dd5cc4b9b67e3db5b9","datavalue":{"value":"10.1016/J.SPA.2022.01.010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668498$02460EB6-898A-4949-8819-99CA7C929320","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc43f3c2d00cf1f4ed4516af566137f3f7621e82","datavalue":{"value":{"entity-type":"item","numeric-id":3386530,"id":"Q3386530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe863570c41e381a8a94840301856b6a6d5b0e4e","datavalue":{"value":{"amount":"+0.8479293584823608","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2668498$8434769F-EE1C-4806-A63D-0DC9313353B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b221d091abeff350e04539b710c708a5dfecf87f","datavalue":{"value":{"entity-type":"item","numeric-id":6074720,"id":"Q6074720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65ad858ad43790a84147f363b1dfc58c708dd494","datavalue":{"value":{"amount":"+0.8154857158660889","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2668498$FAB19CD3-AD10-4114-BBF0-8C634B93926A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b66a56e7b9827d1946182524acaee7b65105126","datavalue":{"value":{"entity-type":"item","numeric-id":2038874,"id":"Q2038874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82d527ec833ae08550c9af63036f0474aeed708a","datavalue":{"value":{"amount":"+0.8113614320755005","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2668498$895C5C85-D622-4FC2-BD80-653B334D73CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a60d3d7fc2aeada427d4c551f87fbd0430df6d87","datavalue":{"value":{"entity-type":"item","numeric-id":655579,"id":"Q655579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21555ef417e029f2eaa65f63712e0cbfedfacaa6","datavalue":{"value":{"amount":"+0.7967238426208496","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2668498$91B1EE4D-9942-456A-BCFF-8587383DB223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b9d1f9907370c84018ae2de03123d9b92547d06","datavalue":{"value":{"entity-type":"item","numeric-id":2294715,"id":"Q2294715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d58014620c7ebe598c86698ade234093cff96da5","datavalue":{"value":{"amount":"+0.7937449812889099","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2668498$FCD45EF4-CA6A-4755-924F-647FB1DE60DA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2668498","badges":[]}}}}}