Pemotongan kue yang adil saat pemain bergabung terlambat

Pernyataan biasa dari masalah adil pemotongan kue mengasumsikan bahwa semua pemain mendapatkan bagian mereka pada waktu yang sama. Namun, dalam banyak kasus para pemain tiba secara bertahap. Misalnya, kami dapat membagi kue lebih dari pemain, tetapi kemudian pemain baru tiba dan ingin berbagi. $n$ $n$

Biasanya, pembagian kue yang adil membutuhkan banyak usaha (misalnya, mengharuskan pemain untuk menjawab banyak pertanyaan), terutama ketika jumlah pemain besar.

Apakah mungkin untuk menggunakan divisi yang ada kue lebih pemain, dalam rangka menciptakan sebuah divisi baru dari kue ke pemain, dengan upaya tambahan minimal (yaitu substansial kurang upaya dari re-mendistribusikan kue dari awal)? $n$ $n+1$

algorithms game-theory online-algorithms Erel Segal-Halevi
sumber

Sudahkah

pemain pertama mulai makan? Apakah adil untuk memberi pemain beberapa bagian, atau apakah setiap orang harus mendapatkan satu bagian?

n

$n$

Raphael

@Raphael, saya secara khusus tertarik pada pembagian tanah yang adil, oleh karena itu para pemain tidak dapat benar-benar mulai memakan bagian mereka (mereka dapat membangun bagian mereka, tetapi mari kita abaikan masalah ini untuk saat ini). Lebih disukai untuk memberikan masing-masing pemain tepat satu bagian, namun, ini tampaknya tidak mungkin dilakukan secara adil jika hanya ada satu orang baru yang datang. Mungkin saya harus bertanya, apa yang terjadi jika

pemain baru tiba. Dalam hal ini, adalah mungkin (setidaknya secara teori) untuk membagi setiap saham dari

pemain pertama menjadi 2 saham baru. Bagaimanapun, referensi apa pun diterima.

n

$n$

n

$n$

Erel Segal-Halevi

Dalam hal tanah yang tidak digunakan, mengapa tidak mendistribusikan kembali semuanya?

Raphael

Saya pikir Anda harus mengklarifikasi apa tujuan Anda. Minimalkan jumlah pemotongan yang diperbarui? Minimalkan total panjang pemotongan baru? Bisakah kita menugaskan bagian untuk pemain lama, atau bisakah satu-satunya kehilangan?

Raphael

Ah, sekarang saya mengerti maksud Anda: maksud Anda bahwa beberapa pemain mulai memakan bagian mereka, dan sekarang pemain baru tiba, dan kami ingin membagi pengingat dengan adil, dengan mempertimbangkan apa yang sudah dimakan masing-masing pemain. Meskipun ini merupakan masalah yang menarik dengan sendirinya, niat saya berbeda - saya harap hasil edit saya baru-baru ini menjelaskan hal ini.

Erel Segal-Halevi

Jawaban:

Saya akan mengatakan di muka bahwa saya tidak dapat memberikan jawaban yang baik untuk pertanyaan Anda (saya pikir Anda mungkin bisa mendapatkan makalah penelitian jika Anda bisa), tetapi saya pikir saya dapat membantu dengan mendefinisikan masalah secara formal dan menyatakan di mana beberapa kesulitan terletak.

Latar Belakang . Biarkan saya dengan jelas menyatakan model untuk memotong kue. Kami ingin membagi interval antara pemain. Setiap pemain memiliki fungsi penilaian atas himpunan bagian kue. Kami akan menganggap bahwa fungsi ini adalah ukuran probabilitas; itu nonnegatif dan aditif (untuk disjoint , $[0,1]$ $n$ $i$ $v_i(S)$ $S$ $A,B \subseteq [0,1]$ ) dan . Solusi untuk masalah ini adalahprotokolatau algoritma yang menanyakan pemain dan memberikan porsi interval. Perhatikan bahwa pemain dapat salah melaporkan / berbohong dalam menjawab pertanyaan. $v_i(A \cup B) = v_i(A) + v_i(B)$ $v_i([0,1]) = 1$

