Tăiere eficientă a prăjiturii

Tăierea eficientă a prăjiturii este o problemă în economie și informatică : există o resursă eterogenă , cum ar fi o prăjitură cu diferite tipuri de decorațiuni sau o bucată de pământ cu vegetație diferită. Se presupune că resursa este divizibilă - poate fi tăiată în părți arbitrar mici, fără pierdere de valoare. Resursa ar trebui împărțită între mai mulți participanți, ținând cont de solicitările acestora: unii preferă decorațiunile de ciocolată, alții preferă cireșe și cineva dorește să obțină cea mai mare bucată posibilă și așa mai departe. Partiția finală ar trebui să fie Pareto eficientă .

Cel mai obișnuit studiu al eficienței a fost în raport cu corectitudinea , unde scopul este de a găsi o partiție care să îndeplinească atât criteriile de eficiență, cât și de corectitudine.

Formalizarea problemei

Există o prăjitură . Se presupune de obicei că modelul este un segment finit unidimensional, sau un poligon bidimensional sau un subset finit al unui spațiu euclidian multidimensional . $C$ $\mathbb{R}^d$

Să fie participanți. Fiecare participant are o funcție subiectivă de evaluare pentru resursa în cauză, care mapează subseturile la numere. $n$ $i$ $V_i$ $C$

Este necesar să se împartă în subseturi care nu se suprapun, astfel încât fiecare participant să primească o piesă separată. Piesa transmisă participantului va fi notată ca ; în acest fel . $C$ $n$ $i$ $X_{i}$ $C=X_{1}\sqcup ...\sqcup X_{n)$

Un exemplu de tort

Mai jos ne vom uita la un tort din două părți, ciocolată și vanilie, împărțit de două persoane: Alice și George. Fie ca valorile funcțiilor de evaluare să aibă următoarele valori:

	parte de ciocolată	partea de vanilie
Alice	9	unu
George	6	patru

Eficiență

Partiția este dominantă Pareto (considerată mai optimă) dacă cel puțin o persoană se simte mai bine decât , și nimeni nu se simte mai rău decât . Simbolic: $Y$ $X$ $Y$ $X$ $Y$ $X$

\forall {i}:\ V_{i}(Y_{i})\geqslant V_{i}(X_{i})

și

\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})

Distribuția Pareto eficientă (EP, în engleză Pareto-eficient , PE) este o distribuție care nu este dominată Pareto de nicio altă distribuție, adică nu poate fi îmbunătățită. În exemplul unui tort, sunt posibile mai multe distribuții EP, în timp ce . De exemplu, orice împărțire care dă întregul tort unei singure persoane este un PE, deoarece orice modificare a distribuției va avea ca rezultat o obiecție a acelei persoane. Desigur, distribuția EP nu este neapărat corectă.

O combinație de eficiență și corectitudine

O partiție care este atât Pareto eficientă, cât și proporțională se numește EPPR ( ing. Pareto-eficient and proportional , PEPR), iar o partiție care este atât EP cât și fără invidie se numește EPSP ( ing. Pareto-efficient and envy-free , PEEF ) pe scurt.

Împărțirea EPPR

Diviziunea EP poate fi obținută trivial, pasând întregul tort unui singur participant. Dar distribuția EP, care este și proporțională cu , nu poate fi găsită printr-un algoritm finit. Dovada este asemanatoare cu cea folosita pentru problema taierii prajiturii dupa utilitate .

Diviziunea EPSP

Pentru n participanți cu funcții de evaluare aditive, atunci când piesele pot fi deconectate, există întotdeauna o împărțire FTE. Aceasta este teorema lui Weller .

Dacă prăjitura este un segment unidimensional și fiecare persoană trebuie să primească un segment conectat, sunt valabile următoarele rezultate generale: dacă funcțiile de evaluare sunt strict monotone (adică fiecare persoană preferă cu putere o piesă față de toate propriile sale subseturi), atunci orice Distribuția SZ este, de asemenea, un EP (rețineți că acest lucru nu este adevărat dacă agenții pot primi bucăți tăiate). Prin urmare, în acest caz , protocoalele Simmons-Su creează o divizare EPSP.

Dacă tortul este un cerc unidimensional (adică un segment ale cărui două capete sunt identificate topologic) și fiecare participant trebuie să primească arcuri conectate, atunci rezultatele de mai sus nu sunt valabile - distribuția SZ nu este neapărat EP. În plus, există perechi de funcții de estimare (neaditive) pentru care nu există distribuție FTE. Totuși, dacă există 2 agenți și cel puțin unul dintre ei are o funcție de rating aditiv, atunci EPSP există [1] .

Vezi și

Note

↑ Thomson, 2006 , p. 501.

Literatură

Thomson W. Copii care plâng la petrecerile de naștere. De ce? // Teoria economică. - 2006. - T. 31 , nr. 3 . - S. 501-521 . - doi : 10.1007/s00199-006-0109-3 . . Titlu: „Copiii plâng la petrecerile de naștere. De ce?"