Dividi e scegli
Il protocollo di dividi e scegli o, dall'inglese, divide and choose è un algoritmo utilizzato per assolvere alcune problematiche di divisione equa di beni o risorse. In italiano è spesso riferito col detto "chi taglia non sceglie".
Esempio
[modifica | modifica wikitesto]Nella sua versione più semplice si possono immaginare due persone che devono dividere un bene tra di loro e necessitano di farlo in maniera equa. Per un esempio pratico possiamo immaginare Alice e Bob che devono dividere tra loro un panino. L'algoritmo è costituito da tre semplici passi:
- Alice taglia a metà il panino.
- Bob sceglie la sua metà.
- Alice prende la metà rimanente.
Considerazioni
[modifica | modifica wikitesto]Almeno in via teorica, con questo approccio si risolve il problema della divisione in parti eque.
Ricollegandoci all'esempio, questo avviene perché:
- Alice ha tutto l'interesse nel dividere le risorse nella maniera più equa possibile perché sa che poi non potrà scegliere tra le parti che ha diviso.
- Bob ha tutto l'interesse nello scegliere la parte migliore lasciando ad Alice l'altra parte (che dualmente sarà quella peggiore).
La concomitanza di queste due situazioni portano Alice a voler suddividere il bene nella maniera più equa possibile, in modo che per Bob sia indifferente scegliere una parte piuttosto che un'altra e in modo in cui lei possa avere la metà che le spetta.
Varie
[modifica | modifica wikitesto]In crittografia è utilizzata una tecnica derivata e molto simile al dividi e scegli. Teorizzata per la prima volta nel 1978 da Michael O. Rabin[1] è chiamata taglia e scegli. L'approccio taglia e scegli e quindi, indirettamente, anche l'approccio dividi e scegli, sono alla base dei protocolli interattivi e delle dimostrazioni a conoscenza zero[2].
