Maximalizace podílu

Maximalizace podílu (MMD, angl.  Maximin share , MMS) je kritériem pro spravedlivé rozdělení objektů . Vzhledem k sadě objektů s různými hodnotami znamená maximální podíl 1 z n největší hodnotu, kterou lze získat rozdělením objektů na n částí a výběrem části s minimální hodnotou.

Rozdělení objektů mezi n agentů s různým skóre se nazývá MMD-fair , pokud každý agent dostane sadu, která je alespoň tak dobrá jako jeho 1 -out- n maximální podíl. MDM-justice navrhl Eric Budisch [1] jako oslabení kritéria proporcionality — každý agent obdrží sadu s hodnotou ne menší než rovnoměrné rozdělení (1/ n každého zdroje). Proporcionalitu lze zaručit, pokud jsou objekty dělitelné, ale ne, pokud jsou nedělitelné, i když mají všichni agenti shodné odhady. Naproti tomu spravedlivost MMD může být vždy zaručena pro identické agenty, takže se jedná o přirozenou alternativu proporcionality, i když jsou agenti odlišní.

Motivy a příklady

Stejné předměty. Předpokládejme nejprve, že m stejných předmětů by mělo být spravedlivě rozděleno mezi n lidí. V ideálním případě by každý člověk měl obdržet m / n objektů, ale může se ukázat, že pokud m není dělitelné n , je to nemožné, protože objekty jsou nedělitelné. Přirozeným kritériem druhé úrovně je zaokrouhlit m / n dolů na nejbližší celé číslo a dát každé osobě alespoň patro ( m / n ) objektů. Získat méně než podlahových( m / n ) objektů by bylo „příliš nespravedlivé“ – tuto nespravedlnost již nelze zakrýt nedělitelností objektů.

Odlišné předměty. Nyní předpokládejme, že objekty jsou odlišné a každý má jinou hodnotu. Nyní zaokrouhlení dolů na nejbližší celé číslo nemusí poskytnout požadované řešení. Předpokládejme například, že n = 3 a m = 5 a hodnota objektů je 1, 3, 5, 6, 9. Součet hodnot je 24 a toto číslo je dělitelné 3, takže v ideálním případě byste dali každý účastník předmět v hodnotě alespoň 8, ale to není možné. Nejvyšší hodnota, kterou můžeme všem agentům zaručit, je 7, což vyplývá z distribuce {1,6},{3,5},{9}.

Množina {1,6}, na které je dosaženo hodnoty maximinu, se nazývá "1-out-3 maximin-parts" - jedná se o nejlepší podmnožinu objektů, kterou lze vytvořit rozdělením původní množiny na 3 části a výběrem nejméně významný soubor. Proto je v tomto příkladu distribuce MMD spravedlivá tehdy a pouze tehdy, když hodnota, kterou každý agent obdrží, je alespoň 7.

Různá hodnocení. Předpokládejme nyní, že například každý agent vyhodnotí každý objekt jinak

Nyní má každý agent jinou sadu MMD:

Zde je distribuce MMD-fair, pokud dává Alici hodnotu alespoň 7, George alespoň 8 a Dina hodnotu alespoň 3. Například distribuce, ve které George získá první dva objekty {1,7 }, Alice dostane následující dvě {5,6} a Daina dostane objekt {17} je MMD-fair.

Výklad . Agentovo 1-out- n MMD lze interpretovat jako maximální užitek, který může agent získat z distribuce, pokud ostatní agenti mají stejné preference, pokud vždy dostane nejhorší podíl. Toto je minimální užitek, na který má agent (podle jeho názoru) nárok, na základě následujících argumentů: pokud ostatní agenti budou mít stejné preference jako já, existuje alespoň jedna distribuce, která mi takový užitek poskytne a která ostatní agenti o nic méně, proto nemají důvod mi dávat méně.

