Pembagian kue dua dimensi yang adil

Saya tertarik pada prosedur pembagian tanah yang adil (yaitu pembagian yang bebas iri, atau setidaknya pembagian yang proporsional).

Berbeda dengan masalah pembagian kue yang dipelajari dengan baik, pembagian tanah adalah dua dimensi, yaitu, preferensi pengguna dapat bervariasi baik secara horizontal maupun vertikal. Oleh karena itu, tidak praktis untuk membatasi algoritma ke pemotongan paralel.

Satu-satunya referensi yang saya temukan sejauh ini adalah Karthik Iyer dan Michael Huhns, 2007 . Mereka mengatakan bahwa "Kami belum menemukan solusi konstruktif (algoritmik) sejauh ini untuk masalah pembagian lahan generik. Semua makalah telah menawarkan solusi eksistensial untuk versi masalah yang memenuhi syarat."

Mereka sendiri membuktikan algoritma O (n ^ 2) untuk pembagian tanah proporsional, dengan batasan tertentu (misalnya masing-masing agen n harus menandai n daerah persegi panjang dengan utilitas 1 / n, dan jika persegi panjang tidak tumpang tindih terlalu banyak, algoritma menjamin bahwa setiap agen mendapatkan salah satu persegi panjangnya).

Apakah Anda tahu ada referensi yang lebih baru tentang masalah ini? Saya tertarik secara khusus dalam algoritma praktis, dan mereka mungkin perkiraan.

Penulis yang Anda kutip memiliki makalah lain tentang topik tersebut .

Apakah Anda akan puas dengan model yang mengasumsikan bahwa sifat-sifat permukaan yang akan dialokasikan dapat diringkas oleh seperangkat parameter satu dimensi yang terbatas tetapi terbatas (katakanlah panjang, kedalaman, titik paling utara, titik paling timur, ... benar-benar sama sebanyak yang Anda inginkan tetapi terbatas)?

Jika ini memuaskan bagi Anda, dan Anda setuju dengan anggapan bahwa orang memiliki preferensi terhadap permukaan seperti yang dijelaskan oleh nilai-nilai parameter ini, Anda mungkin menemukan wawasan yang berguna dalam teori alokasi yang adil dari bundel beberapa barang. Pengantar yang hebat (dan gratis) adalah "Aturan Alokasi Adil" oleh William Thomson .

Tentu saja ketika dimensi mewakili parameter yang menggambarkan bentuk yang akan dialokasikan, Anda cenderung memiliki preferensi yang tidak biasa yang sulit untuk dikerjakan dan tidak cocok dengan hasil yang ada. Mungkin patut dicoba ...

Saya kira Anda bisa mengatasi masalah ini dengan mengurangi dimensi masalah. Misalnya, Anda dapat membagi tanah menjadi beberapa area terpisah (baik secara manual atau menggunakan algoritma yang sesuai). Lalu, Anda dapat menggunakan algoritma satu dimensi diskrit apa pun seperti metode penawaran Tertutup yang dijelaskan dalam http://www.colorado.edu/education/DMP/fair_division.html .

Saya tidak menemukan jawaban yang cocok, jadi saya harus menulisnya sendiri . Itu adalah bagian pertama dari Ph.D. tesis. Masih banyak pertanyaan terbuka di bidang ini.