Beberapa makalah akan memiliki batasan yang lebih spesifik; misal , fungsi penilaian bersifat kontinu, atau linear-demi-satu, atau konstan-demi-satu.

Biarkan potongan yang ditugaskan untuk para pemain menjadi . Kami sering menginginkan properti protokol berikut: $\{S_1,\dots,S_n\}$

proporsionalitas : Setiap pemain memiliki strategi yang menjamin dia menerima nilai setidaknya . (Dari 's perspektif, s / ia mendapat dari total nilai kue.) $i$ $(1/n)v_i([0,1])$ $i$ $1/n$
iri-freeness : Setiap pemain memiliki strategi yang menjamin bahwa untuk setiap pemain lain . (Setiap pemain lebih memilih bagiannya sendiri daripada bagian pemain lain.) $v_i(S_i) \geq v_i(S_j)$ $j$

Perhatikan bahwa iri-hati menunjukkan proporsionalitas.

Ada juga properti "operasional" yang mungkin kita inginkan, seperti memotong menjadi beberapa bagian, waktu menjalankan polinomial (atau memang komputabilitas / konstruktivitas sama sekali - kita tidak ingin menggunakan Aksioma Pilihan untuk memilih subset kue! ), dan seterusnya.

Pertanyaan spesifik untuk ditanyakan . Dua catatan. Pertama, setiap jawaban atas pertanyaan Anda akan menyelesaikan masalah umum: Mulailah dengan memberikan seluruh kue ke pemain , lalu biarkan pemain lain tiba online dan menerapkan protokol ini secara berulang. Jadi kita harus mengharapkan masalah ini lebih sulit daripada pengaturan pemotongan kue standar yang kita terapkan. $1$

Kedua, kami selalu dapat menyelesaikan masalah Anda dengan mengambil seluruh kue kembali dari semua orang dan menggunakan algoritma yang dikenal untuk mendistribusikannya kembali dari awal. Jadi pertanyaannya adalah apakah ada cara yang agak lebih elegan untuk melakukan ini. Saya pikir cara yang baik untuk menghitung ini adalah "kapan redistribusi membutuhkan lebih sedikit waktu atau lebih sedikit pemotongan daripada mulai dari awal; dan / atau kapan pemain bisa mendapatkan porsi signifikan dari irisan mereka saat ini?"

Misalkan kita memiliki alokasi kecemburuan bebas untuk pemain. Bagaimana kita mendistribusikan untuk menghasilkan alokasi iri bebas antara pemain? $n$ $n+1$

Saya kira ini sangat sulit. Alasannya adalah bahwa menemukan alokasi yang bebas iri, efisien, sudah merupakan masalah yang sulit. Sejauh yang saya tahu, protokol yang dikenal bisa membutuhkan jumlah pemotongan yang tidak terbatas pada kue dan sangat kompleks. (Lihat Brams dan Taylor, An Envy-Free Kue Divisi Protocol , 1995.) Jadi mungkin ada yang lebih baik daripada untuk mengambil seluruh kembali kue dari semua orang dan mendistribusikan ke agen menggunakan Brams-Taylor. $n+1$

Misalkan kita memiliki alokasi proporsional untuk ; bagaimana kita mendistribusikan mendapat alokasi proporsional untuk ? $n$ $n+1$

Saya pikir ini masih sulit (walaupun lebih bisa dilakukan). Pertimbangkan kasus di mana setiap pemain menilai kue secara seragam dan setiap pemain memiliki potongan berukuran . Maka apa pun yang dilakukan pemain baru akan membutuhkan perombakan di antara semua orang. Berikut ini kasus buruk lainnya: Misalkan pemain memiliki penilaian tepat untuk slice-nya, tetapi menilai slice pemain di . Misalkan pemain menilai irisannya sendiri tepat , tetapi menghargai irisan pemain di $1/n$ $1$ $1/n$ $2$ $(n-1)/n$ $2$ $1/n$ $3$ , dan seterusnya, dengan pemain menilai irisannya sendiri pada danirispemain di . Sekarang pemain baru tiba. Tidak peduli apa yang diinginkan pemain baru, protokol Anda pada akhirnya harus merombak sesuatu dari pemain ke pemain , dari pemain ke pemain , dll. $(n-1)/n$ $n$ $1/n$ $1$ $(n-1)/n$ $2$ $1$ $3$ $2$

Salah satu referensi mungkin Walsh, Online Cake Cutting , dalam Algorithmic Decision Theory 2011 (pdf link). Tapi saya pikir kertas mengasumsikan kita tahu di muka jumlah agen yang tiba, dan mengasumsikan pemain harus dialokasikan sepotong tepat ketika mereka pergi (yang sebelum akhir protokol), jadi itu benar-benar tidak berlaku untuk masalah Anda.

$n$ $n+1$ $n+1$ $n$

usul
sumber

Saya tidak yakin bagaimana masalah umum (dengan preferensi yang tidak seragam) dapat membantu di sini; whoops ? Memecahkan masalah untuk pemain yang tidak berubah (dan bentuk yang masuk akal) adalah mudah. Saya kira kita harus memperbaiki apa yang dimaksud "efisien" dengan resp "bagus" yang berarti potongan / alokasi dan perubahannya.

Raphael

@ Raphael - sejauh yang saya tahu, pertanyaannya adalah tentang menyelesaikan masalah umum. (Saya setuju kita harus menggunakan struktur tambahan jika ada yang ditentukan.)

usul

Terima kasih, definisi Anda tepat menangkap maksud saya. Dan referensi tentang pemotongan kue online menarik dan relevan.

Erel Segal-Halevi

$C$ $r$ $n$ $\frac{\pi r^2}{n}$ $(n+1)$ $n+1$

Mengerjakan angka-angka itu sederhana; untuk pemain baru pertama, cukup pecahkan

$\qquad \pi r_1^2 = \frac{\pi r^2}{n+1}$

untuk mendapatkan radius plotnya. Untuk yang kedua, selesaikan

$\qquad\begin{align} \pi r_1^2 &= \frac{\pi r^2}{n+2} \\ \pi r_2^2 - \pi r_1^2 &= \frac{\pi r^2}{n+2} \end{align}$

$n + i$ $r_i = \frac{r\sqrt{i}}{\sqrt{n+k}}$ $k$

$n=6$ $k=0,1,2,3$

contoh ^{[ sumber ]}

$n$ $n$

Raphael
sumber

Akan menarik untuk membandingkan area yang dipindahkan dengan metode ini ke area yang ditugaskan dengan memasukkan potongan baru (yaitu sektor) kue dan memindahkan (dan menyusut) semua potongan yang ada searah jarum jam. Jumlah pihak yang dipengaruhi oleh suatu langkah (tidak hanya kerugian) hanya berbeda dengan konstanta. Perhatikan juga bahwa dering tidak lebih efektif daripada sektor, tetapi perubahan dari satu metode ke metode lainnya memungkinkan untuk tidak memindahkan area yang ditentukan oleh metode pertama.

frafl

@raf saya setuju. Bisakah Anda menyajikan varian lain dalam sebuah jawaban? (Anda benar: tampaknya tidak ada alasan yang baik untuk mencampur metodenya. Bagi saya itu termotivasi oleh masalah kue: anggap kue sudah dipotong, apa yang harus dilakukan?)

Raphael

n + 1

$n+1$

Ini adalah solusi gemoetrikus yang indah, namun ini hanya relevan untuk kue dan prererensi seragam yang seragam. Saya merujuk pada masalah pemotongan kue secara umum: en.wikipedia.org/wiki/Fair_division yang mengasumsikan bahwa kue tersebut bisa tidak seragam, dan pemain yang berbeda mungkin memiliki penilaian yang berbeda untuk bagian kue yang berbeda.

Erel Segal-Halevi