Fiera torta-taglio quando i giocatori si uniscono in ritardo

Question

La dichiarazione usuale del problema fiera torta-taglio presuppone che tutti i giocatori $ n $ ottengono la loro quota allo stesso tempo. Tuttavia, in molti casi i giocatori arrivano in modo incrementale. Ad esempio, possiamo dividere una torta più di $ n $ giocatori, ma poi un nuovo giocatore arriva e vuole una quota.

Di solito, la divisione equa torta richiede un grande sforzo (per esempio, richiede ai giocatori di rispondere a molte domande), soprattutto quando il numero di giocatori è di grandi dimensioni.

E 'possibile utilizzare la divisione esistente della torta oltre $ n $ giocatori, al fine di creare una nuova divisione della torta a $ n + 1 $ giocatori, con il minimo sforzo aggiuntivo (cioè sostanzialmente meno sforzo che ri- distribuire la torta da zero)?

Answer 1

dirò fin da subito che non posso fornire una buona risposta alla tua domanda (penso che si potrebbe forse ottenere un documento di ricerca fuori di esso se si potesse), ma penso di poter aiutare con la definizione del problema formale e indicando, se alcune delle difficoltà si trovano.

Sfondo . Permettetemi di affermare chiaramente il modello per la torta-taglio. Vogliamo dividere l'intervallo di $ [0,1] $ tra $ n $ giocatori. Ogni giocatore $ i $ ha una funzione di valutazione $ v_i (S) $ su sottoinsiemi $ S $ della torta. Si assume che questa funzione è una misura di probabilità; è non negativo e additivi (per disgiunti $ A, B \ subseteq [0,1] $, $ v_i (A \ coppa B) = v_i (A) + v_i (B) $) e $ v_i ([0,1] ) = 1 $. Una soluzione a questo problema è un protocollo o algoritmo che interroga dei giocatori e assegna porzioni di dell'intervallo. Si noti che i giocatori possono misreport / giacciono nel rispondere a domande.

Alcuni tipi di carta avrà restrizioni più specifiche; ad es. , funzioni di valutazione sono continue, o lineare a tratti, o costante a tratti.

Lasciate che i pezzi assegnati ai giocatori saranno in $ \ {S_1, \ dots, S_n \} $. Spesso ci vogliono le seguenti proprietà di un protocollo:

