İki genç bilgisayar bilimci, matematikçileri on yıllardır meşgul eden bir problemi çözdüler. Hasetsiz (İng.: envy-free) paylaşım problemi, en basit örneğiyle, bir kekin istenilen kişiye eşit bir şekilde paylaştırılması, öyle ki kimsenin gözünün diğerinin payında kalmaması. Kişi sayısı iki olduğu zaman ve homojen bir kek üzerinde, bir kişinin keki kesmesi, diğerinin de seçmesi, yani Böl ve Seç algoritması hasetsiz, adil paylaşıma bir örnek. İncil’de de yer alan bu hasetsiz ikiye paylaşma yöntemi özellikle iki kardeş arasında adil paylaşım için, sayısız ailede kardeşler tarafından yeniden keşfedilmiştir.
Problemin bilgisayar bilimciler için önemi, daha genel haliyle günlük hayatta birçok pratik uygulamasının karşımıza çıkmasından kaynaklanıyor. Paylaşılan şey her cm2’si eşit özelliklere sahip olan bir kekin aksine homojen olmayabilir; mesela kekin üzerindeki şekerden süslü kısım daha fazla veya az cazip olabilir ya da bir arazideki ormanlık bölgenin varlığı ya da bir apartman dairesini paylaşacak öğrencilerin odaların şerefiyesine göre ödeyecekleri toplam kiraya katkıları veya vardiyalara işin eşit dağılımı, ancak gece ve gündüz vardiyalarının farklı zorlukta olması, vb. Bu gibi paylaşım problemlerinde kimsenin gözünün diğerinin payında kalmaması, hasetsiz paylaşım olarak adlandırılıyor.Bu tarz paylaşım-çekişme problemleri, ekonomide oyun teorisi başlığı altında da inceleniyor.
HASETSİZ ÜÇE BÖLME ALGORİTMASI
1960’da kekin üç eşit parçaya hasetsiz paylaşımı problemi Selfridge-Conway algoritması ile çözüldü. Keki paylaşacak üç kişi Ali, Berk ve Canan olsun ve bu üç kişi de algoritmanın her adımını biliyor olsun. Ali keki üç parçaya böler. Berk gözüne kestirdiği bir parçayı (ona en büyük görünen parçadan) bir parçasını keser, yani 3’e eşit bölme işlemini, kendince biraz daha eşit hale getirir. Canan bu 3 + minik kısımdan kendisi için bir parça seçer. Daha sonra Berk ve saha sonra da Canan alır. Sıra minik kısmın paylaşımına gelmiştir. Minik kısmın paylaşımında bu sefer tersten Canan’a 3’e kesmesi önerilir ve ana kekin 3’e paylaşımı protokolü tekrarlanır. Eğer Canan minik kısmın paylaşımı protokolünün başlatıcısı olmazsa Berk, o da istemezse Ali olur. Bu protokol (üç kişi arasındaki paylaşım adımları) ile kimsenin bir diğerinin payında gözü kalmıyor.
Ancak bilgisayar bilimcileri ve matematikçilerin 50 senelik çabası, problemin genel halinin yani, ’sınırlı adımda kekin n eşit parçaya bölünmesi’ olarak tarif ettikleri probleme dair bir algoritma geliştirilemeyeceğine dair bir kanı oluşturmuştu. 20. yüzyılın önemli açık/çözülmemiş matematiksel problemlerinden birisi olarak gösterilen bu problem üzerine araştırmacılar çalışmaya devam etti. 1998’de Robertson ve Webb’in çalışmaları kek paylaşımı probleminde hasetsiz paylaşımın temel problem olduğunu belirtirken, sadece kek üzerindeki kesim sayısını değil bir kişinin bir dilimi ne kadar değer verdiğini de bir ‘sorgulama’ olarak değerlendirdiler. Değerlendirme ve kesim iki farklı sorgulama. Kesim sorgulamasında ise kişi sol tarafı sabit olacak şekilde, belli bir değerde bir dilim belirlemesi (kesmesi) isteniyor. Bu model literatürdeki tüm protokolleri kapsıyor.
GENEL PROBLEMİN ÇÖZÜMÜ
2016’da ise Avustralya’da çalışan iki genç bilgisayar bilimci R büyüklüğündeki keki, hasetsiz bir şekilde n eşit parçaya bölecek bir algoritma tasarladılar. Daha önce, 2014’de 4 kişi arasında hasetsiz paylaşım problemini çözen araştırmacılar, bu çözümlerine yeni kavramlar ve teknikler ekleyerek n kişilik genel çözüme ulaşmışlar. Bu iki araştırmacı, protokolde kullanılan sorgulamalar açısından Robertson ve Webb modelini referans aldılar. n kişilik algoritma beş farklı protokolün birbiri ile iletişimi şeklinde çalışıyor:
Ana protokol kendisini veya üç farklı protokolü çağırıyor. Her protokol farklı işlevleri olan bir algoritma olarak düşünülebilir. Ana protokolün (Main Protocol) girdisi R büyüklüğündeki kek ve N kümesi. Çıktısı ise R birimin N (n kişilik bir küme) arasındaki hasetsiz paylaşımı. Çekirdek protokolün (Core Protocol) girdisi (N kümesi içinden) belirli bir kişi ve bölüşülmemiş R büyüklüğündeki kek. Çıktısı ise R’ ⊂ R olacak şekilde hasetsiz paylaşım. Altçekirdek protokol (Subcore Protocol) girdisi n parçaya ayrılmış R büyüklüğündeki kekin N’ (N′ ⊂ N şeklinde) n’ kişiye (n’ ayrılma işi. Çıktısı ise R büyüklüğündeki kekin N’ kümesine (|N’| = n’) hasetsiz bir şekilde kısmen bölüştürülmesi.
Bu algoritmanın hasetsiz olduğu, tıpkı 3’e paylaşım algoritması gibi matematiksel olarak ispatlanmış. Gereken sorgulama sayısının en fazla 
. Bu oldukça hızlı büyüyen bir sayı. Ancak, araştırmacılar makalede, protokol sonuna kadar götürülmese bile, 
sorgulamada kısmi bir paylaşım yapılabildiği ve bu kısmi paylaşımın her n kişinin kekin en az 1/n’ini aldığı ve hasetsiz olduğunu gösteriyorlar.
Araştırmacılarla yapılan söyleşideki ilginç bir detay ise, bu konuda on yıllardır çalışanların aksine problemi görece yeni çalışmaya başladıkları ve bu nedenle de araştırmada kimi önyargılardan, ya da düşünsel tuzaklardan azade olduklarını belirtmeleri oldu.
Kaynak:
1. Hariz Aziz and Simon Mackenzie, “A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents”, arXiv:1604.03655v10 [cs.DS] 5 Oct 2016.