Kıskanç kek kesme - Envy-free cake-cutting

Bir kıskanç kek kesme bir çeşit adil pasta kesme. Bu, heterojen bir kaynağın ("kek") bir bölümüdür. kıskanç kriter, yani her ortağın kendi sübjektif değerlemelerine göre, kendilerine tahsis edilen paylarının en az diğer paylar kadar iyi olduğunu hissetmesi.

Soru, Web Fundamentals.svgBilgisayar biliminde çözülmemiş problem:
Kıskançlık içermeyen pasta kesmenin çalışma zamanı karmaşıklığı nedir?
(bilgisayar biliminde daha fazla çözülmemiş problem)

Yalnızca iki ortak olduğu zaman, sorun kolaydır ve İncil dönemlerinde tarafından çözülmüştür. böl ve seç protokol. Üç veya daha fazla ortak olduğunda, sorun çok daha zorlu hale gelir.

Sorunun iki ana çeşidi incelenmiştir:

  • Bağlı parçalar, Örneğin. pasta 1 boyutlu bir aralıksa, o zaman her bir ortak tek bir alt aralık almalıdır. Eğer varsa sadece ortaklar kesintilere ihtiyaç var.
  • Genel parçalar, Örneğin. pasta 1 boyutlu bir aralıksa, o zaman her bir ortak, ayrık alt aralıkların bir birleşimini alabilir.

Kısa tarih

Modern araştırma adil pasta kesme sorun 1940'larda başladı. İncelenen ilk adalet kriteri şöyleydi: orantılı bölme ve bir prosedür için n ortaklar yakında bulundu.

Daha güçlü kriter kıskançlık kek kesme problemine, George Gamow ve Marvin Stern 1950'lerde.[1]

Bir üç ortak ve genel parçalar için prosedür 1960 yılında bulundu. Üç ortak ve bağlantılı parçalar için bir prosedür sadece 1980'de bulundu.

Dört veya daha fazla ortak için kıskançlıktan uzak bölüm, 1990'lara kadar açık bir problemdi. genel parçalar için üç prosedür ve bağlı parçalar için bir prosedür yayınlandı. Tüm bu prosedürler sınırsız - önceden sınırlandırılmamış birkaç adım gerektirebilirler. Bağlı parçalar için prosedür, bir sonsuz adım sayısı.

Kıskançlıktan özgürlüğün çalışma zamanı karmaşıklığına ilişkin iki alt sınır 2000'lerde yayınlandı.

2010'larda birkaç yaklaşık prosedürler ve özel durumlar için prosedürler yayınlandı. Genel davalar için sınırlı süreli prosedürlerin var olup olmadığı sorusu uzun süre açık kalmıştı. Sorun nihayet 2016'da çözüldü. Haris Aziz ve Simon Mackenzie, en çok ihtiyaç duyan, kıskançlık içermeyen ayrı bir protokol sundu. sorguları. Alt sınır ile prosedür arasında hala çok büyük bir boşluk var. Ağustos 2016 itibarıyla, kıskançlıktan uzak olmanın tam çalışma zamanı karmaşıklığı hala bilinmemektedir.

Bağlı parçalar durumunda, sertlik sonucunun tüm pastanın bölünmesi gerektiğini varsaydığı kaydedildi. Bu gereksinim, her ortağın bir orantılı değer (en az 1 /n toplam kek değerinin kendi değerlemesine göre), sonra üç ortak için sınırlı bir prosedür bilinmektedir ancak dört veya daha fazla ortak için sınırlı süreli prosedürlerin olup olmadığı açık bir sorun olarak kaldı.

Bağlı parçalar

Varlık kanıtı

Kıskançlıktan uzak bir bölüm n Bağlantılı parçalara sahip aracılar her zaman aşağıdaki hafif varsayımlar altında var olur:[2]

  • Hiçbir temsilci boş olmayan bir parçayı boş bir parçaya tercih etmez.
  • Ajanların tercihleri ​​süreklidir.

Unutmayın ki değil temsilcilerin tercihlerinin bir katkı işlevi.

İspattaki ana kavram, basit bölümlerin. Pastanın [0,1] aralığı olduğunu varsayalım. Bağlı parçalara sahip her bölüm benzersiz şekilde temsil edilebilir. n - [0,1] 'de kesim konumlarını temsil eden 1 sayı. Tüm bölümlerin birleşimi tek yönlüdür.

Her bölüm için, her ajan zayıf bir şekilde tercih ettikleri bir veya daha fazla parçaya sahiptir. Örneğin, "0.3,0.5" ile temsil edilen bölüm için, bir aracı 1 numaralı parçayı (parça [0,0.3]) tercih ederken, başka bir aracı 2 numaralı parçayı (parça [0.3,0.5]), üçüncü bir aracı ise hem 1 numaralı parçayı hem de 2 numaralı parçayı tercih edebilir (bu, aralarında kayıtsız oldukları ancak herhangi biri gibi 3. parçadan daha fazla oldukları anlamına gelir).

