Hasad qilmasdan narsalarni taqsimlash - Envy-free item allocation

Hasadsiz (EF) mahsulotni taqsimlash a adolatli buyumlarni taqsimlash adolat mezoni bo'lgan muammo hasad-ozodlik - har bir agent kamida boshqa agentlarning to'plami kabi yaxshi deb hisoblagan to'plamni olishi kerak.^{[1]:296–297}

Elementlar bo'linmasligi sababli, EF topshirig'i mavjud bo'lmasligi mumkin. Eng oddiy holat - bitta element va kamida ikkita agent mavjud bo'lganda: agar buyum bitta agentga tayinlangan bo'lsa, ikkinchisi hasad qiladi. Shuning uchun bo'linish protseduralari har xil yengillikni ta'minlaydi.

U mavjud bo'lganda hasadsiz ajratishni topish

Paketlardagi imtiyozli buyurtmalar: hasadgo'ylik

The ostki protsedura ikkita agent uchun to'liq EF ajratilishini topadi, agar shunday ajratish mavjud bo'lsa. Bu agentlardan buyumlar to'plamini saralashini talab qiladi, ammo asosiy yordam dasturi haqida ma'lumot talab qilinmaydi. Bu agentlarning afzallik munosabatlari qat'iy monoton bo'lgan har doim ishlaydi, lekin ular bor deb o'ylashning hojati yo'q javob beradigan afzalliklar. Eng yomon holatda, agentlar barcha mumkin bo'lgan to'plamlarni saralashlari kerak bo'lishi mumkin, shuning uchun ish vaqti elementlar sonida eksponent bo'lishi mumkin.

Buyurtma bo'yicha buyurtmalar: zarur / mumkin bo'lgan hasad-erkinlik

Odamlar uchun to'plamlarni tartiblashdan ko'ra, alohida narsalarni tartiblash osonroq. Barcha agentlar bor deb faraz qilsak javob beradigan afzalliklar, elementlar reytingini qisman to'plam darajasiga ko'tarish mumkin. Masalan, agar elementning darajasi w> x> y> z bo'lsa, unda javoblilik shundan iboratki, {w, x}> {y, z} va {w, y}> {x, z}, lekin hech narsani anglatmaydi {w, z} va {x, y}, {x} va {y, z} va boshqalar o'rtasidagi munosabatlar haqida.

Mahsulotlar reytingi berilgan:

• Ajratish albatta hasadsiz (NEF) agar unga ko'ra hasad qilmasa barchasi buyumlar reytingiga mos keladigan to'plamlar reytingi;
• Ajratish ehtimol hasadsiz (PEF) agar unga ko'ra hasad qilmasa kamida bitta buyumlar darajasiga mos keladigan to'plamning javob berish darajasi;
• Ajratish albatta Pareto-optimal (NPE) agar u Pareto-optimal bo'lsa barchasi buyumlar reytingiga mos keladigan to'plamlar reytingi;
• Ajratish ehtimol Pareto-optimal (PPE) agar u Pareto-optimal bo'lsa kamida bitta ma'lumotlar to'plamiga mos keladigan javobli to'plamlar reytingi.

Bouveret va Endriss va Lang^[2] qo'shimcha samaradorlik sharti bilan, xususan, to'liqlik yoki NPE yoki PPE bilan NEF / PEF ajratilishini topish bo'yicha algoritmik savollarni o'rganish. Umuman olganda, PEF hisoblashda oson, NEF esa hisoblashda qiyin.

EF ajratish mavjudligini hal qilish

Bo'sh ajratish har doim EF bo'ladi. Ammo biz EF-dan tashqari ba'zi bir samaradorlikni istasak, unda qaror muammosi hisoblash qiyin bo'ladi:^{[1]:300–310}

