Tăierea prăjiturii în funcție de utilitate

Tăierea prăjiturii după utilitate (sau tăierea tortului cu suma maximă ) este regula împărțirii resurselor eterogene , cum ar fi un tort sau un imobil , între mai mulți participanți cu funcții de utilitate cantitativă diferite, astfel încât suma utilității pentru participanți să fie la fel de mare ca posibil. O astfel de tăiere a fost inspirată din filozofia utilitarismului . Tăierea tortului în funcție de utilitate este adesea „nedreaptă”. Prin urmare, utilitarismul este în conflict cu doar tăierea tortului .

Exemplu

Să ne imaginăm un tort format din două părți - ciocolată și vanilie. Să fie doi participanți - Alice și George cu următoarele estimări

Participant	Ciocolată	Vanilie
Alice	9	unu
George	6	patru

Regula de utilitate dă fiecare parte participantului cu cel mai mare scor de utilitate . În acest caz, conform regulii de utilitate, Alice primește toată ciocolata și George primește toată vanilia. Valoarea maximă va fi 13.

Reducerea în funcție de utilitate este nedreaptă - nu este proporțională pentru că George obține mai puțin de jumătate din nota maximă. De asemenea, nu este lipsit de invidie , deoarece George este gelos pe Alice.

Notație

Să notăm tortul cu litera . De obicei, se presupune că este fie un segment finit unidimensional, un poligon bidimensional , fie o submulțime finită a unui spațiu euclidian de dimensiuni mai mari . $C$ $\mathbb{R}^d$

Sunt participanți. Fiecare participant are o funcție personală de notare care mapează subseturi („bucăți de tort”) în numere. $n$ $i$ $V_i$ $C$

$C$ trebuie împărțite în părți care nu se suprapun, una pentru fiecare participant. Partea transmisă participantului este notată cu și . $n$ $i$ $X_{i}$ $C=X_{1}\sqcup ...\sqcup X_{n)$

O împărțire se numește împărțire de utilitate , sau utilitate maximă (MP) sau sumă maximă dacă maximizează următoarea expresie: $X$

{\displaystyle \sum _{i=1}^{n}{V_{i}(X_{i)))))

Conceptul este adesea generalizat prin atribuirea de ponderi diferite fiecărui participant. O partiție se numește ponderat-utilitar-maximal ( WUM ) dacă maximizează următoarea expresie: $X$

\sum _{i=1}^{n}{\frac {V_{i}(X_{i})}{w_{i)))

unde sunt date constante pozitive. $w_{i}$

Maxsum și eficiența Pareto

Orice partiție MVP cu ponderi pozitive este evident Pareto eficientă . Dacă partiția este dominantă Pareto , atunci suma ponderată a utilităților în este strict mai mare decât în , deci nu poate fi o partiție MVP. $Y$ $X$ $Y$ $X$ $X$

Mai surprinzător, orice partiție Pareto eficientă este un MVP pentru anumite ponderi [1] [2] .

Caracteristicile regulii maxsum

Christopher P. Chambers a propus trăsăturile caracteristice ale regulii MVP [3] . Caracteristicile se bazează pe următoarea proprietate a regulii de împărțire R :

Eficiență Pareto (PE, în engleză Pareto-efficiency , PE): regula R returnează numai partiții care sunt Pareto eficiente.
Independenta de diviziune ( ND, independența de diviziune în engleză , DI) : dacă tortul este împărțit în mai multe bucăți și fiecare dintre ele este tăiată conform regulii R , rezultatul va fi același ca și cum prăjitura originală a fost tăiată conform regulii R .
Independența terenului infezabil ( IIL): atunci când un sub-tort este împărțit conform regulii R , rezultatul nu depinde de beneficiul participanților la alte sub-turte.
Tratamentul pozitiv al egalilor ( PTE) : dacă toți participanții au aceleași funcții de utilitate, regula R recomandă cel puțin o împărțire care să ofere utilitate pozitivă fiecărui participant.
Scala -invarianță ( SI) : atunci când funcțiile de evaluare a participanților sunt înmulțite cu o valoare constantă (sunt permise diferite constante pentru diferiți participanți), recomandările date de regula R nu se modifică.
Continuitate ( Continuitate , CO ): Pentru o bucată fixă de tort, setul de scheme de utilitate care se mapează la o anumită distribuție este închis prin convergență punctuală .