Her ajan için, bölüm simpleksi şu kapsamdadır: n parçalar, muhtemelen kendi sınırlarında üst üste biner, öyle ki kısmen tüm bölümler için benajan parçayı tercih ediyor ben. Parçanın iç kısmında benajan tercih ediyor sadece parça benparçanın sınırındayken benajan ayrıca başka parçaları da tercih ediyor. Yani her biri için benbölme simpleksinde en az bir ajanın yalnızca parçayı tercih ettiği belirli bir bölge vardır. ben. Bu bölgeyi ara Uben. Belirli bir topolojik lemma kullanma (bu, Knaster – Kuratowski – Mazurkiewicz lemma ), tümünün kesişme noktasının olduğunu kanıtlamak mümkündür. Uben's boş değil. Dolayısıyla, her parçanın bir temsilcinin benzersiz tercihi olduğu bir bölüm vardır. Parça sayısı temsilci sayısına eşit olduğundan, her parçayı onu tercih eden acenteye tahsis edebilir ve kıskanç bir tahsis alabiliriz.

Prosedürler

Üç temsilci için, birkaç farklı prosedür kullanılarak kıskanç bir bölüm bulunabilir:

Bunlar sürekli prosedürlerdir - bıçakları sürekli ve aynı anda hareket ettiren insanlara güvenirler. Sonlu sayıda ayrık adımda yürütülemezler.

İçin n ajanlar, kıskanç bir bölüm tarafından bulunabilir Simmons'ın pasta kesme protokolü. Protokol bir bölümlerin simpleksi Stromquist'in varoluş kanıtında kullanılana benzer. Kıskançlık içermeyen bir bölüme yakınsayan bir bölüm dizisi oluşturur. Yakınsama sonsuz sayıda adım atabilir.

Tüm bu algoritmaların sonsuz sayıda sorgu gerektirmesi bir tesadüf değildir. Aşağıdaki alt bölümde gösterdiğimiz gibi, sınırlı sayıda sorguya sahip birbirine bağlı parçalarla kıskançlık içermeyen bir pasta kesimi bulmak imkansız olabilir.

Sertlik sonucu

Sonlu bir protokolle 3 veya daha fazla aracı için bağlantılı parçaların olduğu kıskanç bir bölüm bulunamaz.[3] Bu sonucun daha önce bahsedilen algoritmalarla çelişmemesinin nedeni, matematiksel anlamda sonlu olmamasıdır.[4]

İmkansızlık kanıtı bir katı ölçü sistemi (RMS) - bir sistem n kıskanç bir bölümün pastayı çok özel yerlerde kesmesi gereken değer ölçüleri. Daha sonra, kıskanç bir bölüm bulmak, bu belirli yerleri bulmaya indirgenir. Pastanın gerçek aralık [0,1] olduğunu varsayarsak, ajanlara yapılan sorguları kullanarak kıskanç bir bölme bulmak, evet / hayır sorularını kullanarak [0,1] aralığında gerçek bir sayı bulmaya eşdeğerdir. Bu, sonsuz sayıda soru gerektirebilir.

Üç ajan için bir RMS aşağıdaki gibi oluşturulabilir. İzin Vermek x, y, s, ve t tatmin edici parametreler olmak:

Bu iki özelliğe sahip bir dizi üç ölçü oluşturun:

  1. Her ölçünün yoğunluğu her zaman kesinlikle 2/ 2 ve 2 (bu nedenle, belirli bir parça için, temsilcilerin değerlemeleri 2'den küçük bir faktörle farklılık gösterir).
  2. Parçaların değerlerini belirleyen x ve y tablodaki gibidir:
Ajan[0,x][x,y][y,1]
Birtts
Bstt
Ctst

Sonra, Alice Bob ve Carl arasındaki kıskançlıktan uzak her bölüm, x ve y (tam olarak böyle iki bölüm vardır), çünkü diğer tüm seçenekler kıskançlığa yol açar:

  • Solunda kesikler yapılırsa x ve sağında y, sonra Alice ve Bob ortadaki parçayı almakta ısrar ediyor.
  • Sağında kesim yapılırsa x ve solunda y, o zaman hiçbir temsilci ortadaki parçayı kabul etmez.
  • Sağında kesim yapılırsa x ve sağında y (söyle x *>x ve y *>y), sonra hem Alice hem de Carl en soldaki parçayı en sağdaki parçaya tercih ederler, bu yüzden Bob en sağdaki parçayı kabul etmelidir. Bu, Bob'un parçaya değer vermesi gerektiği anlamına gelir [x,x *] en az iki katı [y,y *]. Ancak değer yoğunluklarındaki kısıtlama nedeniyle, bu hem Alice hem de Carl'ın [x,x *] daha fazla [y,y *], böylece en soldaki parça üzerinde ısrar ediyorlar.
  • Dördüncü vaka (sol taraftaki x ve solunda y) benzerdir.

Her RMS için her ajan ben ve her sabit ε> 0, aşağıdaki özelliklere sahip biraz farklı bir RMS vardır:

  • Temsilcinin yeni değer ölçüsü ben eski değer ölçüsü ile tamamen aynıdır;
  • Diğer iki ajanın yeni değer ölçüleri, her yerde eski değer ölçüleri ile aynıdır. dışında ε mahallesinde x ve y.

Bu, şimdiye kadar yanıtlanan tüm sorgular, ε- mahallesi x ve y, sonra ajan ben eski RMS'de mi yoksa yeni RMS'de mi olduğumuzu bilmenin bir yolu yok.

Bu bilgiyle donatılmış bir rakip, kıskançlıktan uzak her bölünme protokolünü sonsuza dek devam ettirmek için kandırabilir:

  1. Herhangi bir RMS ile başlayın, ör. parametrelerle x = 1/3, y = 2/3, s = 0.3 ve t = 0.35.
  2. Protokol dışındaki noktalarda kesintiler yaptığı sürece x ve ydevam etmesine izin ver.
  3. Protokol aracıya sorduğunda ben kesmek x veya yile farklı bir RMS'ye geçin x '≠ x ve y '≠ y, daha önce yapılan tüm kesimler için değerlerin aynı olduğundan emin olun.

Böylece protokol asla doğru şekilde kesinti yapamaz. x ve y kıskanç bir bölüm için gerekli.

Yaklaşımlar

Bağlı parçalarla gıpta etmeden kek kesme işlemi sınırlı bir sürede yapılamadığından, kek kesiciler geçici çözümler bulmaya çalıştı.

Çözümlerden biri, yalnızca neredeyse kıskanç. Yaklaşımı tanımlamanın iki yolu vardır - birimleri cinsinden uzunluk veya birimlerinde değer.

Uzunluğa dayalı yaklaşım aşağıdaki tanımları kullanır:

  • Bir bölüm bir pastanın n oluşturduğu aralıkların uzunlukları. Yani (0.2,0.5,0.3), birim aralığın 0.2, 0.5 ve 0.3 uzunluklarında üç alt aralığa bölünmesidir (birim aralığın 0.2 ve 0.7'de kesilmesiyle oluşturulur).
  • Bir çok bölümlü birkaç farklı bölümden oluşan bir settir.
  • Çok bölümlü X adı verilir kıskanç ortakların her biri için bir permütasyonu varsa ben, bir X öğesi vardır öyle ki ben-nci ortak tercih eder ben-inci segment.
  • Bir δ-çok bölümlü her bölüm çifti için koordinatlarının her biri arasındaki farkın en fazla olduğu çok bölümlüdür δ. Örneğin: {(0.2+δ,0.5,0.3), (0.2,0.5+δ,0.3), (0.2,0.5,0.3+δ)}.

Parametre δ ortakların uzunluk birimleri cinsinden toleransını temsil eder. Örneğin, arazi bölünmüşse ve ortaklar, sınırın konumunda 0.01 metrelik bir farkın kendileriyle ilgili olmadığı konusunda hemfikir ise, gıpta edilmeyen 0,01 çok bölmeli bir bölme aramak mantıklıdır. Diğerinde Deng[5] bir değişiklik sunmak Simmons'ın pasta kesme protokolü kıskanç bulan δ-multi-partition kullanarak sorguları. Dahası, daha düşük bir sınır olduğunu kanıtlıyorlar sorguları. Fayda fonksiyonları polinom zaman algoritmaları tarafından açıkça verildiğinde bile, kıskanç kek kesme problemi PPAD -tamamlayınız.

Değere dayalı yaklaşım aşağıdaki tanımları kullanır:

  • X bölümü denir ε kıskançlık içermeyen ortakların her biri için bir permütasyonu varsa bendeğeri ben-inci parça artı ε en az herhangi bir parçanın değeri kadar: .
  • Bir değer ölçüsü denir Lipschitz-sürekli sabit varsa K öyle ki, herhangi bir aralık çifti için, aralarındaki değer farkı en fazla K simetrik farklarının uzunluğunun katı .

Tüm değer ölçüleri Lipschitz-sürekliliği ise, iki yaklaşım tanımı birbiriyle ilişkilidir. İzin Vermek . Sonra kıskanç bir şekilde her bölüm δ-multi-partition ε-envy içermez.[5] Dolayısıyla, Deng ve diğerlerinin sonuçları, tüm ortakların Lipschitz-sürekli değerlemelerine sahip olması durumunda, ε-envy içermeyen bölüm ile bulunabilir sorguları.

Çevrimdışı hesaplama tamamen kıskanç bir bölüm bulan, ancak yalnızca sınırlı bir değerleme sınıfı için ikinci bir çözümdür. Tüm değer ölçüleri en fazla derece polinomları ise d, içinde polinom olan bir algoritma var n ve d.[6] Verilen dalgoritma aracılara sorar d+1 değerlendirme sorguları, dDeğer ölçüsünün grafiğindeki +1 puan. Biliniyor ki d+1 puan, bir derece polinomunu enterpolasyon için yeterlidir d. Bu nedenle, algoritma tüm aracıların tüm değer ölçülerini hesaplayabilir ve çevrimdışı olarak kıskanç bir bölünme bulabilir. Gerekli sorgu sayısı .

Değerlemelerle ilgili bir başka kısıtlama da, parçalı sabit - her temsilci için en fazla m istenen aralıklar ve ajanın her aralıktaki değer yoğunluğu sabittir. Bu varsayım altında, bağlı kıskançlık içermeyen bir tahsis, çözülerek bulunabilir. doğrusal programlar. Böylece ne zaman n sabittir, sorun polinomdur m. [7]

Ücretsiz bertaraf bölümün tamamen gıpta edilmemesi ve tüm değer ölçüleri için işe yaraması gerekliliğini koruyan, ancak tüm pastanın bölünmesi gerekliliğini ortadan kaldıran üçüncü bir çözümdür. Yani, pastanın bir alt kümesini bölmeye ve kalanını atmaya izin verir. Daha fazla gereksinim olmaksızın, sorun önemsizdir, çünkü tüm aracılara hiçbir şey vermemek her zaman kıskançtır. Bu nedenle, gerçek amaç, her bir temsilciye kesinlikle pozitif bir değer vermektir. Her kek tahsisi, seviyesiyle karakterize edilebilir. orantılılık, bu en az şanslı ajanın değeridir. Tüm pastanın kıskançlıktan uzak bir bölümü de bir orantılı bölme ve orantılılık seviyesi en az , bu mümkün olan en iyisidir. Ancak özgürce elden çıkarılmaya izin verildiğinde, kıskançlık içermeyen bir bölüm daha düşük bir orantılılık düzeyine sahip olabilir ve amaç, mümkün olan en yüksek orantılılığa sahip kıskançlık içermeyen bir bölüm bulmaktır. Şu anda bilinen sınırlar şunlardır:

  • 3 temsilci için orantılılık yani kıskanç ve orantılı bölünme sınırlı zamanda elde edilebilir.[8]
  • 4 temsilci için orantılılık .[8]
  • İçin n ajanlar, orantılılık .[9]

Bağlı parçaları olan dört veya daha fazla ortak için sınırlı süreli, kıskançlık içermeyen ve orantılı bir bölme prosedürü olup olmadığı bilinmemektedir.

Varyantlar

Bağlı parçalarla kek kesme işlemlerinin çoğu, kekin 1 boyutlu bir aralık olduğunu ve parçaların 1 boyutlu alt aralıklar olduğunu varsayar. Çoğunlukla, parçaların kare gibi belirli bir geometrik şekle sahip olması istenir. Bu tür kısıtlamalarla, tüm pastayı bölmek imkansız olabilir (örneğin, bir kare iki kareye bölünemez), bu nedenle serbest bırakmaya izin vermeliyiz. Açıklandığı gibi yukarıda, serbest bertarafa izin verildiğinde, prosedürler onların seviyelerine göre ölçülür. orantılılık - tüm aracılara garanti ettikleri değer. Aşağıdaki sonuçlar şu anda bilinmektedir:[10]

  • Kare bir pastayı paylaşan ve kare parçalar isteyen iki ortak için orantılılık ve bu kıskançlık olmadan bile garanti edilebilecek en iyisidir.
  • Kare bir pastayı paylaşan ve kare parçalar isteyen üç ortak için orantılılık ; kıskanmadan garanti edilebilecek en iyi şey .

Bağlantısız parçalar

Prosedürler

Üç ortak için, Selfridge – Conway ayrık prosedür en fazla 5 kesinti ile kıskanç bir bölünme yapar. Hareketli bıçak kullanan diğer prosedürler daha az kesim gerektirir:

Dört ortak için, Brams – Taylor – Zwicker prosedürü en fazla 11 kesinti ile kıskanç bir bölünme yapar.[12] Beş ortak için, Saberi ve Wang'ın bir prosedürü, sınırlı sayıda kesinti ile kıskanç bir bölünme yaratır.[13] Her iki prosedür de kullanır Austin'in iki ortak ve genel kesirler için prosedürü ilk adım olarak. Bu nedenle, bu prosedürler sonsuz olarak kabul edilmelidir - sınırlı sayıda adım kullanılarak tamamlanamazlar.

Dört veya daha fazla ortak için, sonlu ancak sınırsız olan üç algoritma vardır - gerekli kesim sayısında sabit bir sınır yoktur.[14] Bu tür üç algoritma vardır:

  • Brams-Taylor protokolü, ilk olarak 1995 tarihli bir makalede ve daha sonra 1996 tarihli bir kitapta yayınlandı.
  • Robertson – Webb protokolü, ilk olarak 1997 tarihli bir makalede ve daha sonra 1998 tarihli bir kitapta yayınlandı.
  • Pikhurko protokolü,[15] 2000 yılında yayınlandı.

Protokoller farklı olsa da, arkasındaki ana fikir benzer: Pastayı, her biri o kadar küçük olan ve tüm ortaklar için değeri ihmal edilebilir olan sınırlı sayıda ancak sınırsız sayıda "kırıntıya" bölün. Ardından, istenen bölümü elde etmek için kırıntıları sofistike bir şekilde birleştirin. William Gasarch, üç sınırsız algoritmayı karşılaştırdı. sıra sayıları.[16]

Dört veya daha fazla ortak için kıskançlık içermeyen kek kesiminin sınırlı bir sürede yapılıp yapılamayacağı sorusu uzun yıllardır açıktı. Sonunda 2016 yılında Hariz Aziz ve Simon Mackenzie tarafından çözüldü. Başlangıçta dört ortak için sınırlı zamanlı bir algoritma geliştirdiler.[17] Ardından, algoritmalarını herhangi bir sayıda ortağı işleyecek şekilde genişlettiler.[9] Algoritmaları en çok sorguları. Bu sayı sınırlı olmakla birlikte, alt sınırından çok uzaktır. . Yani kıskançlık içermeyen kek kesmek için kaç sorgu gerektiği sorusu hala açık.

Yaklaşımlar ve kısmi çözümler

Bir son küçültücü protokolün evresel varyantı Sınırlı zamanda kıskançlık içermeyen bir bölünmeye toplamsal bir yaklaşım bulur. Özellikle, her sabit için , her ortağın değerinin en azından en büyük değer eksi olduğu bir bölüm döndürür , zamanında .

Tüm değer ölçüleri Parçalı doğrusaldeğer fonksiyonlarının temsilinin boyutunda polinom olan bir algoritma vardır.[18] Sorgu sayısı , nerede değer yoğunluğu fonksiyonlarının türevlerindeki süreksizliklerin sayısıdır.

Sertlik sonucu

Kıskançlık içermeyen her prosedür n insanlar en az Ω (n2) sorguları.[19] Kanıt, algoritmanın her bir ortak hakkında sahip olduğu bilgi miktarının dikkatli bir analizine dayanır.

A. Pastanın 1 boyutlu aralık [0,1] olduğunu ve ortakların her biri için tüm pastanın değerinin normalleştirildiğini varsayın 1. Her adımda, algoritma belirli bir ortağa ya değerlendirmek [0,1] içinde bulunan belirli bir aralık veya işaret belirli bir değere sahip bir aralık. Her iki durumda da, algoritma yalnızca uç noktaları sorguda veya yanıtta belirtilen aralıklar hakkında bilgi toplar. Bunlara uç noktalar diyelim görülecek yer. Başlangıçta tek simgesel yapı ben 0 ve 1'dir çünkü algoritmanın ortak hakkında bildiği tek şey ben bu mu vben([0,1]) = 1. Algoritma ortak sorarsa ben [0.2,1] aralığını değerlendirmek, ardından yanıtın ardından önemli noktalar ben {0,0.2,1}. Algoritma hesaplayabilir vben([0,0.2]), ancak bitiş noktası 0.2'den farklı olan herhangi bir aralığın değeri değil. Yer işaretlerinin sayısı her sorguda en fazla 2 artar. Özellikle [0,0.2] aralığının değeri, tamamen 0'a yakın veya tamamen 0.2'ye yakın veya bunların arasında herhangi bir yerde yoğunlaşabilir.

B. Partnerin ardışık iki yer işareti arasındaki aralık ben denir dönüm noktası aralığı partnerin ben, Algoritma ortağa bir parça kek ayırmaya karar verdiğinde ben, toplam değeri için bir parça tahsis etmelidir ben en az herhangi bir dönüm noktası aralığı kadar büyük ben. Kanıt çelişkidir: Farz edin ki belirli bir dönüm noktası aralığı vardır J kimin değeri ben gerçekte tahsis edilen değerden daha fazlasıdır ben. Başka bir ortak, söyle j, mutlaka dönüm noktası aralığının bir kısmını alacaktır J. A paragrafına göre, aralığın tüm değerlerinin J ortağa tahsis edilen pay içinde yoğunlaşır j. Böylece, ben kıskançlık j ve bölüm kıskanç değildir.

C. Tüm ortakların tüm soruları yanıtladığını varsayalım sanki değer ölçüleri tek tiptir (yani bir aralığın değeri uzunluğuna eşittir). B paragrafına göre, algoritma ortağa bir parça atayabilir ben, yalnızca tüm dönüm noktası aralıklarından daha uzunsa ben. En azından n/ 2 ortaklar, en fazla 2 / uzunluğunda bir aralık almalıdırn; dolayısıyla tüm dönüm noktası aralıklarının uzunluğu en fazla 2 /n; dolayısıyla en azından sahip olmaları gerekir n/ 2 dönüm noktası aralığı; dolayısıyla en azından sahip olmaları gerekir n/ 2 önemli nokta.

D. Ortak tarafından cevaplanan her sorgu ben en fazla iki yeni uç noktayı içerir, bu nedenle yer işaretlerinin sayısını artırır ben en fazla 2. Bu nedenle, C paragrafında açıklanan durumda, algoritma şunu sormalıdır: n/ En az 2 ortak n/ 4 sorgu. Dolayısıyla toplam sorgu sayısı en az n2/ 8 = Ω (n2).

Varlık kanıtları ve çeşitleri

Yukarıda açıklanan algoritmaların ima ettiği genel varoluş kanıtlarına ek olarak, ek özelliklere sahip kıskanç bölümlerin varlığına dair kanıtlar vardır:

Her iki kanıt da yalnızca eklemeli ve atomik olmayan değer ölçüleri için çalışır ve her bir ortağa çok sayıda bağlantısız parça verme yeteneğine dayanır.

Farklı haklara sahip kıskançlıktan uzak bölüm

Kıskançlıktan arındırma kriterinin ortak bir genellemesi, ortakların her birinin farklı bir yetkiye sahip olmasıdır. Yani her ortak için ben bir ağırlık var wben kekin almaya hak kazandıkları bölümünü açıklayarak (tümünün toplamı) wben 1'dir). Daha sonra ağırlıklı kıskançlık içermeyen bölüm şu şekilde tanımlanır. Her ajan için ben değer ölçüsü ile Vbenve diğer her ajan için j:

Yani, her ortak, haklarına göre tahsisatlarının en az diğer ortağın haklarına göre diğer tahsisler kadar büyük olduğunu düşünür.

Tüm ağırlıklar aynı olduğunda (ve 1 / 'e eşit olduğunda)n), bu tanım kıskançlığın standart tanımına indirgenir.

Parçaların bağlantısı kesildiğinde, ağırlıklı, kıskançlık içermeyen bir bölüm her zaman vardır ve Robertson-Webb protokolü, herhangi bir ağırlık seti için. Zeng, daha az sayıda kesim gerektiren yaklaşık ağırlıklı gıpta içermeyen bölme için alternatif bir algoritma sundu.[20]

Ancak parçaların birleştirilmesi gerektiğinde, ağırlıklı kıskançlık içermeyen bir bölüm olmayabilir. Bunu görmek için, her ağırlıklı kıskançlık içermeyen bölümün aynı zamanda ağırlıklı orantılı aynı ağırlık vektörü ile; bu, her ajan için ben değer ölçüsü ile Vben:

Bağlı parçalarla ağırlıklı orantılı tahsisin olmayabileceği bilinmektedir: bkz. farklı haklara sahip orantılı pasta kesme Örneğin.

Ağırlıklı kıskançlık içermeyen bölümün, ağırlıkların atandığı alternatif bir tanım olduğunu unutmayın. adet ajanlardan ziyade. Bu tanımla, aşağıdaki durumlarda ağırlıklı kıskançlık içermeyen bir bölümün var olduğu bilinmektedir (her durum bir önceki durumu genellemektedir):

'Kötü' bir pastayı bölmek

Bazı durumlarda, bölünecek "kek" negatif bir değere sahiptir. Örneğin, biçilmesi gereken bir çim parçası veya temizlenmesi gereken bir çorak arazi olabilir. O halde pasta, "heterojen bir iyi" olmaktan ziyade "heterojen bir kötü" dür.

Kıskançlık içermeyen kek kesmeye yönelik bazı prosedürler, kötü bir kek için işe yarayacak şekilde uyarlanabilir, ancak adaptasyon genellikle önemsiz değildir. Görmek kıskançlık içermeyen angarya bölümü daha fazla ayrıntı için.

Özet tablolar

Sonuca göre özet
İsimTürKekAdet
#ortaklar (n)
#sorguları#cutsimrenme
orantılılık[24]
Yorumlar
Böl ve seçAyrık procHiçBağlandı221 (en uygun)Yok1/2
StromquistHareketli bıçak procAralıkBağlandı32 (en uygun)Yok1/3
Selfridge – ConwayAyrık procHiçBağlantı kesildi395Yok1/3
Brams – Taylor – ZwickerHareketli bıçak procHiçBağlantı kesildi411Yok1/4
Saberi-Wang[13]Ayrık procHiçBağlantı kesildi4SınırlıSınırlıYok1/4Ücretsiz bertaraf
Aziz-Mackenzie[17]Ayrık procHiçBağlantı kesildi4203584Yok1/4
Saberi-Wang[13]Hareketli bıçak procHiçBağlantı kesildi5SınırlıYok1/5
StromquistVaroluşAralıkBağlandınn-1Yok1/n
SimmonsAyrık procAralıkBağlandınn-1Yok1/n
Deng-Qi-SaberiAyrık procAralıkBağlandınn-1Katkı Yalnızca değerlemeler Lipschitz-sürekliliği olduğunda
Branzei[6]Ayrık procAralıkBağlandın?Yok1/nYalnızca değer yoğunlukları en fazla derece ile polinom olduğunda d.
Atık-Acele EdiyorAyrık procAralıkBağlandı394Yok1/3Ücretsiz bertaraf
Atık-Acele EdiyorAyrık procHiçBağlandı4166Yok1/7Ücretsiz bertaraf
Atık-Acele EdiyorAyrık procHiçBağlandınYokÜcretsiz bertaraf
Aziz-Mackenzie Bağlantılı Parçalar [9]Ayrık procHiçBağlandınYokÜcretsiz bertaraf
Brams-TaylorAyrık procHiçBağlantı kesildinSınırsızSınırsızYok1/n
Robertson-WebbAyrık procHiçBağlantı kesildinSınırsızSınırsızYok1/nAğırlıklı kıskançlıktan uzak.
Pikhurko[15]Ayrık procHiçBağlantı kesildinSınırsızSınırsızYok1/n
Aziz-Mackenzie[9]Ayrık procHiçBağlantı kesildinYok1/n
Yeniden giriş son küçültücüAyrık procAralıkBağlantısızn?Katkı 1/n
Kurokawa-Lai-Procaccia[18]Ayrık procAralıkBağlantısızn?Yok1/nYalnızca değer yoğunlukları en fazla ile parça parça doğrusal olduğunda k süreksizlikler.
WellerVaroluşHiçBağlantı kesildinYok1/nPareto verimli.
2 boyutluAyrık procMeydanBağlı ve Kare222Yok1/4Ücretsiz bertaraf
2 boyutluHareketli bıçak procMeydanBağlı ve Kare36Yok1/10Ücretsiz bertaraf

Temsilci sayısı ve parça türüne göre özet:

# aracıBağlı parçalarGenel parçalar
2Böl ve seç
3Stromquist hareketli bıçak prosedürü (sonsuz zaman);
Çöpler acele eder (sınırlı süreli, sınırlı kesimler, serbest bertaraf, orantılı)
Selfridge – Conway ayrık prosedür (sınırlı süreli, en fazla 5 kesim).
4Çöpler acele eder (sınırlı zaman, sınırlı kesimler, serbest bertaraf, orantılılık 1/7).Brams – Taylor – Zwicker hareketli bıçak prosedürü (sonsuz zaman, en fazla 11 kesim).
Saberi – Wang ayrık prosedürü[13] (sınırlı zaman, sınırlı kesimler, serbest bertaraf, orantılı).
Aziz-Mackenzie ayrık prosedür[17] (sınırlı zaman, sınırlı kesimler, orantılı).
5Saberi-Wang hareketli bıçak prosedürü[13] (sonsuz zaman, sınırlı kesimler).
nSimmons'ın protokolü (sonsuz zaman)
Deng-Qi-Saberi (yaklaşık olarak kıskanç, üstel zaman).
Çöpler acele eder (tamamen kıskanç, üstel zaman, serbest bırakma, üstel orantılılık)
Aziz-Mackenzie Bağlantılı Parçalar [9] (tamamen kıskanç, üstel zaman, serbest bırakma, doğrusal orantılılık)
Brams ve Taylor (1995);
Robertson ve Webb (1998).
- Her iki algoritma da sınırlı ancak sınırsız sayıda kesim gerektirir.

Aziz-Mackenzie ayrık prosedür[9] (sınırlı zaman, sınırlı kesimler, orantılı).

Sertlikİçin tüm algoritmalar n ≥ 3 sonsuz olmalıdır (Stromquist, 2008).Tüm algoritmalar en azından kullanmalıdır Ω (n2) adımlar (Procaccia, 2009).
VaryantlarKeyfi ağırlıklar için ağırlıklı kıskançlıktan uzak bir bölüm mevcuttur (İdzik, 1995),
pasta ve parçalar simpleks olsa bile (Idzik ve Ichiishi, 1996),
ve hatta eklemeli olmayan tercihlerle (Dall'Aglio ve Maccheroni, 2009).
Robertson-Webb, keyfi ağırlıklar için ağırlıklı kıskançlık içermeyen bölümler bulabilir.
Bir mükemmel bölüm mevcuttur (Dubins & Spanier, 1961).
Kıskanç ve verimli kek kesme var (Weller teoremi ).

Ayrıca bakınız

Dış bağlantılar

  • Adil Bölünme Hesaplayıcı - Pastalar, ev işleri, odalar ve kiralar için kıskançlık içermeyen bölümü hesaplamak için bir uygulama.

Referanslar

  1. ^ Gamow, George; Stern, Marvin (1958). Bulmaca-matematik. ISBN  978-0670583355.
  2. ^ Stromquist Walter (1980). "Makul Şekilde Pasta Nasıl Kesilir". American Mathematical Monthly. 87 (8): 640–644. doi:10.2307/2320951. JSTOR  2320951.
  3. ^ Stromquist Walter (2008). "Kıskançlık içermeyen kek bölümleri, sonlu protokollerle bulunamaz" (PDF). Elektronik Kombinatorik Dergisi.
  4. ^ Stromquist hareketli bıçak prosedürü hakemin kılıcı her hareket ettiğinde üç temsilcinin bıçaklarını ayarlamasını gerektirir. Kılıç sürekli hareket ettiğinden, gereken adım sayısı sayılamaz bir sonsuzdur. Simmons kek kesme protokolü kıskanç bir bölüme yaklaşır, ancak yakınsama sonsuz sayıda adım gerektirebilir.
  5. ^ a b Deng, X .; Qi, Q .; Saberi, A. (2012). "Kıskançlık İçermeyen Pasta Kesimi için Algoritmik Çözümler". Yöneylem Araştırması. 60 (6): 1461–1476. doi:10.1287 / opre.1120.1116.
  6. ^ a b Brânzei, S. (2015). "Polinom değerlemeleri ile kıskançlık içermeyen kek kesimi üzerine bir not". Bilgi İşlem Mektupları. 115 (2): 93–95. doi:10.1016 / j.ipl.2014.07.005.
  7. ^ Alicani, Reza; Farhadi, Majid; Ghodsi, Mohammad; Seddighin, Masoud; Tacikçe, Ahmad S. (2017-02-10). "En Az Kesinti Sayısıyla Kıskançlıktan Uzak Mekanizmalar". Yapay Zeka Üzerine Otuz Birinci AAAI Konferansı.
  8. ^ a b Segal-Halevi, Erel; Hasidim, Avinatan; Aumann, Yonatan (2016). "Atık Acele Ediyor". Algoritmalar Üzerine ACM İşlemleri. 13: 1–32. arXiv:1511.02599. doi:10.1145/2988232.
  9. ^ a b c d e f Aziz, Haris; MacKenzie Simon (2016). "Herhangi bir sayıda ajan için ayrı ve sınırlı, kıskanç bir kek kesme protokolü". FOCS 2016. arXiv:1604.03655. Bibcode:2016arXiv160403655A.
  10. ^ Erel Segal-Halevi ve Avinatan Hassidim ve Yonatan Aumann (Ocak 2015). İki Boyutta Kıskanımsız Pasta Kesme. 29. AAAI Yapay Zeka Konferansı (AAAI-15). Austin, Teksas. s. 1021–1028. doi:10.13140 / RG.2.1.5047.7923.
  11. ^ Brams, Steven J .; Taylor, Alan D. (1996). Adil bölünme: pasta kesmekten anlaşmazlık çözümüne. Cambridge University Press. ISBN  0-521-55644-9.
  12. ^ Brams, Steven J .; Taylor, Alan D .; Zwicker, William S. (1997). "Dört Kişilik Kıskançlıktan Uzak Pasta Bölümüne Hareketli Bıçak Çözümü" (PDF). American Mathematical Society'nin Bildirileri. 125 (2): 547–555. doi:10.1090 / S0002-9939-97-03614-9. Alındı 2 Eylül 2014.
  13. ^ a b c d e Amin Saberi ve Ying Wang (2009). Beş Kişilik Pasta Kesmek. Bilgi ve Yönetimde Algoritmik Yönler. doi:10.1007/978-3-642-02158-9_25.
  14. ^ S. J. Brams, M. A. Jones ve C. Klamler, "Bir pastayı kesmenin daha iyi yolları", AMS Bildirimleri, 2005. [Çevrimiçi]. Mevcut: http://www.ams.org/notices/200611/fea-brams.pdf
  15. ^ a b Pikhurko, O. (2000). "Kıskançlıktan Uzak Pasta Bölümünde". American Mathematical Monthly. 107 (8): 736–738. doi:10.2307/2695471. JSTOR  2695471.
  16. ^ Gasarch, William (2015). "Kıskançlıksız Kek Kesimi için Hangi Sınırsız Protokol Daha İyi?". arXiv:1507.08497 [math.LO ].
  17. ^ a b c Aziz, Haris; MacKenzie Simon (2016). "Dört ajan için ayrı ve sınırlı bir kıskançlık içermeyen kek kesme protokolü". 48. Yıllık ACM SIGACT Hesaplama Teorisi Sempozyumu Bildirileri - STOC 2016. s. 454. arXiv:1508.05143. doi:10.1145/2897518.2897522. ISBN  9781450341325.
  18. ^ a b Kurokawa, David; Lai, John K .; Procaccia, Ariel D (2013). "Parti Bitmeden Pasta Nasıl Kesilir". AAAI. Alındı 2 Eylül 2014.
  19. ^ Procaccia Ariel (2009). "Komşunun Pastasını Seveceksin". IJCAI'09 21. Uluslararası Yapay Zeka Ortak Konferansı Bildirileri: 239–244.
  20. ^ Zeng, Dao-Zhi (2000). "Yaklaşık Kıskançlıktan Uzak Prosedürler". Oyun Uygulaması: Uygulamalı Oyun Teorisinin Katkıları. Teori ve Karar Kitaplığı. 23. Springer. s. 259–271. doi:10.1007/978-1-4615-4627-6_17. ISBN  9781461546276.
  21. ^ Idzik, Adam (1995). Birim aralığının optimum bölümleri. Kudüs.
  22. ^ Ichiishi, T .; İdzik, A. (1999). "Bölünebilir malların adil tahsisi". Matematiksel İktisat Dergisi. 32 (4): 389–400. doi:10.1016 / s0304-4068 (98) 00053-6.
  23. ^ Dall'Aglio, M .; MacCheroni, F. (2009). "İhtilaflı topraklar" (PDF). Oyunlar ve Ekonomik Davranış. 66: 57–77. doi:10.1016 / j.geb.2008.04.006.
  24. ^ Orantılılık = katkı değerlemeleri ile her bir ajan için garanti edilen değer (tüm pastanın fraksiyonu olarak). Kıskançlık olmadığında ve tüm pasta bölündüğünde, orantılılık her zaman 1/n, bu mümkün olan en iyisidir.