Egalitarne krojenie ciasta
Egalitarne krojenie to rodzaj sprawiedliwego krojenia, w którym kryterium uczciwości jest zasada egalitaryzmu . Tort o różnych wartościach części zasobu. Celem egalitarnego krojenia tortu jest maksymalizacja najmniejszej wartości agenta; z zastrzeżeniem tego, zmaksymalizuj następną najmniejszą wartość; i tak dalej. Nazywa się to również krojeniem ciasta leksyminy , ponieważ optymalizacja odbywa się przy użyciu porządku leksymin na wektorach użyteczności.
Koncepcja egalitarnego krojenia ciasta została po raz pierwszy opisana przez Dubinsa i Spaniera , którzy nazwali to „podziałem optymalnym”.
Istnienie
Alokacje optymalne dla leksyminy istnieją zawsze, gdy zbiór alokacji jest przestrzenią zwartą . Dzieje się tak zawsze w przypadku alokacji dyskretnych obiektów i łatwe do udowodnienia w przypadku alokacji skończonej liczby ciągłych jednorodnych zasobów. Dubins i Spanier udowodnili , że przy ciągłym heterogenicznym zasobie („ ciastku ”) zbiór alokacji jest zwarty. Dlatego zawsze istnieją optymalne dla leksyminy przydziały ciasta. Z tego powodu reguła alokacji ciasta leksyminowego jest czasami nazywana regułą Dubinsa-Spaniera .
Warianty
Kiedy wyceny agentów nie są znormalizowane (tj. różni agenci mogą przypisać różną wartość całemu tortowi), istnieje różnica między bezwzględnym profilem użyteczności alokacji (gdzie element i jest po prostu użytecznością agenta i ) a jego względny profil użyteczności (gdzie element i to użyteczność agenta i podzielona przez całkowitą wartość agenta i ). Reguła bezwzględnej leksyminy wybiera alokację, w której profil użyteczności bezwzględnej jest maksymal- na leksyminy, a reguła leksyminy względnej wybiera alokację, w której profil użyteczności względnej jest maksymal- ny leksyminy.
Nieruchomości
Oba warianty reguły leksyminy są optymalne w sensie Pareto i monotoniczne dla populacji . Różnią się jednak innymi właściwościami:
- Reguła leksymin absolutnych jest zasobem monotonicznym , ale nie proporcjonalnym ;
- Reguła względnych leksymin jest proporcjonalna, ale nie monotoniczna względem zasobów.
Stosunek do braku zazdrości
Oba warianty reguły leksyminy mogą dawać alokacje, które nie są wolne od zawiści . Załóżmy na przykład, że jest 5 agentów, ciasto jest fragmentarycznie jednorodne z 3 regionami, a wyceny agentów to (brakujące wartości to zera):
| Agent | Lewy | Środek | Prawidłowy |
|---|---|---|---|
| A | 6 | 9 | |
| B | 5 | 10 | |
| C | 15 | ||
| D | 15 | ||
| mi | 15 |
Wszyscy agenci wyceniają cały tort na 15, więc leksymina absolutna i leksymina względna są równoważne. Największa możliwa wartość minimalna to 5, więc przydział leksymin musi dawać wszystkim agentom co najmniej 5. Oznacza to, że Prawica musi być równo podzielona między agentów C, D, E, a Środek musi być w całości przyznany agentowi B. Ale wtedy A zazdrości B.
Dubins i Spanier udowodnili, że kiedy wszystkie miary wartości są ściśle dodatnie, każda alokacja względna leksymin jest wolna od zawiści.
Weller wykazał wolny od zazdrości i efektywny przydział tortu, który nie jest względną leksyminą. Placek to [0,1], są trzy agenty, a ich miary wartości to trójkątne rozkłady wyśrodkowane odpowiednio w 1/4, 1/2 i 3/4. Alokacja ([0,3/8],[3/8,5/8],[5/8,1]) ma profil użyteczności (3/8,7/16,7/16). Jest wolny od zazdrości i utylitarno -optymalny, stąd efektywny w sensie Pareto. Istnieje jednak inna alokacja ([0,5/16], [5/16,11/16], [11/16,1]) z profilem użyteczności lepszej od leksyminy.
Obliczenie
Dall'aglio przedstawia algorytm obliczania optymalnej dla leksyminy alokacji zasobów.
Zobacz też
- Sprawiedliwe krojenie ciasta - alokacja dająca każdemu agentowi równą użyteczność. Często alokacja egalitarna zbiega się z alokacją sprawiedliwą, ponieważ jeśli użyteczności są różne, mniejszą użyteczność można poprawić, usuwając trochę ciasta z agenta o większej użyteczności.
- Równoważność egalitarna – podobne pojęcie w kontekście homogenicznej alokacji zasobów.