Următoarele fapte sunt dovedite pentru participanții care atribuie utilitate pozitivă oricărei bucăți de tort cu o dimensiune pozitivă:

Dacă regula R are proprietățile PE, ND și NNS, atunci există o secvență de ponderi astfel încât toate partițiile recomandate de regula R sunt MVP-uri cu aceste ponderi (s-a demonstrat că orice partiție PE este o MVP cu unele ponderi ). Ceea ce este nou este că toate partițiile recomandate de regula R sunt MVP-uri cu aceleași greutăți (asta reiese din proprietățile ND). $w_{1},\dots,w_{n)$
Dacă regula R are proprietățile PE, ND, NNS și POR, atunci toate partițiile recomandate de regula R sunt maxim utile (cu alte cuvinte, toate diviziunile trebuie să fie MVP și toți agenții trebuie să aibă ponderi egale. Aceasta rezultă din POR proprietate).
Dacă regula R are proprietățile PE, ND, NNS și NS, atunci regula R este o regulă dictatorială - dă întregul tort unui participant.
Dacă o regulă R are proprietățile PE, ND, NNS și LR, atunci există o secvență de ponderi astfel încât regula R este o regulă MVP cu aceste ponderi (adică, R recomandă doar o diviziune MVP cu aceste ponderi). $w_{1},\dots,w_{n)$

Găsirea sumei maxime a partițiilor

Piese deconectate

Dacă funcțiile scor sunt aditive , diviziunile sumei maxime există întotdeauna. Intuitiv, putem oferi fiecare parte din tort participantului care o evaluează cel mai mult, ca în exemplul de mai sus . În mod similar, divizia MVP poate fi găsită pasând fiecare bucată de tort partenerului pentru care raportul are cea mai mare valoare. $V_{i}/w_{i}$

Acest proces este ușor de implementat dacă tortul este omogen pe bucăți , adică poate fi împărțit într-un număr finit de bucăți pentru care densitatea funcțiilor de valoare pentru toți participanții este constantă.

Dacă tortul nu este omogen pe bucăți, algoritmul de mai sus nu reușește deoarece există un număr infinit de „bucăți” diferite de luat în considerare.

În acest caz, partiția maxsum încă există. Aceasta este o consecință a teoremei de compactitate Dubins-Spanier și poate fi demonstrată folosind mulțimea Radon-Nikodim .

Cu toate acestea, niciun algoritm finit nu poate găsi partiția maxsum. Dovada [4] . Algoritmul final are date despre valoarea unui număr finit de piese. Adică, există doar un număr finit de subseturi ale tortului pentru care algoritmul cunoaște scorurile participanților. Să presupunem că algoritmul s-a oprit după primirea datelor pe subseturi. Acum este posibil ca toți participanții să fi răspuns că au aceleași scoruri de bucată . În acest caz, cea mai mare utilitate posibilă care poate fi atinsă de algoritm este 1. Cu toate acestea, este posibil ca în adâncul uneia dintre bucăți să existe un subset pe care cei doi participanți îl apreciază diferit. În acest caz, există o împărțire superproporțională în care fiecare participant primește o valoare mai mare decât , astfel încât suma utilităților este strict mai mare decât 1. Prin urmare, diviziunea returnată de algoritmul final nu va fi suma maximă. $k$ $k$ $1/n$

Piese conectate

