Indica un intervallo di date:
  • Dal Al

Sali in auto! Allocazione stabile di passeggeri e guidatori

Ritrovo alle 7:30 domattina al parcheggio dietro casa per una bella giornata al mare. Quattro auto, venti persone in totale, insomma, una bella comitiva. Ecco che mi sorge un dubbio: come ci divideremo nelle auto? C’è sempre quello che guida troppo forte, quello che ascolta techno anche prima di fare colazione, i due che si scannerebbero a parlare di politica asfissiando gli altri passeggeri. Chi fuma. Chi non fuma. Il tempo sarà splendido, vogliamo evitare dissidi di prima mattina, e soprattutto partire in orario!

Sono uno dei guidatori, e la sera precedente non riesco a prendere sonno. Proviamo a formalizzare il problema: siamo 4 guidatori e 16 restanti passeggeri. Ogni guidatore ha le sue preferenze su chi vorrebbe in macchina, supponiamo una lista ordinata dal passeggero preferito al passeggero meno desiderabile. Ogni passeggero ha di suo una preferenza sull’auto su cui vorrebbe salire, anche qui supponiamo una lista ordinata dall’auto preferita all’ultima scelta. Tralasciamo le antipatie e le preferenze tra i passeggeri stessi, mi pare di avere già un problema sufficientemente complesso. E poi è tardi.

Ora, cosa esattamente vogliamo evitare nella allocazione tra auto e passeggeri? Se al primo autogrill due passeggeri si scambiano di auto significa che l’allocazione di che avevamo trovato non era stabile. Dunque vogliamo fare in modo che non ci siano mai due coppie guidatore-passeggero tali che i guidatori preferiscano il passeggero che sta sull’altra auto a quello a loro allocato, e che anche i passeggeri stessi preferiscano stare sull’altra auto piuttosto che su quella a cui sono stati allocati. Con uno scambio ci guadagnano tutti e quattro (ossia seguono i propri incentivi) rompendo la tanto agognata stabilità del sistema.

Ormai è troppo tardi per chiedere le rispettive preferenze a tutti e mettermi ad assegnare passeggeri e guidatori a mano, e ci vorrebbero tonnellate di messaggi su whatsapp.

Lampo di genio! Ecco la procedura che ci farà partire in orario e senza intoppi: appena siamo tutti presenti, uno, due, tre, e ognuno si presenta davanti all’auto che preferisce. Ovviamente ci saranno le auto più popolari che saranno prese d’assalto (ahimé dopo l’invenzione di questa procedura temo che la mia auto non sarà tra quelle). A questo punto è il turno dei guidatori, che scelgono i quattro passeggeri che preferiscono tra quelli che si sono presentati alla loro auto. I “rifiutati” ora si presentano all’auto di seconda scelta, e i guidatori di nuovo scelgono i quattro passeggeri che preferiscono tra i nuovi arrivati e quelli che avevano scelto alla prima tornata. Può darsi infatti che qualcuno dei primi rifiutati sia il preferito di uno degli altri guidatori, ma che la cosa non sia reciproca (e a quest’ora del mattino nessuno si offende, si vuole solo partire). La procedura continua così fino a che gli equipaggi non sono stati formati, non ci sono più rifiutati che rimbalzano da un’auto all’altra, e finalmente si può partire!

pilot

Non avrò tempo di spiegare domattina che questa procedura garantisce un matching stabile tra guidatori e passeggeri, ma conto sulla fiducia e sul sonno dilagante. Inoltre la procedura favorisce lievemente i guidatori, ma questo non lo dirò a nessuno. Ecco la sveglia, è ora di partire!

[Oltre a farmi perdere sonno, questa procedura è utilizzata dagli ospedali americani per spartirsi ogni anno le candidature degli specializzandi, in un’enorme procedura di matching a livello nazionale. Più informazioni su questa pagina.]