• EF yoki yo'qligini hal qilish to'liq ajratish mavjud NP tugadi. Bu faqat ikkita agent bo'lsa ham va ularning yordam dasturlari qo'shimchali va bir xil bo'lsa ham to'g'ri keladi, chunki bu holda EF ajratilishini topish bo'lim muammosi.^[3]
• Odil taqsimot mavjudligini hal qilish uchun, agar ikkitadan ortiq agent bo'lsa, eksponent ma'lumot (tovar sonida) talab qilinadi. Ikkita agent bo'lsa, aloqa kompleksi parametrlarning aniq kombinatsiyalariga bog'liq.^[4]
• EF yoki yo'qligini hal qilish Pareto samarali ajratish mavjud NP yuqorida: u shunday ${ displaystyle Sigma _ {2} ^ { textrm {P}}}$- to'liq bilan ham ikkilamchi kommunal xizmatlar^[5] va hatto qo'shimcha dasturlar.^[6] (${ displaystyle Sigma _ {2} ^ { textrm {P}}}$ noan'anaviy vaqt ichida echilishi mumkin bo'lgan muammolar sinfidir.

Muammoning ba'zi parametrlari sobit kichik konstantalar deb hisoblanganda qaror qabul qilish muammosi tarqalishi mumkin:^[7]

• Ob'ektlar sonini hisobga olgan holda m parametr sifatida PE + EF taqsimotining mavjudligini o'z vaqtida hal qilish mumkin ${ displaystyle O ^ {*} (m ^ {2m})}$ qo'shimcha yoki ikkilamchi yordam dasturlari uchun. Yordamchi dasturlar ikkilik va / yoki bir xil bo'lganda, ish vaqti tushadi ${ displaystyle O ^ {*} (m ^ {m})}$. Mana, yozuv ${ displaystyle O ^ {*}}$ boshqa parametrlarda polinom bo'lgan ifodalarni yashiradi (masalan, agentlar soni).
• Agentlar sonini hisobga olgan holda n parametr sifatida PE + EF ajratishining mavjudligi qiyin bo'lib qoladi. Ikkilamchi yordam dasturlari bilan, bu NP uchun ham qiyin n=2.^[5] Biroq, u endi NP-da va NP oracle bilan samarali echilishi mumkin (masalan, a SAT hal qiluvchi ). Bilan ${ displaystyle n geq 5}$ agentlari, bu bilan amalga oshirilishi mumkin ${ displaystyle 2 ^ {n + 1}}$bunday oracle va hech bo'lmaganda ${ displaystyle 2 ^ {n-4}}$ P = NP bo'lmasa, oracle kerak. Qo'shimcha yordam dasturlari bilan NP qiyin n=2.^[5] Bundan tashqari, bu shunday V [1] - to'liq w.r.t. barcha kommunal xizmatlar bir xil va unary-da kodlangan bo'lsa ham, agentlar soni.
• Ikkala agent sonini ham hisobga olgan holda n va eng katta yordam dasturi V parametrlar sifatida PE + EF taqsimotining mavjudligini o'z vaqtida hal qilish mumkin ${ displaystyle O ^ {*} ((m cdot V + 1) ^ {n ^ {2}} cdot mn ^ {2})}$ qo'shimcha dasturlardan foydalanish uchun dinamik dasturlash.
• Ikkala agent sonini ham hisobga olgan holda n va kommunal xizmatlar darajalarining soni z parametrlar sifatida bir xil qo'shimcha dasturlar uchun PE + EF ajratish mavjudligini an yordamida hal qilish mumkin butun sonli chiziqli dastur bilan ${ displaystyle d = n cdot z ^ {n}}$ o'zgaruvchilar; Lenstra algoritmi bunday ILPni o'z vaqtida hal qilishga imkon beradi ${ displaystyle O ^ {*} (d ^ {2.5d})}$.

Cheklangan hasad darajasi bilan ajratishni topish

Ko'p protseduralar "deyarli" hasadsiz ajratishni topadi, ya'ni hasad darajasi chegaralangan. "Deyarli" hasadgo'ylik haqida turli xil tushunchalar mavjud:

EF1 - ko'pi bilan bitta narsaga qadar hasadsiz

Ajratish deyiladi EF1 agar har bir A va B agentlari uchun, B to'plamidan ko'pi bilan bitta narsani olib tashlasak, A B ga hasad qilmaydi.^[8] EF1 ajratmasi har doim mavjud va uni turli xil protseduralar yordamida samarali topish mumkin, xususan:

• Barcha agentlar mavjud bo'lganda zaif qo'shimchalar kommunal xizmatlar, davra protokoli to'liq EF1 ajratilishini topadi. Zaif qo'shimchalar talab etiladi, chunki har bir agent har bir vaziyatda "eng yaxshi mahsulot" ni tanlashi kerak.
• Umuman olganda, barcha agentlar bir xilda ko'payadigan kommunal xizmatlarga ega bo'lganda, hasad-grafik protsedurasi to'liq EF1 ajratilishini topadi. Bitta talab - agentlar buyumlar to'plamini saralashi mumkin. Agar agentlarning baholari a bilan ifodalangan bo'lsa asosiy yordam dasturi funktsiyasi, keyin EF1 kafolati qo'shimcha talqinga ega: har bir agentning raqamli hasad darajasi eng ko'p maksimal-marginal-foydalidir - eng katta marginal yordam dasturi ushbu agent uchun bitta element.
• Agentlar o'zboshimchalik bilan yordam dasturlariga ega bo'lganda (qo'shimcha yoki monoton bo'lishi shart emas), the A-CEEI mexanizmi qisman EF1 ajratilishini qaytaradi. Bitta talab - agentlar buyumlar to'plamini saralashi mumkin. Kichik miqdordagi narsalar ajratilmagan bo'lib qolishi mumkin va oz sonli narsalar qo'shilishi kerak. Ajratilgan buyumlar bo'yicha Pareto-samarali hisoblanadi.
• The Nashning maksimal farovonligi algoritm kommunal xizmatlarning mahsulotini maksimal darajada oshiradigan to'liq ajratishni tanlaydi. Bu har bir agentdan har bir narsaning raqamli bahosini taqdim etishni talab qiladi va agentlarning yordam dasturlari qo'shimcha hisoblanadi. Natijada ajratish EF1 va Pareto-samarali.^[9]
• Turli xil boshqa algoritmlar Pareto-samarali EF1 ajratmalarini qaytaradi; qarang Taxminan adolatli mahsulot taqsimoti.
• O'zboshimchalik bilan monoton bahoga ega bo'lgan ikkita agent yoki qo'shimcha qiymatga ega uchta agent uchun EF1 taqsimotini elementlar sonidagi bir qator so'rovlar logaritmik yordamida hisoblash mumkin.^[10]
• O'zboshimchalik bilan foydali funktsiyalarga ega bo'lgan ikkita agent uchun (monoton bo'lishi shart emas), polinom vaqtida EF1 ajratilishini topish mumkin.^[11]
• O'zboshimchalik bilan monoton bahoga ega bo'lgan eng ko'p 4 agent uchun yoki n bir xil monoton baholarga ega agentlar, har doim ham EF1 taqsimoti mavjud ulangan (buyumlarga oldindan buyurtma berilganda, masalan, ko'chadagi uylar). Isbotida o'xshash algoritm ishlatiladi Simmons-Su protokollari. Qachon mavjud bo'lsa n > 4 ta agent, ulangan EF1 taqsimotining mavjudligi yoki yo'qligi ma'lum emas, lekin ulangan EF2 ajratish har doim mavjud.^[12]

EFx - har qanday narsaga qadar hasadsiz

Ajratish deyiladi EFx agar har bir A va B agentlari uchun, agar biz olib tashlasak har qanday B to'plamidan narsa, keyin A B ga hasad qilmaydi.^[13] EFx EF1dan qat'iyan kuchliroq: EF1 mahsulotni olib tashlash orqali hasadni yo'q qilishga imkon beradi eng qimmatli (A uchun) B to'plamidan; EFx mahsulotni olib tashlash orqali hasadni yo'q qilishni talab qiladi eng kam qimmatli (A uchun). EFx ajratmasi ba'zi bir maxsus holatlarda mavjud ekanligi ma'lum:

• Qachon mavjud bo'lsa ikkitasi agentlar yoki mavjud bo'lganda n agentlari bilan bir xil baholash. Bu holda leximin -optimal ajratish EFx va Pareto-optimal hisoblanadi. Ammo, bu hisoblash uchun juda ko'p so'rovlarni talab qiladi.^[14][11]
• Qachon mavjud bo'lsa n agentlari bilan qo'shimchani baholash, lekin tovarlar uchun eng ko'p ikki xil qiymat mavjud. Bunday holda, har qanday max-Nash-farovonlik ajratmasi EFx. Bundan tashqari, EFx ajratilishini hisoblash uchun samarali algoritm mavjud (garchi max-Nash-farovonligi shart emas).^[15]
• I bor bo'lganda n agentlari bilan qo'shimchani baholash, lekin ko'pi bilan ikki xil baholash turlari mavjud.^[16]
• Qachon bo'lsa uchta agentlari bilan qo'shimchani baholash. Bunday holda, ko'p polinomli vaqt algoritmi mavjud.^[17]

Ba'zi taxminlar ma'lum:

• 1/2 ga yaqin EFx taqsimoti (shuningdek, boshqa taxminiy-adolat tushunchasini qondiradi Maksimin xabardor) polinom vaqtida topish mumkin.^[18]
• Taxminan 0,618 ta EFx taqsimoti (bu ham EF1 va boshqa adolat tushunchalariga yaqinlashadi guruh bo'yicha maximin ulushi va juftlik bilan maximin ulushi ) polinom vaqtida topish mumkin.^[19]
• Har doim mavjud qisman EFx ajratmasi, bu erda Neshning farovonligi Nashning maksimal yordamining kamida yarmini tashkil qiladi. Boshqacha qilib aytganda, ba'zi narsalarni xayriya tashkilotiga topshirgandan so'ng, qolgan narsalar EFx usulida taqsimlanishi mumkin. Ushbu chegara imkon qadar yaxshiroqdir. Agentning har bir buyum uchun baholari nisbatan kichik bo'lgan katta bozorlarda algoritm deyarli optimal Nash farovonligi bilan EFx ga erishadi.^[20] Xayriya qilish kifoya n-1 dona va hech bir agent sovg'a qilingan narsalar to'plamiga havas qilmaydi.^[21]

Umuman olganda EFx ajratmasi mavjudmi degan savol ochiq. Eng kichik ochiq holat - bu qo'shimchalar bahosiga ega bo'lgan 4 ta agent.

Elementlar sonida bir qator so'rovlarni logaritmik talab qiladigan EF1dan farqli o'laroq, EFx ajratilishini hisoblash bir xil qo'shimchalar bahosiga ega ikkita agent bo'lsa ham, chiziqli sonli so'rovlarni talab qilishi mumkin.^[10]

EF1 va EFx o'rtasidagi yana bir farq shundaki, EFX ajratmalar soni ikkitadan kam bo'lishi mumkin (har qanday elementlar uchun), EF1 ajratmalar soni har doim elementlar sonida eksponent hisoblanadi.^[22]

EFm - bo'linadigan va bo'linmaydigan narsalar aralashmasi uchun taxminiy hasadsiz

Ayrim bo'linish stsenariylari ikkiga bo'linadigan va bo'linmaydigan narsalarni o'z ichiga oladi, masalan, bo'linadigan erlar va bo'linmaydigan uylar. Ajratish deyiladi EFm agar har bir A va B agentlari uchun:^[23]

• Agar B to'plami bo'linadigan ba'zi bir tovarlarni o'z ichiga olsa, unda A B ga hasad qilmaydi (EF taqsimotidagi kabi).
• Agar B to'plami faqat bo'linmas tovarlarni o'z ichiga olsa, B to'plamidan eng ko'p bitta narsani olib tashlaganidan keyin A (EF1 ajratishda bo'lgani kabi) B ga hasad qilmaydi.

EFm ajratish har qanday agentlar uchun mavjud. Biroq, uni topish uchun oracle kerak aniq bo'linish tort. Ushbu oracle holda EFm taqsimotini polinom vaqtida ikkita maxsus holatda hisoblash mumkin: umumiy qo'shilish bahosiga ega ikkita agent yoki bo'lak-chiziqli baholarga ega bo'lgan har qanday agent.