Dacă tortul este unidimensional și piesele trebuie conectate, algoritmul simplu de atribuire a fiecărei piese cele mai valoroase unui agent nu mai funcționează, chiar dacă piesele sunt constante pe bucăți. În acest caz, sarcina de a găsi imputația MT este NP-hard și, în plus, nicio schemă FPTAS nu este posibilă decât dacă P=NP.

Există un algoritm de aproximare de 8 ori și un algoritm solubil cu parametri fix care este exponențial în numărul de jucători [5] .

Pentru orice set de greutăți pozitive, există o partiție MVP și poate fi găsită într-un mod similar.

Suma maximă și capitalul propriu

Diviziunea sumei maxime nu este întotdeauna corectă, vezi exemplul de mai sus . De asemenea, o împărțire corectă nu este întotdeauna maxsum.

O abordare a soluționării conflictului este constrângerea „prețului justiției” - calculăm limitele superioare și inferioare ale scăderii cantității de utilitate pentru a obține o partiție corectă. Pentru detalii, consultați articolul „ Prețul capitalului propriu ”.

O altă abordare pentru a combina eficiența și corectitudinea este să căutați printre toate diviziunile echitabile posibile diviziunea cu cantitatea maximă de utilitate:

Găsirea distribuțiilor de sumă maximă corectă

Următorii algoritmi pot fi utilizați pentru a găsi o tăietură fără invidie cu utilitatea totală maximă pentru un tort sub forma unui interval unidimensional, dacă fiecare participant poate primi bucăți disparate (deconectate) din tort și funcțiile de evaluare sunt aditive [6] :

Pentru participanții cu estimări constante pe bucăți : împărțiți tortul în m regiuni complet constante (). Rezolvăm o problemă de programare liniară cu nm variabile - fiecare pereche (agent, zonă) are o variabilă care determină ponderea ariei transferată agentului. Pentru fiecare regiune există o constrângere că suma tuturor părților regiunii este 1. Pentru fiecare pereche (agent, agent) există o constrângere că primul agent nu este gelos pe al doilea agent. Rețineți că despicarea prăjiturii obținute printr-o astfel de procedură se poate dovedi a fi extrem de mică. $n$
Pentru participanții cu estimări liniare pe bucăți : pentru fiecare punct al tortului, calculăm raportul dintre utilități: . Oferim participantului 1 punct de la , iar participantului 2 puncte de la , unde este calculat pragul astfel încât împărțirea să nu fie invidiată. În general, nu poate fi calculat deoarece poate fi irațional , dar în practică, când estimările sunt liniare pe bucăți, poate fi aproximat prin algoritmul de aproximare „căutare irațională”. Pentru orice , algoritmul găsește o distribuție care este -SZ (valoarea fiecărui agent nu este mai mică decât valoarea oricărui alt agent minus ) și suma atinge cel puțin suma maximă a distribuțiilor SZ. Timpul de rulare al algoritmului depinde polinom de datele de intrare și de . $2$ $r=u_{1}/u_{2)$ $r\geqslant r^{*}$ $r<r^{*}$ $r^{*}$ $r^{*}$ $r^{*}$ $\epsilon > 0$ $\epsilon$ $\epsilon$ $\log(1/\epsilon )$
Pentru participanții cu estimatori generali: o aproximare aditivă pentru a obține o distribuție fără invidie și eficientă bazată pe un algoritm de scor liniar pe bucăți. $n$

Proprietăți ale distribuțiilor maxsum-fair

Articolul lui Brahms et al [7] studiază atât împărțirea torturilor fără invidie (SE, eng. envy-free , EF) cât și imparțială (DB, eng. echitable , EQ) și stabilește legătura lor cu maxsum și Pareto optim ( OP, ing. Pareto-optimalitate , PO) pe diviziuni. După cum sa explicat mai sus, suma maximă a unei distribuții este întotdeauna OP. Cu toate acestea, atunci când suma maximă este constrânsă de condiția de corectitudine, acest lucru nu este neapărat adevărat. Brahms și coautorii au dovedit următoarele

