Complessità esatta in termini di tagli della divisione proporzionale di una torta in parti di uguale lunghezza

Abstract degli autori

Studiamo la divisione proporzionale di una torta con il vincolo di parti di uguale lunghezza: ciascuno degli $n$ agenti deve ricevere una porzione lunga esattamente $1/n$ che, secondo la sua valutazione, valga almeno $1/n$. Il nostro risultato principale determina il numero esatto di tagli necessari nel caso peggiore per garantire una tale ripartizione: $2n-2$ per ogni $n$. Il risultato migliora il limite superiore quadratico noto in precedenza. La dimostrazione combina il teorema della divisione vincolata della collana con un argomento ricorsivo di assegnazione basato sul teorema di Hall. Lo stesso limite vale anche con il requisito più forte dell’assenza di invidia quando $n$ è una potenza di un numero primo; per un $n$ qualsiasi, vale invece un limite superiore di $O(n^{1.525})$. Ci chiediamo poi se sia possibile calcolare tali ripartizioni. Mostriamo anzitutto che nessun protocollo deterministico nel modello Robertson--Webb termina dopo un numero finito di interrogazioni per ogni istanza e restituisce sempre una ripartizione proporzionale esatta con parti di uguale lunghezza, nemmeno nel caso di due agenti con valutazioni identiche. Per ogni $\varepsilon>0$, tuttavia, bastano $O(n^2/\varepsilon)$ interrogazioni per ottenere una ripartizione in cui ogni agente riceve una porzione lunga esattamente $1/n$ e di valore almeno $1/n-\varepsilon$, usando anche in questo caso al massimo $2n-2$ tagli. Infine, estendiamo il modello Robertson--Webb con interrogazioni a due coltelli. Mostriamo che il dimezzamento bilanciato ricorsivo raggiunge il limite ottimale di $2n-2$ tagli quando $n$ è una potenza di due. Per un $n$ qualsiasi, proponiamo una procedura che usa $O(n\log n)$ tagli.