Pareto-optimallik bilan mos keladigan EF1dan farqli o'laroq, EFm unga mos kelmasligi mumkin.

Hasad nisbati minimallashtirilishi

Ajratish berilgan X, ning hasad qilish nisbatini aniqlang men yilda j kabi:

${ displaystyle EnvyRatio (X, i, j): = max (1, {u_ {i} (X_ {j}) over u_ {i} (X_ {i})})}$

shuning uchun bu nisbat 1 ga teng men hasad qilmaydi jva qachon kattaroq bo'lsa men hasad qiladi j.Tasvirning hasad qilish nisbatini quyidagicha aniqlang:

${ displaystyle EnvyRatio (X): = max _ {i, j} (EnvyRatio (X, i, j)}$

The hasad nisbatlarini minimallashtirish muammo - bu ajratishni topish muammosi X eng kichik hasad nisbati bilan.

Umumiy baholash

Umumiy baholashda allozatsiyani minimal hasad-nisbat bilan hisoblab chiqadigan har qanday deterministik algoritm eng yomon holatda tovar soniga nisbatan eksponent bo'lgan bir qator so'rovlarni talab qiladi.^[3]:3

Qo'shimcha va bir xil baholash

Qo'shimcha va bir xil baholash bilan:^[3]:4–6

• Quyidagi ochko'zlik algoritmi hasad nisbati eng kam 1,4 baravarga teng bo'lgan taqsimotni topadi:^[24]
  1. Buyurtmalarni kamayish qiymati bo'yicha buyurtma qiling;
  2. Ko'proq narsalar mavjud bo'lsa-da, keyingi elementni umumiy qiymati eng kichik agentga bering.
• Bor PTAS hasad nisbati minimallashtirish uchun. Bundan tashqari, o'yinchilar soni doimiy bo'lganda, FPTAS.

Qo'shimcha va turli xil baholashlar

Qo'shimcha va turli xil baholashlar bilan:^[25]

• Agar agentlar soni kirishning bir qismi bo'lsa, polinom vaqtida 1,5 ga teng bo'lgan taxminiy omilni olish mumkin emas, agar P = NP bo'lmasa.
• Agentlar soni doimiy bo'lsa, an bo'ladi FPTAS.
• Agentlar soni elementlar soniga teng bo'lganda, ko'p polinom-vaqt algoritmi mavjud.

Qisman hasadsiz ajratishni topish

The AL protsedurasi ikkita agent uchun EF ajratilishini topadi. Bu ba'zi narsalarni bekor qilishi mumkin, ammo yakuniy ajratish Pareto samarali quyidagi ma'noda: boshqa hech qanday EF taqsimoti biri uchun yaxshiroq, ikkinchisi uchun zaifligi uchun yaxshiroq emas. AL protsedurasi faqat agentlardan alohida elementlarni tartiblashini talab qiladi. Bu agentlar bor deb taxmin qiladi javob beradigan afzalliklar va ajratishni qaytaradi albatta hasadsiz (NEF).

The G'olibni sozlash tartibi ikkita agent uchun to'liq va samarali EF ajratilishini qaytaradi, lekin u bitta elementni kesishi kerak bo'lishi mumkin (alternativa, bitta element umumiy mulkda qoladi). Bu agentlardan har bir element uchun raqamli qiymat haqida hisobot berishni talab qiladi va ular bor deb hisoblaydi qo'shimcha dasturlar

Tasodifiy baholash bilan EF ajratmalarining mavjudligi

Agar agentlar bo'lsa qo'shimcha dastur ba'zi bir mustaqillik mezonlarini qondiradigan ehtimollik taqsimotidan kelib chiqadigan funktsiyalar va moddalar soni agentlar soniga nisbatan etarlicha ko'p bo'lsa, u holda EF taqsimoti mavjud yuqori ehtimollik bilan. Xususan:^[26]

• Agar buyumlar soni etarlicha ko'p bo'lsa: ${ displaystyle m = Omega (n log n)}$, keyin w.h.p. EF taqsimoti mavjud (m cheksizlikka borgan sari ehtimollik 1 ga boradi).
• Agar buyumlar soni etarlicha ko'p bo'lmasa, ya'ni. ${ displaystyle m = n + o (n)}$, keyin w.h.p. EF ajratmasi mavjud emas.

Hasad-erkinlik va boshqa adolatli mezonlarga nisbatan

• Har bir EF ajratmasi min-max-adolatli. Bu to'g'ridan-to'g'ri tartibli ta'riflardan kelib chiqadi va qo'shimchaga bog'liq emas.
• Agar barcha agentlarda bo'lsa qo'shimcha dastur funktsiyalari, keyin EF ajratish ham bo'ladi mutanosib va max-min-adolatli. Aks holda, EF taqsimoti mutanosib bo'lmasligi va hatto maksimal min-adolatsiz bo'lishi mumkin.
• A har bir ajratish raqobatdosh muvozanat teng daromadlardan ham hasad qilmaydi. Bu qo'shilishdan qat'iy nazar to'g'ri.^[8]
• Har bir Nash-optimal ajratish (kommunal xizmatlarning mahsulotini maksimal darajada oshiradigan ajratish) EF1.^[13]
• Guruh-hasad-ozodlik ikkiga bo'linadigan va bo'linmaydigan narsalarga taalluqli bo'lgan hasad-erkinlikni kuchaytirishdir.

Qarang Adolatli mahsulot taqsimoti tafsilotlar va ma'lumotnomalar uchun.

Xulosa jadvali

Quyida quyidagi stenografiyalar qo'llaniladi:

• ${ displaystyle n}$ = bo'linishda qatnashadigan agentlar soni;
• ${ displaystyle m}$ = bo'linadigan narsalar soni;
• EF = hasadsiz, EF1 = 1-moddadan tashqari (EFdan zaif) hasadsiz, MEF1 = 1-moddadan tashqari marginal-hasadsiz (EF1dan zaif).
• PE = Pareto-samarali.

Ism	#tartiblar	Kiritish	Afzalliklar	# so'rovlar	Adolat	Samaradorlik	Izohlar
Pastki qism	2	To'plamlar reytingi	To'liq monoton	${ displaystyle 2 ^ {m}}$	EF	Bajarildi	Agar va faqatgina - agar EFning to'liq taqsimoti mavjud bo'lsa
AL	2	Mahsulotlar reytingi	Zaif qo'shimchalar	${ displaystyle Poly (m)}$	Albatta-EF	Qisman, lekin boshqa NEF tomonidan pareto-dominant emas
G'olib sozlangan	2	Mahsulotni baholash	Qo'shimcha	${ displaystyle Poly (m)}$	EF va teng huquqli	Pe	Bitta narsani ajratish mumkin.
Dumaloq aylanish	${ displaystyle n}$	Mahsulotlar reytingi	Zaif qo'shimchalar	${ displaystyle m}$	Albatta-EF1	Bajarildi
Hasad-graf	${ displaystyle n}$	To'plamlar reytingi	Monoton	${ displaystyle O (mn ^ {3})}$	EF1	Bajarildi
A-CEEI	${ displaystyle n}$	To'plamlar reytingi	Har qanday	?	EF1 va ${ displaystyle (n + 1)}$-maksimin-ulush	Qisman, lekin pe w.r.t. ajratilgan narsalar	Shuningdek, taxminan strategiyaga chidamli agentlar ko'p bo'lganda.
Maksimal-Nash-farovonlik[13]	${ displaystyle n}$	Mahsulotni baholash	Qo'shimcha	NP-hard (lekin alohida holatlarda taxminlar mavjud)	EF1 va taxminan-${ displaystyle n}$-maksimin-ulush	Pe	Submodular yordam dasturlari bilan ajratish PE va MEF1.

Shuningdek qarang

• Maksimin-ulush elementlarini taqsimlash - adolatning boshqa mezonlari.
• Ijara uyg'unligi va Hasadsiz narxlanish - pullik to'lovlar orqali hasad erkinligiga erishiladigan ikkita variant.

Adabiyotlar