Când există doi agenți, distribuția SZ max, DB max și SZ-DB max va fi întotdeauna OD.
Când există trei sau mai mulți agenți cu estimatori omogene pe bucăți , distribuțiile maxime SZ sunt întotdeauna OP (deoarece SZ este echivalent cu proporționalitatea , care este păstrată sub îmbunătățirile Pareto). Cu toate acestea, este posibil să nu existe un DB maxim și o distribuție maximă DB-SZ care ar fi OP.
Dacă există trei sau mai mulți agenți cu funcții de evaluare constante pe bucăți (adică, având densități constante pe bucăți), este posibil să nu existe o distribuție maximă SZ care să fie OP. De exemplu, luați în considerare un tort cu trei regiuni și trei agenți cu valori: Alice : 51/101, 50/101, 0 Bob : 50/101, 51/101, 0 Carl : 51/111, 10/111, 50/111 . Regula maxsum dă aria i agentului i, dar această împărțire nu este lipsită de invidie, deoarece Carl este gelos pe Alice. Folosind programarea liniară, se poate găsi o singură distribuție maximă SZ și se poate arăta că ar trebui să dea cote în regiunea 1 și regiunea 2 atât lui Alice, cât și lui Bob. Cu toate acestea, o astfel de alocare nu poate fi OP, deoarece Alice și Bob ar putea beneficia de schimburi de acțiuni în aceste regiuni.
Dacă toți agenții au funcții de evaluare liniară pe bucăți , atunci suma utilităților distribuției maxime SZ nu este mai mică decât utilităților distribuției maxime DB. Acest rezultat se extinde la scoruri generale pentru aproximări aditive (adică, distribuțiile -SZ au o sumă de utilități nu mai mică decât utilitățile distribuțiilor DB minus ). $\epsilon$ $\epsilon$

Vezi și

Pleasure Counting este o încercare de a determina utilitatea folosind formule matematice.
Tăiere eficientă a prăjiturii
Provocarea de tăiere a prăjiturii
teorema lui Weller
Distribuție Pareto eficientă fără invidie
Distribuție maximă pe rang

Note

↑ Barbanel și Zwicker 1997 , p. 203.
↑ Vezi și teorema lui Weller . Pentru rezultate similare legate de problema de alocare neuniformă a resurselor, vezi teoremele lui Varian .
↑ Chambers, 2005 , p. 236–258.
↑ Brams și Taylor 1996 , p. 48.
↑ Aumann, Dombb, Hassidim, 2013 .
↑ Cohler, Lai, Parkes, Procaccia, 2011 .
↑ Brams, Feldman et al., 2012 , p. 1285–1291.

Literatură

Julius B. Barbanel, William S. Zwicker. Două aplicații ale unei teoreme a lui Dvoretsky, Wald și Wolfovitz la divizarea tortului // Teorie și decizie. - 1997. - T. 43 , nr. 2 . - doi : 10.1023/a:1004966624893 .
Christopher P. Chambers. Reguli de alocare pentru împărțirea terenurilor // Journal of Economic Theory. - 2005. - T. 121 , nr. 2 . - doi : 10.1016/j.jet.2004.04.008 .
Steven J. Brams, Alan D. Taylor. împărțire corectă; De la tăierea prăjiturii la soluționarea disputelor. - 1996. - ISBN 978-0521556446 .
Yonatan Aumann, Yair Dombb, Avinatan Hassidim. Calcularea diviziilor de prăjituri eficiente din punct de vedere social // AAMAS . — 2013.
Yuga Julian Cohler, John Kwang Lai, David C. Parkes, Ariel Procaccia. Tăiere optimă de tort fără invidie // AAAI . — 2011.
Steven J. Brams, Michal Feldman, John K. Lai, Jamie Morgenstern, Ariel D. Procaccia. Despre Maxsum Fair Cake Divisions // Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI-12) . — 2012.