Indietro

ⓘ Dividi e scegli




                                     

ⓘ Dividi e scegli

Il protocollo di dividi e scegli o, dallinglese, 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".

                                     

1. Esempio

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. Lalgoritmo è costituito da tre semplici passi:

  • Alice taglia a metà il panino.
  • Alice prende la metà rimanente.
  • Bob sceglie la sua metà.
                                     

2. Considerazioni

Almeno in via teorica, con questo approccio si risolve il problema della divisione in parti eque.

Ricollegandoci allesempio, questo avviene perché:

  • Bob ha tutto linteresse nello scegliere la parte migliore lasciando ad Alice laltra parte che dualmente sarà quella peggiore.
  • Alice ha tutto linteresse nel dividere le risorse nella maniera più equa possibile perché sa che poi non potrà scegliere tra le parti che ha diviso.

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 unaltra e in modo in cui lei dovrà scegliere potrà avere la metà che gli spetta.

                                     

3. Varie

In crittografia è utilizzata una tecnica derivata e molto simile al dividi e scegli. Teorizzata per la prima volta nel 1978 da Michael O. Rabin è chiamata taglia e scegli. Lapproccio taglia e scegli e quindi, indirettamente, anche lapproccio dividi e scegli, sono alla base dei protocolli interattivi e delle dimostrazioni a conoscenza zero.