• proporzionalità : Ogni giocatore $ i $ ha una strategia che garantisce s / riceve un valore di almeno $ (1 / n) v_i ([0,1]) $. (Da $ i $ 's prospettiva, s / ottiene $ 1 / $ n del valore totale della torta.)
• invidia-freeness : Ogni giocatore ha una strategia che garantisce che $ v_i (S_i) \ geq v_i (S_j) $ per ogni altro giocatore $ j $. (Ogni giocatore preferisce il suo / la sua propria pezzo a pezzo qualsiasi altro giocatore.)

Si noti che l'invidia-freeness implica proporzionalità.

Ci sono anche proprietà "operative" che potremmo desiderare, come ad esempio il taglio in pochi pezzi, tempo di esecuzione polinomiale (o addirittura computabilità / costruibilità a tutti - non vogliamo usare l'assioma di scelta per selezionare un sottoinsieme di la torta!), e così via.

---

Domande specifiche da porre . Due note. In primo luogo, una risposta alla tua domanda risolverà il problema generale: Avviare dando tutta la torta al giocatore $ 1 $, poi lasciare che gli altri giocatori arrivano on-line e si applicano in modo iterativo questo protocollo. Così dovremmo aspettarci che questo problema sia più difficile di quanto l'impostazione di torta-taglio standard che applichiamo a.

In secondo luogo, si può sempre risolvere il problema prendendo tutta la schiena torta da tutti e utilizzando un algoritmo noto per ridistribuire da zero. Quindi la domanda è solo se c'è un po 'più elegante modo per farlo. Penso che un buon modo per quantificare questo è "quando fa la redistribuzione richiedono meno tempo o meno tagli che partire da zero, e / o quando fare i giocatori ottengono per mantenere una parte significativa della loro fetta corrente?"

1. Supponiamo di avere un'assegnazione gratuita invidia a $ n $ giocatori. Come facciamo a ridistribuire a produrre uno stanziamento senza invidia tra i $ n + 1 $ giocatori?

Ho il sospetto che questo è molto difficile. La ragione è che trovare un, efficiente allocazione priva di invidia è già un problema difficile. Per quanto ne so, i protocolli noti potrebbero richiedere un numero illimitato di tagli alla torta e sono molto complesse. (Vedere Brams e Taylor, Un Envy-libera della torta Divisione protocollo , 1995) Così ci può essere niente di meglio che prendere tutta la schiena torta da tutti e ridistribuirlo ai $ n + 1 $ agenti utilizzando Brams-Taylor.

1. Supponiamo di avere una ripartizione proporzionale a $ n $; come possiamo ridistribuire per ottenere una ripartizione proporzionale a $ n + 1 $?

Credo che questo sia ancora difficile (anche se più fattibile). Si consideri il caso in cui ogni giocatore apprezza la torta in modo uniforme ed ogni giocatore ha un $ 1 / $ n fetta -sized. Quindi qualunque sia il nuovo giocatore non richiederà rimescolare tra tutti. Ecco un altro caso male: il giocatore Supponiamo $ 1 $ ha una valutazione di esattamente $ 1 / $ n per la sua fetta, ma la fetta Valori giocatore $ 2 $ 's $ a (n-1) / n $. giocatore $ 2 $ valori Supponiamo che la propria fetta esattamentefetta $ 1 / n $, ma Valori giocatore $ 3 $ s 'fetta s a $ (n-1) / n $, e così via, con il giocatore di $ n $ valorizzando la propria fetta di $ 1 / n $ e lettore $ 1 $' a $ (n-1) / n $. Ora il nuovo giocatore arriva. Non importa quale sia il nuovo giocatore vuole, il protocollo finirà per dover rimescolare qualcosa dal giocatore $ 2 $ al giocatore $ 1 $, da giocatore di $ 3 $ al giocatore $ 2 $, ecc.

---

Un riferimento potrebbe essere Walsh, Cake linea di taglio , in teoria delle decisioni Algorithmic 2011 (pdf link). Ma penso che la carta assume sappiamo in anticipo il numero di agenti che arrivano, e si assume i giocatori devono essere assegnati un pezzo proprio quando se ne vanno (che è prima della fine del protocollo), quindi in realtà non è quello applicabile al vostro problema.

---

Un modo per ridistribuire una ripartizione proporzionale che mantiene proporzionalità è il seguente. Lasciate che ciascuno degli attuali $ n $ giocatori tagliano il suo pezzo di torta allocato in $ n + 1 $ pezzi che lui stesso ugualmente valori. Player $ n + 1 $ sarà ora scegliere il miglior pezzo, secondo lui, da ciascuno dei tagli $ giocatore $ n. È facile dimostrare che la ripartizione risultante è anche proporzionale.

Answer 2

Si supponga la torta / zona è un cerchio $ C $ di raggio $ R $. Poi, possiamo creare $ N $ pezzi equi dal taglio della torta canonica e quindi assegnare ad ogni giocatore una superficie di $ \ frac {\ pi r ^ 2} {n} $. Possiamo quindi assegnare il $ (n + 1) $ esimo un piccolo cerchio intorno al centro, e successive nuovi giocatori anelli intorno che una (deglutizione parte del cerchio interno), e così via. In questo modo, ogni giocatore ottiene un pezzo contigua / trama che si restringe in modo monotono per i primi $ n + 1 $ giocatori, e si muove verso il centro per quelli affiliarsi in seguito.

Facendo i numeri è semplice; per il primo nuovo giocatore, semplicemente risolvere

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

per ottenere il raggio per la sua trama. Per il secondo, risolvere

$ \ 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} $

per ottenere raggi (esterno) sia per i nuovi giocatori, e così via. Sembra che il giocatore $ n + i $ ottiene raggio esterno $ r_i = \ frac {r \ sqrt {i}} {\ sqrt {n + k}} $ dopo $ k $ giocatori aggiuntivi sono uniti, ma non mi dimostrano.

Questo è ciò che si ottiene a $ n = 6 $ e $ k = 0,1,2,3 $:

^{[ fonte ]}

La stessa idea funziona per i poligoni regolari con $ n $ lati. Se si assume un rettangolo come forma di base, si può fare una cosa simile, assegnando il primo $ n $ di dimensioni altrettanto colonne e le seguenti giocatori righe (a partire da un lato).