{"entities":{"Q1961037":{"pageid":1971779,"ns":120,"title":"Item:Q1961037","lastrevid":82103024,"modified":"2026-05-06T20:06:32Z","type":"item","id":"Q1961037","labels":{"en":{"language":"en","value":"An algorithm for super envy-free cake division"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1389242"}},"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":"Q1961037$364299BC-9576-4136-996F-3EA15B3B46B9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7c436f75b790a652d6744cb148a2f82eb1efc659","datavalue":{"value":{"text":"An algorithm for super envy-free cake division","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1961037$A21F9ACA-9E0A-44A2-B3FE-B96AD2B94075","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2ed4bcb3716277a39cd3ba1bd99f935832cc27d8","datavalue":{"value":"0948.28006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961037$E850CF12-BECB-4D32-895E-1873C74DE96B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e512bb606b982ff914879158e1c02c4a077ebd3c","datavalue":{"value":{"entity-type":"item","numeric-id":677612,"id":"Q677612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$90F786DF-8DBC-4C70-B542-FAB209E8319F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c5ad7b9baf8e531c6b1ad954eb5f2899cc8fe5e5","datavalue":{"value":{"entity-type":"item","numeric-id":85344,"id":"Q85344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$D3846D52-90B5-462C-8CB4-0C76EF4D5F43","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"45c6b522baf77e7131b262008cde5ff0fa2a03f4","datavalue":{"value":{"time":"+2000-11-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1961037$2B1483D1-523B-4FA1-99F0-6B7E17C972CA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5b3ecee2208fce1ea86754540a2e3f94be6c6426","datavalue":{"value":"Let \\(\\mu_1,\\dots,\\mu_n\\) be nonatomic probability measures on a set \\(X\\). A partition of \\(X\\) into subsets \\(X_1,\\dots,\\) \\(X_n\\) is called super envy-free if \\(\\mu_i(X_i)>1/n\\) for each \\(i\\) and \\(\\mu_i(X_j)<1/n\\) whenever \\(j\\neq i\\). \\textit{J. B. Barbanel} showed [J. Math. Anal. Appl. 197, No. 1, 54-60 (1996; Zbl 0857.90019)] that a super envy-free allocation exists if and only if the measures are linearly independent.    This paper gives a finite algorithm for finding a super-envy-free allocation if it exists. The number of steps required depends on the measures. As initially presented, the algorithm assumes the availability of a ``witness'' to the independence of the measures -- that is, sets \\(A_1,\\dots,A_n\\) that make \\((\\mu_i(A_j))\\) non-singular. With additional assumptions, the required witness can be found as part of the finite algorithm.    This paper is the authority for section 10.4 in the book ``Cake-cutting algorithms. Be fair if you can'', by \\textit{J. Robertson} and \\textit{W. Webb} [A. K. Peters, Natick, Massachusetts (1998)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961037$5EA381BC-1CC1-4FB9-BBB5-627C435B756F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c7de4dc0d2b34b063c61971b509a1933e43f4fa2","datavalue":{"value":"28B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961037$40BF1EE5-25AE-48F4-903D-6FBF9B9D13EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3783afd39b9a4c0ecdd0e6ac842f765284c23884","datavalue":{"value":"91B32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961037$33156C4A-2E66-4D3B-BA0A-753075A6C419","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"16a41880afbd8630e6acc78be050f90ea5608911","datavalue":{"value":"05A18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961037$E3A9454F-EE4E-48A3-B027-38C9617EA623","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8e210403bf62613d9109dd88508110a78eb1f3ee","datavalue":{"value":"1389242","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961037$BA9422BE-E600-4328-8C4E-329F18F84542","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c4a2006afe68d5c7328600561667aa14c56881f","datavalue":{"value":"cake division","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961037$00D628F2-FDD4-44D2-90E9-A285DFA3BE7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3388289d592fe5f4b88e95ab758a446cf6e8b2b7","datavalue":{"value":"fair division","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961037$B8DE0EF1-2EF0-4501-9856-A69955A16BFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c08a0a4f4eb310725e1d2a1f47b26cb57845056","datavalue":{"value":"envy-free partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961037$E1E97E0A-F242-4010-8071-273D5E6998BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb7d8e296001658c753e2d90414dabeafac29959","datavalue":{"value":"nonatomic probability measures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1961037$BCB0AB1B-EAD9-4B76-8143-1535ECB44A8D","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":"Q1961037$9D97E4EA-6FBB-4E32-BBF0-40B6BB3C7FED","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"218029d61486029535265c8c021433bd15924707","datavalue":{"value":"https://doi.org/10.1006/jmaa.1999.6581","type":"string"},"datatype":"url"},"type":"statement","id":"Q1961037$5BE15231-E624-4BF6-B51A-CC874EA9CF39","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a63ee710f48d1c03d671ec13d4a2a0c2bf6bebe6","datavalue":{"value":"W1989218403","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961037$9F7B7028-0EFF-49DC-BEE0-86B83DDD23A0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4089587ed7b59f2c58a2d2638a9ee02ba2827133","datavalue":{"value":{"entity-type":"item","numeric-id":4853044,"id":"Q4853044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$76A192C4-A6A8-44C3-B2B4-F54E6686576E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8eb1950dc1161fa800918f949bf916c27ef2a74","datavalue":{"value":{"entity-type":"item","numeric-id":1916698,"id":"Q1916698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$BD834FEF-34CF-43CC-A27D-4E1AF315FA0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da9f578c81f1865c94dd527badc2f8cb01fdd377","datavalue":{"value":{"entity-type":"item","numeric-id":3837575,"id":"Q3837575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$D831C86A-7244-46C1-BDEA-7A62DDF03E14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46ab963f46672fc97d1b105d6f66fdce3eca25eb","datavalue":{"value":{"entity-type":"item","numeric-id":4845929,"id":"Q4845929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$18D387F9-3959-41B0-8886-45A57C1E367C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f579d5a5f37c7b45384c39359af8049eb23650a2","datavalue":{"value":{"entity-type":"item","numeric-id":4698451,"id":"Q4698451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$245BD2C4-516F-47D1-8A8E-5031DC00151A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99cc14e8210475ba6de6b39bd848ff67719b69b1","datavalue":{"value":{"entity-type":"item","numeric-id":1347261,"id":"Q1347261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$D12F6388-2F91-407E-98D2-9D0DFC4122C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e77d7f768c9e6e010305af81b887666761a4126a","datavalue":{"value":{"entity-type":"item","numeric-id":4338900,"id":"Q4338900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$04FEC1DF-BDFB-48E1-A49A-00441D95922F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5174f6485fdcbdeb5c69f9cc8856054f388f46f9","datavalue":{"value":{"entity-type":"item","numeric-id":1903417,"id":"Q1903417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$5CCEC5C9-48A5-4107-B927-4E5711DAEEA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb324982a0359ed73d1e87ddb60ed30aeb11a16e","datavalue":{"value":{"entity-type":"item","numeric-id":4332981,"id":"Q4332981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$8EF5C9A3-17D8-478C-AA66-501B7F753979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec9cc8d6da4d6a910f6206f79f6375b8d668f91b","datavalue":{"value":{"entity-type":"item","numeric-id":3844704,"id":"Q3844704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$4CFE7FF6-91B5-4FF0-B165-2ED4A6E5A656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11967d9717319013098bd62c77f065b56dd0a2db","datavalue":{"value":{"entity-type":"item","numeric-id":595538,"id":"Q595538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$92762886-FDBC-417B-9A12-D05D3E68E5D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c0c13ee90e6badeb989c6794b0ac13cf5a049c7","datavalue":{"value":{"entity-type":"item","numeric-id":5340475,"id":"Q5340475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$BE65F2ED-8FE4-492D-8C03-CC9146C7058F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b26f0df0686cd3ddbd06f6ccdae2b7470e7cffa9","datavalue":{"value":{"entity-type":"item","numeric-id":3981356,"id":"Q3981356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$14DF6603-6EAE-4A5C-A710-BB7AACDCEA48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b02a7aad2f854ce5497e688a7cf512f5046099d0","datavalue":{"value":{"entity-type":"item","numeric-id":1903017,"id":"Q1903017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$A22436C4-D64E-4C30-BA1C-32FEB9CDE118","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2dfc969e0a3824c3b45114b078ecba7c9cb4716","datavalue":{"value":{"entity-type":"item","numeric-id":677613,"id":"Q677613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$D5D28B94-2FF5-42D4-BA0D-F4EDBAA65A72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbfa819ad88fee1f6a8129e92e7583ae04286b78","datavalue":{"value":{"entity-type":"item","numeric-id":4940018,"id":"Q4940018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$1E452539-89B6-424B-8DB3-5DD540884C8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eaa224c00a01867ceda043a3c3fa19dc4744ba6b","datavalue":{"value":{"entity-type":"item","numeric-id":5799067,"id":"Q5799067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$04A2D393-7257-454D-884C-D0E9E44423C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"938ab5e3b71630a63eb7b431703af1e040200e03","datavalue":{"value":{"entity-type":"item","numeric-id":3883835,"id":"Q3883835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$E99046F1-9559-47BC-AF7D-202EFF5AAE3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03718608b89a351684645e2517b7f79f33c2c05c","datavalue":{"value":{"entity-type":"item","numeric-id":1088802,"id":"Q1088802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$8F80BA62-69FA-4405-9B44-13DEAD022EDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ee7d0c01c2fb770fe8f41d985360a23dc020faa","datavalue":{"value":{"entity-type":"item","numeric-id":1356520,"id":"Q1356520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$22823EA7-816B-4795-9812-EFA3543D95A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d852a2a919cc0f298e5f32bf44ef3e59c7620a12","datavalue":{"value":{"entity-type":"item","numeric-id":1160300,"id":"Q1160300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$8E2F864D-38AB-44B5-BEEE-98715BE5B51D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e4658092d276097368558adcd5e6e696b75160d","datavalue":{"value":{"entity-type":"item","numeric-id":1075937,"id":"Q1075937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1961037$07FEDE55-2CD6-4FF4-B305-1B3E597F2F7B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"03a3de6c3372175702531953975b27290c3dd990","datavalue":{"value":"10.1006/JMAA.1999.6581","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1961037$F3720E09-1C04-4EAD-8B19-F3ED9C77D940","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b3f939a80a1c0a30f5eb2e70b13597c320db3b1","datavalue":{"value":{"entity-type":"item","numeric-id":1916698,"id":"Q1916698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bfd07c8aed871e139599a42d27f887a57d55250","datavalue":{"value":{"amount":"+0.92001473903656","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":"Q1961037$6E015236-9D5D-4B06-8805-3F333041440C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bf9eb091d776e28a9c107e3452c7a505e85ab53","datavalue":{"value":{"entity-type":"item","numeric-id":4940018,"id":"Q4940018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3f7d5c679e69b68de46a9525c004b3299fc50bc","datavalue":{"value":{"amount":"+0.8515068292617798","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":"Q1961037$3FD01C50-E0FE-484E-8B32-305A839E5F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01e8db60f5ceb702f110131d25decc56e76ab93e","datavalue":{"value":{"entity-type":"item","numeric-id":1625485,"id":"Q1625485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ae13aa46360f1bc6b9d9dbd049dd667e7356678","datavalue":{"value":{"amount":"+0.8409193754196167","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":"Q1961037$3B5A902F-632A-4D64-9DA0-9BC3F2E9FB20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c1af1e63f4dfdd74dad7b43a026ef9faff64a83","datavalue":{"value":{"entity-type":"item","numeric-id":4698451,"id":"Q4698451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d4b0b109d1496d8fda71e05922019aa3eec2516","datavalue":{"value":{"amount":"+0.8408748507499695","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":"Q1961037$0C992811-9B82-4C3D-A6D8-16B8B332F0D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f735198469cea1d3a10eea856d067f7b0acc670","datavalue":{"value":{"entity-type":"item","numeric-id":1290667,"id":"Q1290667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8c58f0d13a0f815117e8d56fcf6648e5498c258","datavalue":{"value":{"amount":"+0.8393465876579285","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":"Q1961037$F30C5C37-6187-4BF2-A30C-7612874B47FD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An algorithm for super envy-free cake division","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_algorithm_for_super_envy-free_cake_division"}}}}}