Se siamo in due e dobbiamo dividere equamente una torta, che si fa?
Semplice: tu tagli, io scelgo.
O viceversa.
È un buon metodo perché a giochi fatti nessuno potrà lamentarsi.
Zero lamentele.
Tuttavia, non è ancora un metodo perfetto poiché sia io che te potremmo voler "scegliere" anziché “tagliare”, in modo da trarre profitto da eventuali errori nel taglio.
Questo conflitto ci mette a rischio di stallo.
Ma il metodo ha un altro difetto: se fossimo in tre? Il metodo non funziona più.
E un altro ancora: se fossimo in quattro? Nemmeno.
Ha infiniti difetti. Ma limitiamoci a dire che non costituisce una soluzione universale.
Ebbene, esiste un metodo alternativo che supera tutte queste difficoltà garantendo assenza di stallo e assenza di invidia post-riparto. Un metodo cioè che garantisce la divisione della torta e il fatto che nessuno dei commensali possa mai invidiare la fetta altrui.
***
Come si procede?
Per capirlo, facciamo mente locale su un altro stallo famoso, quello a cui andò incontro Re Salomone nella Bibbia: come ripartire il bambino conteso da due madri?
[tra parentesi: la Bibbia e il Talmud sono pieni di divisioni problematiche]
Il povero Re dovette ripiegare su un trucco poiché non c'erano alternative. Il bene da ripartire – si noti - non era né divisibile né moltiplicabile.
Il metodo che azzera stalli e invidia, infatti, si applica solo a beni e servizi divisibili o moltiplicabili.
E’ un grave limite? No, non è un grande limite perché molti beni all'apparenza indivisibili e non moltiplicabili sono comunque soggetti a trasformazioni che li rendono tali.
Ci sono molti modi per trasformare la natura di un bene, per esempio avvalendosi della moneta.
Per esempio, Salomone avrebbe potuto mettere all’asta il bambino conteso.
Ma questo metodo ha un inconveniente: difficilmente azzera l'invidia, la retrocede soltanto spostandone l’oggetto.
La madre più povera invidierà la madre più ricca perché possiede un patrimonio che le consente di ottenere il figlio messo all’asta da Salomone.
L’invidia, in altri termini, si trasferisce semplicemente dalle fette di torta alla liquidità disponibile.
Non c’è qualcosa di meglio?
***
Forse sì.
Arriviamoci per gradi, è proprio grazie al denaro, infatti, che possiamo capire come si giunge alla soluzione ottimale. Prendete questo caso fatto da Albert Sun..
... Last year, two friends and I moved into a small three-bedroom apartment in Manhattan. We chose it for its relatively reasonable price— around $ 3,000 a month— and its convenient location. Just finding it was a challenge, but then we faced another one: deciding who would get each bedroom...
È il caso di tre universitari che devono ripartirsi le tre stanze di un appartamento che hanno preso in affitto. Come fare?
Le stanze non sono né divisibili, né moltiplicabili, lo spettro dello stallo aleggia.
… division of rent based on square feet or any fixed list of elements can’t take every individual preference into account…
Ciascuno dei tre potrebbe avere gusti che i pochi parametri presi in considerazione dai soliti metodi non catturano...
... The problem is that individuals evaluate a room differently. I care a lot about natural light, but not everyone does. Is it worth not having a closet? Or one might care more about the shape of the room, or its proximity to the bathroom...
Fortunatamente, qualcosa di divisibile legato al problema c'è: il canone d'affitto. Quello sì che “divisibile” in molti modi.
Che fare? Un’asta?
L’asta funziona quando bisogna assegnare un bene, qui ce ne sono tre.
Si potrebbe fare un’asta con le buste ma non garantirebbe la soddisfazione generale.
Un partecipante potrebbe per esempio puntare troppo sulla stanza che gli piace di più per poi vedersi soffiare anche quella che gli piace un po’ meno a vantaggio, magari, di qualcuno che è fondamentalmente indifferente a tutto.
In sintesi possiamo dire che si tratta di soluzioni che implicano “comportamento strategico”: devo tener conto di quello che faranno gli altri. Per esempio: meglio puntare sulla mia seconda preferita anziché sulla prima, tanto per rischiare un po’ meno. Ma se gli altri facessero altrettanto?
Quando si entra nel vortice dei bluff e dei comportamenti strategici possiamo stare certi che il metodo prescelto per allocare i beni è inefficiente.
***
Veniamo alla soluzione ottima.
Deriva da un lemma del matematico tedesco Emanuel Sperner.
Il metodo non è pura teoria, è già stato usato in alcuni casi concreti…
… The procedures have been used to divide such things as Germany after World War II, deep-sea mining rights, and property after a divorce or death…
Il metodo garantisce: soluzioni certe, zero matematica, zero strategia, zero invidia, zero scambi post riparto. Non male
Se siamo in tre costruiamo un triangolo e ad ogni angolo fissiamo una tripletta che ripartisce il canone per ciascuna stanza.
Esempio: 3000/0/0 – 0/3000/0 – 0/0/3000. Per ogni tripletta si chiede agli studenti di scegliere la loro camera preferita.
Esiste una tripletta in cui tre studenti scelgono tre camere differenti? Se sì, si procede all’assegnazione. Se no, si compie un passo ulteriore creando altri triangoli meno polarizzati.
Esempio: 1500/1500/0 – 1500/0/1500 – 0/1500/1500.
Esiste ora una tripletta in cui tre studenti scelgono tre camere differenti? Se sì, si procede all’assegnazione. Se no, si compie un passo ulteriore creando altre triplette.
E via così.
All’infinito?
No! Il lemma di Sperner garantisce proprio questo: la tripletta fatidica – quella che accontenta tutti - si ottiene sempre compiendo un numero finito di passi. L’algoritmo è convergente.
Il metodo è semplice: basta un algoritmo per generare le triplette.
Risultato finale:
Zero matematica: i partecipanti non devono fare nessun calcolo per ottimizzare le loro scelte.
Zero strategia: i partecipanti possono trascurare le scelte dei “concorrenti”.
Zero invidia: alla fine nessuno invidierà la condizione di qualcun’ altro.
Zero scambi: alla fine nessuno sarà interessato a scambiare qualcosa con qualcun’altro.
Universalità dell’applicazione: se siamo in quattro creeremo delle quadriplette e via così ad libitum.
***
Qualcuno obbietterà: sì ma nel caso degli universitari comparivano ancora i soldi e, come si diceva, i soldi non risolvono ma spostano solo i problemi legati all’invidia.
Vero. Ma in un caso del genere la logica adottata prescinde dalla presenza del denaro, si potrebbe anche non tirarli in ballo.
Basta “divisibilità e moltiplicazione” per applicare il lemma di Sperner con tutte le sue spettacolari garanzie. La moneta non è l’unico modo di assicurare divisibilità e moltiplicazione.
La cosa migliore però è fare qualche esempio.
Prendiamo allora un altro problema: come ripartire i lavori domestici tra marito e moglie?
I soggetti sono due: marito e moglie.
I lavori sono tre: pulire i pavimenti, lavare i piatti, fare la lavatrice.
I lavori non sono divisibili… ma sono moltiplicabili poiché sono compiti ripetitivi: i piatti li posso lavare una volta, due, tre ecc.
I soggetti esprimono le loro preferenze: per esempio, il marito preferisce lavare i piatti che fare la lavatrice.
Ma possono quantificarle in modo preciso appunto perché parliamo di compiti “moltiplicabili”: potrebbe preferire, per esempio, lavare due volte i piatti pur di evitare una lavatrice.
Anche differenze più raffinate sono esprimibili, esempio: preferisco fare 17 volte i piatti piuttosto che 5 lavatrici.
Si noti che nel confronto relativo tra i vari beni si creano dei prezzi (questa volta in natura), e quindi la possibilità di compilare triplette come nel caso precedente.
Con queste premesse – seguendo la logica vista nel caso degli universitari - i compiti sono sempre ripartibili tra marito e moglie con zero matematica, zero strategia, zero invidia, zero scambi.
Esempio: ogni volta che il marito pulirà 3 volte il pavimento, farà 4 lavatrici e 5 lavastoviglie, la moglie pulirà 4 volte il pavimento, farà 3 lavatrici e 5 lavastoviglie.
E funziona indipendentemente dal numero di coniugi e di lavori domestici.
Funziona sempre!
***
E quando i coniugi divorziano e devono distribuirsi i beni?
Il lemma di Sperner piomba offrendo una soluzione universale e non contestabile: zero litigi.
In casi del genere i beni – a parte i soldi - non siamo in presenza di beni divisibili (chi si prende la lavatrice? e la libreria?), e di sicuro nemmeno moltiplicabili.
Tuttavia, la divisibilità di cui necessitiamo potrebbe essere ricavata da una scala di preferenze.
Assegnate, per esempio, 1000 punti di preferenza a moglie e marito chiedendo loro di spalmarli sui vari oggetti da ripartire.
Sarà possibile formare tanti pacchetti (insieme di beni), in particolare, visto che i coniugi sono due, tante coppie di pacchetti.
Dopodiché, Sperner garantisce l’esistenza di una coppia di pacchetti ideale: zero litigi. Ma anche zero matematica, zero strategia, zero invidia, zero scambi.
***
Ei, ma questo caso è simile a quello iniziale della torta!
Torniamo allora alla torta da dividere fra tre persone: tagliatela (anche a casaccio) e dotate ciascun goloso di mille punti da spalmare sulle varie fette di torta.
Una volta espresse le preferenze ci penserà Sperner.
Se ci sono problemi, tagliate ulteriormente e riassegnate i punti-preferenza (oppure moltiplicate i punti preferenza portandoli a 10000).
Ancora problemi?: tagliate e/o moltiplicate i punti preferenza.
Paura di dover continuare all’infinito? Non dovete aver paura, Sperner vi garantisce che il numero di passi necessari per arrivare in porto è finito.
***
C’è chi osserva: zero matematica? Non mi sembra.
Attenzione: zero matematica per chi partecipa al riparto. Costoro, nell’assolvere il loro compito al meglio, devono solo esprimere una preferenza senza che sia necessario nessun calcolo e nessun ragionamento complesso. Devono solo dire cosa preferiscono.
Dopodiché, è vero, occorre comunque un algoritmo che generi alternative coerenti e calcoli il riparto ottimo. E magari che acceleri la procedura senza dover fare tutti i passi: per quanto siano “finiti”, potrebbero essere molti!
Se non volete ricavarlo voi, roba del genere per passare dalla teoria ai fatti è comunque disponibile in rete su molti siti gratuiti.
***
Affine al problema del riparto è quello dell’accoppiamento.
Nel riparto, oggetti senza preferenze devono essere assegnati a soggetti con preferenze.
Nell’accoppiamento, soggetti con preferenze vanno abbinati a soggetti con preferenze.
Il classico caso è quello romantico: come formare le coppie migliori, ovvero a zero invidia, zero strategia, zero scambi di coppia eccetera?
Ma anche fare l’orario scolastico alla fin fine è un problema di accoppiamento: bisogna abbinare ad ogni ora una materia, da una parte ci sono le preferenze dell’insegnante (che per esempio vuole il giorno libero), dall’altra quella degli allievo e/o della scuola (che non vogliono mettere matematica all’ultima ora quando si è tutti stanchi).
***
I casi concreti risolti in modo efficiente sono tanti: come abbinare uno slot a una compagnia aerea? Un donatore di reni a un ricevente? Un paziente a una sala operatoria?…
… Kidneys for transplantation are scarce. So is airspace: an airliner uses several hundred dollars per minute in fuel, and only one airplane can occupy a given block of airspace at a time. Passengers’ time is also costly. Who got which kidney, which operating room, and which flight path that day in April all required an allocation of scarce resources, so it is perhaps fitting that when Jerry is not flying a small plane, he is a professor of economics at Harvard…
Il problema è economico: allocazione efficiente di risorse scarse. I donatori sono pochi, gli slot sono pochi, le sale operatorie sono poche…
Accoppiare bene i soggetti puo’ essere questione di vita e di morte…
… Matching sometimes is the gatekeeper of life itself, as when it determines which desperately ill patients receive scarce organs for transplant…
Di solito pensiamo che sia il mercato ad occuparsi di allocare le risorse...
... Until recently, economists often passed quickly over matching and focused primarily on commodity markets, in which prices alone determine who gets what. In a commodity market, you decide what you want, and if you can afford it, you get it...
E in effetti il mercato fa un gran lavoro. Il mercato è anonimo: basta il prezzo per fare tutto...
... When buying one hundred shares of AT&T on the New York Stock Exchange, you needn’t worry about whether the seller will pick you. You don’t have to submit an application or engage in any kind of courtship... The price does all the work...
Ma in molti casi noi non accettiamo che il prezzo "sia tutto", in questi casi il mercato va integrato. Pensiamo solo al mondo della scuola: noi non accettiamo la logica per cui chi paga si prenda le scuole migliori…
... Going to college can be costly, and not everyone can afford it. But that isn’t because colleges raise tuition until only as many students can afford to attend as the college can accommodate—that is, until demand equals supply. On the contrary, selective colleges, high priced as they are, try to keep the tuition low enough so that many students would like to attend, and then they admit a fraction of those who apply... A market involves matching whenever price isn’t the only determinant of who gets what...
D'altro canto, dobbiamo far tesoro dei pregi legati al meccanismo di mercato.
Altri esempi...
... Kidney transplants cost a lot, but cash doesn’t decide who gets a kidney... Similarly, airport landing slots involve fees, but that isn’t what determines who gets them...
Pensiamo al mercato dei reni da trapiantare. Molti di noi lo sentono come ripugnante. In casi del genere si può ricorrere a algoritmi di accoppiamento che stemperino la ripugnanza senza perdere del tutto i pregi legati alla logica di mercato...
... Many people would find it repugnant to allow money to decide who gets a kidney or a seat in a sought-after public kindergarten. When there aren’t enough kidneys to go around (and there aren’t) or seats in the best public schools (there never are), scarce resources must be allocated by some kind of matching process...
***
Queste correzioni prendono il nome di "market design" (MD).
A volte questi pseudo mercati evolvono spontaneamente, altre volte vengono progettati dai designer...
... Sometimes a matching process, whether formal or ad hoc, evolves over time. But sometimes, especially recently, it is designed...
Disegnare pseudo mercati fa capire bene cosa sia un mercato. Un designer deve conservare i punti di forza tipici del mercato. Ma quali sono?...
... Markets differ from central planning because no one but the participants themselves determines who gets what. And marketplaces differ from anything-goes laissez-faire because participants enter the marketplace knowing that it has rules...
Sul mercato l'esito emerge dalle preferenze degli attori.
Sul mercato i valori soggettivi bastano a far funzionare tutto.
E’ un gran pregio poiché la cosa limita i conflitti. Non è necessario che un' autorità s'imponga e dica "a chi spetta cosa" in nome di un qualche valore oggettivo.
Lo abbiamo visto prima trattando i riparti: l'esito finale che emerge è a prova di invidia, non c'è motivo per cui si generi un conflitto.
Certo, uno puo’ sempre contestare l’esito finale rimproverando all’altro le sue preferenze, ma si tratta di una posizione eticamente debole.
***
I mercati, oltre a essere a volte ripugnanti, spesso sono difettosi.
Per esempio: sono diluiti.
Il mercato è diluito quando gli operatori presenti sono pochi, oppure arrivano alla spicciolata, oppure vanno e vengono. Se io arrivo prima di te può darsi che compri un articolo che tu avresti pagato di più perché lo desideri di più. Questo è uno spreco bell' e buono. Ecco, chi disegna accoppiamenti deve sapere che un buon mercato è "spesso", ovvero non "diluito". Lo vediamo con le aste: si comincia quando sono tutti presenti, e quando si finisce di “battere” tutti se ne vanno. Anche la borsa apre e chiude ad orari precisi...
... The first task of a successful marketplace is bringing together many participants who want to transact, so they can seek out the best transactions. Having a lot of participants makes a market thick... Efforts to keep markets thick often concern the timing of transactions. When should offers be made? How long should they be left open?...
Il caso contrario è quello del mercato congestionato...
... Congestion is a problem that marketplaces can face once they’ve achieved thickness.... congestion has set in, and that can make it impossible for participants to identify the most promising alternatives the market has to offer...
Tu puoi aprire e chiudere la casa d'aste ad orari ben definiti ma se poi fai partire 4 aste contemporaneamente la gente non capisce più niente e molti affari sfumano: la procedura di accoppiamento si dice che è "congestionata".
Sia come sia nell'accoppiamento come sul mercato la preferenza degli operatori è al centro...
... One thing that all markets challenge participants to do is to decide what they like... College admissions officers aren’t simply trying to pick the best students. They’re trying to pick the best students who will choose to attend if admitted...
Il vero nemico di chi disegna algoritmi di accoppiamento sono i comportamenti strategici di chi partecipa. Come definirli?...
... Decisions that depend on what others are doing are called strategic decisions and are the concern of the branch of economics called game theory... Sometimes the goal of the market designer is to reduce the need to game the system, allowing choosers to concentrate on identifying their true needs and desires...
L'algoritmo che assegnava gli studenti nelle scuole pubbliche di Boston è fallito proprio perché dava adito a comportamenti strategici...
... the issue that led Boston Public Schools to invite my colleagues and me to help redesign the system for matching children to schools...
Poteva essere conveniente invertire l’ordine delle prime due preferenze.
Quando a militare ho finito l’Accademia mi hanno chiesto le destinazioni preferite: poiché sapevo che la mia preferita era molto richiesta, ho segnalato come preferita la mia seconda ottenendola. Chi invece è stato sincero l’ha preso in quel posto.
Il colpevole: un algoritmo ministeriale di accoppiamento stupido.
Una volta che il bluff paga la procedura puo’ dirsi “stupida”.
Semplicità e sicurezza cono il cuore di un buon algoritmo: essere sinceri nell'esprimere le proprie preferenze non deve essere una virtù ma una convenienza.
***
Chi disegna algoritmi di accoppiamento studia i difetti del mercato: diluito, congestionato, ripugnante...
... Every market has a story to tell. Stories about market design often begin with failure—failure to provide thickness, to ease congestion, or to make participation safe and simple... market designers are like firefighters who come to the rescue when a market has failed and try to redesign a marketplace... But markets can succeed on their own practical terms and still fail in the eyes of those who don’t or won’t participate in them. Some markets are regarded as repugnant...
Il processo evoluzionistico può essere visto come un algoritmo per accoppiare. L'uomo, grazie alla ragione, può migliorarlo...
... Avi (mentore di Roth)commanded me to stick my finger deep into the flower of a sage plant. When I withdrew my finger, it had a line of pollen on the back. Avi then explained how this flower has evolved so that bees have to reach deep inside to get nectar, and thus only big bees with long tongues can get it. The pollen sticks to their backs, where it will be safely transmitted to the next flower they visit. The flower of this plant and bees have coevolved to take advantage of what each offers the other: The flower offers an especially rich source of nectar that can be harvested only by big bees. Big bees, therefore, have a reason to specialize in this kind of flower, which means that the pollen has a good chance of being delivered to another flower of the same species (which is the point of the flower, from the plant’s point of view). In this case, evolution has been the matchmaker...
I fallimenti di mercato ispirano il designer, sono il suo cibo quotidiano, in questo senso, per la sua opera, non c'è nulla di più prezioso…
... Much of what we’ve learned about market design—and from market design about markets more generally—has come from observing market failures and figuring out how to fix them...
***
L’algoritmo ideale puo’ essere inventato oppure scoperto…
… THE SOLUTIONS TO problems in market design are sometimes invented, sometimes discovered, and often a bit of both…
Quando una soluzione emerge viene poi sfruttata altrove…
… we can sometimes discover a solution to a new market failure in a design pioneered in another market….
Ma cosa si intente per “scoperta”? Prendiamo il caso della penicillina…
… we can sometimes discover a solution to a new market failure in a design pioneered in another market….
Alcune soluzioni di accoppiamento sono già disponibili in natura, la gente comune provando e riprovando le ha già di fatto adottate. Possono essere prese e formalizzate per altri casi.
Facciamo un esempio: c’è una malattia che ha sempre afflitto i medici, quella del primo impiego dopo la laurea…
… Since about 1900, the first job American doctors take after graduating from medical school is called an internship or residency, in which they’re supervised by more senior docs…
Sia il neo-medico che l’ospedale hanno le loro esigenze. Come conciliarle?…
… there’s a lot of pressure on both sides to make good matches—on medical students to get good first jobs and on hospital residency programs to hire good young docs…
La competizione tra ospedali per accaparrarsi i migliori creava distorsioni…
… their competition for scarce medical school graduates, hospitals began to try to hire interns a little earlier than competing hospitals….
Venivano contattati gli studenti dal terzo anno, e persino le matricole in alcuni casi! Ma era rischioso anticipare i tempi in questo modo spericolato.
Per gli studenti stessi era problematico formulare preferenze con anni di anticipo.
Mancava una visione complessiva del problema…
… Students also were often forced to consider offers from one hospital at a time, without ever knowing what their prospects might be at other hospitals…
La prima soluzione adottata dalla scuole mediche: mantenere il segreto sul profitto degli studenti e su altre informazioni…
… Although early hiring was pretty bad for both students and residency programs, we’ve already seen that unraveling isn’t solved by self-control. Only in 1945, when a third party—medical schools—agreed not to release information about students before a specified date, was the timing of offers controlled…
Gli ospedali risposero con una esplosione di offerte generalizzate nel giorno della laurea…
… Hospitals now found that if some of the first offers they made were rejected after a period of deliberation, the candidates to whom they wished to make their next offers often had already accepted other positions… This, of course, led hospitals to begin making exploding offers. Now candidates had to reply immediately, even before they could learn what other offers might be available. That in turn led to a chaotic market that shortened in duration from year to year and resulted not only in missed agreements but also in broken ones. In other words, the market suffered from congestion…
Il mercato si congestionava restando altamente inefficiente.
Fu uno studente medico (fondatore di un’associazione dopo aver subito l’ingiustizia del sistema) a proporre l’algoritmo che poi valse il Nobel agli studiosi che lo formalizzarono. Si puo’ ben dire che David Gale e Lloyd Shapley “scoprirono” la loro formula senza inventare alcunché.
Si capì ben presto che la procedura di accoppiamento andava centralizzata.
La procedura è semplicissima, si esaurisce in pochi passi.
Passo 0:
… Applicants and employers privately submit preferences to a clearinghouse in the form of rank order lists…
Ogni ospedale stila una classifica dei suoi candidati preferiti. Altrettanto fanno i candidati con gli ospedali.
Passo 1:
… Each employer offers jobs to its top-choice candidates, up to the number of its available positions… tentatively accepts the best one (the one highest on her preference list), and rejects any others…
Ogni ospedale formula le offerte ai suoi candidati preferiti. Chi ha in mano più offerte mantiene la sua preferita e scarta le altre. Si noti che l’accettazione è provvisoria.
Passo 2:
… Each employer that had a job offer rejected in the previous step offers that job to its next choice… Each applicant considers the offer he or she has been holding together with his or her new offer(s) and tentatively accepts…
Gli ospedali con offerte rifiutate formulano offerte alternative a chi credono (anche a chi ha già un’offerta accettata temporaneamente).
Il processo termina quando non ci sono più offerte rifiutate.
Semplice, no?
La garanzia dell’algoritmo:
… the final matching is always stable with respect to the preferences submitted by the employers and applicants, whatever those preferences happen to be…
L’esito è stabile: non possono esserci situazioni migliori rispetto a quella creata dall’algoritmo.
***
Ma l’algoritmo entrò in crisi.
Quando?
Con l’accesso alla professione delle donne.
Molti medici si fidanzarono o si sposarono tra loro, a questo punto le preferenze di Tizio venivano a dipendere da quelle di Caio. Con preferenze relative l’algoritmo va in palla.
La storia degli algoritmi con preferenze interrelate è più incasinata, meglio evitarla.
