Distribuie și alege

Delhi și alegeți (sau Tăiați și alegeți , precum și eu tăiați, alegeți voi ) este o procedură de tăiere a tortului între doi participanți, în urma căreia nu există invidie . Problema presupune bunuri sau resurse eterogene („tort”) și doi participanți cu preferințe diferite pentru părți separate ale tortului. Protocolul funcționează după cum urmează: unul dintre participanți („tăiere”) taie tortul în două bucăți, al doilea participant („alegerea”) alege una dintre bucăți, iar tăietorul primește bucata rămasă.

Istorie

Metoda împărțiți și alegeți este menționată în Biblie în Cartea Genezei . Când Avraam și Lot au ajuns în țara Canaanului , Avraam s-a oferit să o împartă între ei. Atunci Avraam, care a venit dinspre sud, a împărțit țara în părți „stânga” (vest) și „dreapta” (est) și l-a invitat pe Lot să aleagă. Lot a ales partea de est, care includea Sodoma și Gomora , în timp ce Avraam a primit partea de vest, care conținea Beer- Șeba , Hebron , Beit El și Sihem .

Analiză

Metoda împărțiți și alegeți oferă o partiție fără invidie în următorul sens: fiecare dintre cei doi participanți poate acționa în așa fel încât, ca urmare a divizării, partea lui (în opinia sa) să nu fie mai puțin valoroasă. decât partea celui de-al doilea participant, indiferent de comportamentul celui de-al doilea participant. Iată cum se pot comporta membrii:

Pentru un observator din afară, împărțirea poate părea nedreaptă, dar nu există niciun motiv pentru care participanții la diviziune să se invidieze reciproc.

Dacă funcțiile de evaluare a participanților sunt aditive , atunci împărțirea și alegerea este de asemenea proporțională în următorul sens: fiecare participant poate acționa în așa fel încât să i se garanteze că va obține o piesă cu o valoare de cel puțin 1/2 din evaluarea totală a tortului. Aceasta este o consecință a faptului că, în cazul estimărilor aditive, orice tăiere fără invidie este de asemenea proporțională.

Protocolul funcționează în același mod pentru partajarea unei resurse dorite (ca în tăierea tortului ) ca și pentru partajarea unei resurse nedorite (ca în partajarea sarcinilor ).

Protocolul de împărțire și alegere presupune aceleași cote datorate și decizia de a împărți între ei sau de a folosi medierea , dar nu un arbitru . Se presupune că binele este divizibil în orice fel, dar părțile pot fi evaluate diferit de jucători.

Este logic ca tăietorul să împartă resursa cât mai corect posibil, altfel s-ar putea să obțină o parte nedorită. Această regulă este o aplicare specifică a conceptului de cortină a ignoranței .

Metoda împărțiți și alegeți nu garantează că fiecare participant va primi exact jumătate din tort conform propriei estimări, deci împărțirea nu este exactă . Nu există o procedură finită pentru împărțirea exactă, dar se poate face cu două cuțite în mișcare . Vezi articolul despre procedura cuțitului în mișcare al lui Austin .

Probleme de eficiență

Delhi-și-alege poate da o feliere ineficientă.

Un exemplu des folosit este prăjitura , care este jumătate vanilie și jumătate ciocolată . Să presupunem că lui Bob îi place doar ciocolata și lui Carol doar vanilia. Dacă Bob este tăietorul și nu cunoaște preferințele lui Carol, cea mai sigură strategie a lui este să taie tortul astfel încât fiecare bucată să conțină o cantitate egală de ciocolată. Dar apoi, indiferent de alegerea lui Carol, Bob primește doar jumătate din ciocolată și este clar că tăierea nu este eficientă Pareto . Este cu totul posibil ca Bob să separe, fără să știe, toată vanilia (și puțină ciocolată) într-o singură porție mare, astfel încât Carol să primească tot ce și-a dorit, în timp ce Bob să primească mai puțin decât ar putea obține după o discuție comună.

Alternative

Dacă Bob știe preferințele lui Carol și o place, el poate tăia tortul în toată ciocolată și toată vanilie, așa că Carol poate alege vanilia și Bob primește toată ciocolata. În schimb, dacă nu-i place Carol, poate tăia tortul în puțin peste jumătate din porția de vanilie dintr-o bucată, iar restul porției de vanilie și porția de ciocolată în altă bucată. Carol poate, de asemenea, să ia o bucată cu o bucată de ciocolată pentru a-l detesta Bob. Există o procedură pentru rezolvarea chiar și a unor astfel de probleme, dar este foarte instabilă cu mici erori în estimări [1] . Există mai multe soluții practice care garantează optimitatea, dar sunt mult mai bune decât metoda divide-and-choose dezvoltată de Stephen Brahms și Alan Taylor, în special procedura „ tuning winner ” [2] [3] .

În 2006, Stephen J. Brahms, Michael A. Jones și Christian Klamer au explicat în detaliu o nouă modalitate de tăiere a prăjiturii, numită procedura surplus ( surplus procedure , SP), care satisface condiția de imparțialitate și, prin urmare, rezolvă cele de mai sus. problema [4] . Aprecierile subiective ale jucătorilor pieselor alocate acestora în raport cu întregul tort sunt aceleași.  

Partajare între mai mult de doi participanți

Martin Gardner a popularizat provocarea de a dezvolta o procedură de împărțire echitabilă similară pentru grupuri mari în rubrica sa din mai 1959 „Mathematical Games” din Scientific American [5] . Una dintre proceduri începe cu faptul că unul dintre participanți taie tortul conform înțelegerii lor despre o împărțire corectă. Oricine altcineva poate tăia o parte dintr-o bucată pentru a o face mai mică. Ultimul care reduce o bucată este obligat să o ia.

O nouă metodă a fost propusă în Scientific American [6] de Aziz și McKenzie [7] . Deși în principiu mai rapid decât metodele anterioare, poate rămâne foarte lent: , unde n este numărul de bucăți dorit.

Vezi și

Note

  1. ↑ Cake Cutting with Full Knowledge Arhivat 9 februarie 2020 la Wayback Machine David McQuillan 1999 (nerevizuit)
  2. ↑ Brams, Taylor, 1996 .
  3. ↑ Brams, Taylor, 1999 .
  4. ↑ Brams, Jones, Klamler, 2006 , p. 1313-1321.
  5. ↑ Gardner, 1994 .
  6. ↑ Klarreich, 2016 .
  7. ↑ Aziz, MacKenzie, 2017 .

Literatură