Alternativní výklad: nejpreferovanější množina pro agenta, garantovaná rozdělovačem v protokolu rozděl a vyber mezi soupeřícími protivníky – agent navrhne nejlepší alokaci a nastavené pravidlo výběru přenechá ostatním, zatímco zbývající množinu si vezme [2 ] .

Spravedlivost MMD lze také popsat jako výsledek následujícího procesu vyjednávání. Byla navržena určitá distribuce. Každý agent si může na takovou distribuci stěžovat a nabízet svou. Poté však musí umožnit ostatním, aby si vzali jejich podíly, zatímco on sám si vezme zbývající sadu. Proto si agent bude stěžovat na distribuci pouze v případě, že může nabídnout distribuci, ve které jsou všechny sady lepší než ta současná. Alokace je MMD spravedlivá tehdy a jen tehdy, pokud si na ni žádný z agentů nestěžuje, tj. pro každého agenta v jakékoli alokaci existuje soubor, který není lepší než podíl, který obdrží v aktuální alokaci.

Existence MMD-férových distribucí

Pokud má všech n agentů identické ocenění, MMD-spravedlivé rozdělení vždy podle definice existuje.

Pokud má stejné skóre pouze n -1 agentů, stále existuje spravedlivé rozdělení MMD a lze jej nalézt pomocí protokolu rozděl a vyber - n -1 identických agentů rozděluje objekty do n sad, z nichž každá není horší než MMD, pak n-tý agent vybere sadu s nejvyšším skóre a identičtí agenti seřadí zbývajících n -1 sad.

Zejména pro dva agenty vždy existuje spravedlivá distribuce MMD.

Bouvre a Lemaitre [2] provedli intenzivní simulace na náhodných datech pro více než 2 agenty a zjistili, že v každé studii existovalo spravedlivé rozdělení MMD. Prokázali, že MMD-férové ​​distribuce existují v následujících případech:

Procaccia a Won [3] , stejně jako Kurokawa [4] , zkonstruovali příklad s n= 3 agenty a m =12 objekty, ve kterém distribuce zaručuje každému agentovi MMD 1 ze 3. Navíc ukázali, že pro všechny existuje příklad s předměty.

Multiplikativní aproximace

Pro případ neexistence distribucí MMD navrhli Procaccia a Vaughn multiplikativní aproximaci pro MMD — distribuce se nazývá r-share MMD pro nějaký zlomek r z [0,1], pokud hodnota jakéhokoli činitele není menší než zlomek r hodnoty jeho/její MMD.

Představili algoritmus, který vždy najde -shared MMD, kde , a oddfloor( n ) je největší liché celé číslo nepřesahující n . Konkrétně se zmenšuje s rostoucím n a je vždy větší než . Jejich algoritmus běží v polynomiálním čase v m , pokud je n konstantní.

Amanatidis, Markakis, Nikzad a Saberi [5] prokázali, že v náhodně generovaných problémech s vysokou pravděpodobností existují MMD spravedlivé distribuce . Navrhli několik vylepšených algoritmů

Barman a Krishnamurti [6] představili

Navrhli Godsi, Hadzhigoyi, Sedigin a Yami [7]

Garg, McGlaflin a Taki [8] navrhli jednoduchý algoritmus pro 2/3dílné MMD, jehož analýza je jednoduchá.

V současnosti není známo, jaká je největší hodnota r , pro kterou vždy existuje r - částečné rozdělení MMD. Může to být číslo mezi 3/4 a 1 (kromě 1).

Amanatidis, Burmpas a Markakis [9] navrhli nezranitelné strategie pro přibližné distribuce MMD (viz také Strategicky spravedlivé rozdělení ):

Xin a Pingyang [10] studovali MMD spravedlivé rozdělení cel (objekty s negativním hodnocením) a ukázali, že částečné rozdělení MMD 9/11 vždy existuje.

Ordinální aproximace

Budish [1] navrhl další aproximaci rozdělení 1-out- n MMD - 1-out-( ) MMD (každý agent dostane alespoň tolik, kolik by mohl získat rozdělením do n + 1 sad a výběrem nejhorší z nich) . Ukázal, že přibližná konkurenční rovnováha se stejným příjmem vždy zaručuje 1-z-( ) MMD. Tato distribuce však může překročit počet dostupných objektů, a co je důležitější, překročit potřeby – součet sad distribuovaných všem agentům může být o něco větší než součet všech objektů. Taková chyba je přijatelná při přidělování míst studentům kurzu, protože malý nedostatek lze napravit přidáním malého počtu židlí. Ale klasický problém spravedlivého rozdělení předpokládá, že položky nelze přidat.

Pro jakýkoli počet agentů s aditivními odhady dává jakákoli spravedlivá distribuce bez závisti s výjimkou jednoho  ( EF1) každému agentovi alespoň 1-out-(2 n -1) MMD [11] . Rozdělení BZ1 lze nalézt například pomocí cyklického rozdělení objektů nebo cyklů procedury závisti .

Navíc distribuci 1-out-(2 n -2) MMD lze nalézt pomocí párování bez závisti [12] .

V současnosti není známo, jaké je minimum N , pro které vždy existuje rozdělení 1-out- N MMD. Může to být libovolné číslo mezi n +1 a 2 n -2. Nejmenší hodnota n , pro kterou takové N již není známo , je 4.

Počáteční MDM podmínku lze použít pro asymetrické agenty (agenty s rozdílným podílem díky nim) [13] .

Jiné algoritmické problémy

Některé základní algoritmy související s MMD:

MMD-férovost pro skupiny

Alokace se nazývá pairwise -maximin-share-fair ( PMMS -fair), pokud pro libovolnou dvojici agentů i  a j obdrží agent i alespoň své maximum 1-out-2- podíl omezený objekty z celkového souboru objekty i a j [16] .

Distribuce se nazývá group - wise-maximin-share-fair ( GMMS  -fair), pokud pro jakoukoliv podskupinu agentů velikosti k každý člen podskupiny obdrží svůj 1- z- k -maximin-share, omezený k objektům získaným touto podskupinou [17] .

Různé pojmy spravedlnosti souvisí s aditivním oceňováním následujícím způsobem.

Distribuce HMMD jsou zaručeny, pokud jsou odhady agentů buď binární nebo identické. S obecnými aditivními odhady existují 1/2-HMMD distribuce a lze je nalézt v polynomiálním čase [17] .

Viz také

Poznámky

  1. ↑ 1 2 Budish, 2011 , str. 1061–1103.
  2. ↑ 1 2 3 Bouveret, Lemaître, 2015 , str. 259.
  3. ↑ Procaccia, Wang, 2014 , str. 675–692.
  4. ↑ Archivovaná kopie . Získáno 26. února 2020. Archivováno z originálu dne 28. července 2019.
  5. ↑ Amanatidis, Markakis, Nikzad, Saberi, 2017 , str. 1–28.
  6. ↑ Barman, Krishnamurthy, 2017 , str. 647-664.
  7. ↑ Ghodsi, Hajiaghayi et al., 2018 , str. 539-556.
  8. ↑ Garg, McGlaughlin, Taki, 2018 , str. 20:1–20:11.
  9. ↑ Amanatidis, Birmpas, Markakis, 2016 , str. 31-37.
  10. ↑ Huang, Lu, 2019 .
  11. ↑ Segal-Halevi, Suksompong, 2019 , str. 103167.
  12. ↑ Aigner-Horev, Segal-Halevi, 2019 .
  13. ↑ Segal-Halevi, 2019 .
  14. ↑ Woeginger, 1997 , s. 149–154.
  15. ↑ Lang, Rothe, 2016 , str. 493–550.
  16. ↑ 1 2 Caragiannis, Kurokawa et al., 2019 , str. 12:1–12:32.
  17. ↑ 1 2 3 Barman, Biswas, Krishnamurthy, Narahari, 2018 .
  18. ↑ Závidět svobodu až k nejméně ceněnému dobru .  Viz Caragiannis, Kurokawa et al.

Literatura