Simmons-Su protokollari - Simmons–Su protocols

The Simmons-Su protokollari uchun bir nechta protokollar mavjud hasadsiz bo'linish. Ular asoslanadi Sperner lemmasi. Ushbu protokollarning mohiyati shundaki, ular sheriklarning afzalliklariga ozgina cheklovlar qo'yadilar va sheriklardan faqat "qaysi qismni afzal ko'rasiz?" Kabi oddiy savollarni so'rashadi.

Bir qator tegishli muammolarni hal qilish uchun protokollar ishlab chiqildi:

Kekni kesish

In hasadsiz tortni kesish muammo, "pirojnoe" (heterojen bo'linadigan resurs) o'rtasida bo'linishi kerak n kek qismlariga nisbatan turli xil imtiyozlarga ega bo'lgan sheriklar. Kekni ikkiga bo'lish kerak n (a) har bir sherik bitta bog'langan qismni oladi va (b) har bir sherik uning parchasi boshqa qismlarga qaraganda (zaifroq) yaxshiroq deb hisoblaydi. Ushbu muammoni hal qilish uchun protokol tomonidan ishlab chiqilgan O'rmon Simmons 1980 yilda, bilan yozishmalarda Maykl Starbird. Bu birinchi tomonidan e'lon qilingan Frensis Su 1999 yilda.[1]

Kesilgan to'plam (ya'ni pirojniyning ma'lum bir qismi) berilgan n dona), sherik deymiz afzal ko'radi agar u bu qism boshqa barcha qismlarga qaraganda kuchsizroq ekanligiga ishonsa. "Zaif" degani sherik buyum va bir yoki bir nechta boshqa buyumlar o'rtasida befarq bo'lishi mumkinligini anglatadi, shuning uchun u (bog'lanish holatlarida) bir nechta bo'laklarni "afzal ko'rishi" mumkin.

Protokol sheriklarning afzalliklari bo'yicha quyidagi taxminlarni keltiradi:

  1. Boshqa sheriklarda mustaqillik: Afzallik sherikga va butun to'plamga bog'liq, ammo boshqa sheriklar tomonidan qilingan tanlovga emas.
  2. Och sheriklar: Hamkorlar hech qachon bo'sh bo'lakni afzal ko'rishmaydi.
  3. Topologik jihatdan yopiq afzalliklar to'plamlari: Kesilgan to'plamlarning konvergent ketma-ketligi uchun afzal bo'lgan har qanday qism, cheklovli kesmada afzallik beriladi. Masalan, sherik birinchi kesilgan birinchi kesilgan barcha to'plamlarda birinchi qismni afzal ko'rsa x > 0.2 ga teng va birinchi kesilgan barcha kesilgan to'plamlarda ikkinchi qismni afzal ko'radi x <0,2, keyin birinchi kesma joylashgan kesmada x = 0,2 bu sherik ikkala qismni teng ravishda afzal ko'radi.

Yopiqlik sharti ijobiy istakka ega bo'lgan kekning bitta nuqtasi mavjudligini istisno qiladi.[nega? ]

Ushbu taxminlar juda yumshoq: uchun boshqa protokollardan farqli o'laroq adolatli tort kesish, yordamchi funktsiyalar emas qo'shimchalar yoki monotonik bo'lishi kerak.

Protokol 1 o'lchovli kesma to'plamlarni ko'rib chiqadi. Masalan, pirojnoe 1 o'lchovli interval bo'lishi mumkin [0,1] va har bir bo'lak oraliq; yoki pirojnoe uzunroq tomoni bo'ylab kesilgan to'rtburchak bo'lishi mumkin, shunda har bir bo'lak to'rtburchak bo'ladi. Har qanday kesilgan to'plam bilan ifodalanishi mumkin n raqamlar xmen, men = 1, ..., n, qayerda xmen ning uzunligi menqism. Kekning umumiy uzunligi 1 ga teng, deb taxmin qilamiz x1 + ... + xn = 1. Mumkin bo'linmalar maydoni shunday qilib (n - 1) bilan o'lchovli sodda n tepaliklar Rn. Protokol ushbu simpleksda quyidagi tarzda ishlaydi:

  1. Oddiy bo'laklarni istalgan o'lchamdagi kichikroq soddaliklarga uchburchak qilib oling.
  2. Uchburchakning har bir tepasini bitta sherigiga tayinlang, shunda har bir sub-simpleksda bo'ladi n turli xil yorliqlar.
  3. Uchburchakning har bir tepasi uchun uning egasidan so'rang: "Agar pirojnoe shu nuqtada ko'rsatilgan kesilgan to'plam bilan kesilgan bo'lsa, qaysi qismini tanlaysiz?". Kerakli parcha soni bo'yicha ushbu tepalikka belgi qo'ying.

Yaratilgan yorliq talablarga javob beradi Spernerning lemma ranglanishi:

  • Asl simpleksning har bir tepasi kesilgan to'plamga mos keladi, unda bitta parcha butun tortni o'z ichiga oladi va qolgan qismlar bo'sh bo'ladi. "Och sheriklar" taxminiga ko'ra, ushbu tepalik egasi ushbu qismni afzal ko'rishi kerak. Shuning uchun katta simpleks tepalari yorliqlari har xil.
  • Asl simpleksning har bir tomoni / yuzi ba'zi qismlar bo'sh bo'lgan kesma to'plamlarga to'g'ri keladi va bo'sh bo'lmagan qismlar bu tomonning tepalariga to'g'ri keladi. "Och sheriklar" taxminiga ko'ra, egalar faqat bo'sh bo'lmagan qismlarni afzal ko'rishlari kerak, shuning uchun bu tomonlarning uchburchak tepaliklarida tegishli tepalarda paydo bo'ladigan yorliqlardan bittasi bo'lishi mumkin.

Demak, Sperner lemmasiga binoan yorliqlar har xil bo'lgan kamida bitta sub-simpleks bo'lishi kerak. №2 bosqichda biz ushbu kichik simpleksning har bir tepasini boshqa sherikga tayinladik. Shuning uchun biz topdik n turli xil sheriklar turli xil pirojniylarni afzal ko'radigan juda o'xshash kesilgan to'plamlar.

Endi biz sub-simpleksni pastki sub-soddaliklarning ingichka meshiga uchburchak qilib, jarayonni takrorlashimiz mumkin. Biz bitta nuqtaga yaqinlashadigan kichikroq va kichikroq soddaliklar ketma-ketligini olamiz. Ushbu nuqta bitta kesilgan to'plamga mos keladi. "Afzalliklar to'plamlari yopiq" degan taxmin bo'yicha, har bir sherik turli xil qismlarni afzal ko'radi. Bu hasadsiz bo'lim!

Hasadsiz bo'lim mavjudligi ilgari isbotlangan,[2] ammo Simmonsning isboti ham konstruktiv yaqinlashuv algoritmini beradi. Masalan, ma'lum bir er uchastkasini ajratish kerak deb taxmin qiling va sheriklar ortiqcha yoki minus 1 santimetr farq ular uchun ahamiyatsiz ekanligiga rozi bo'lishdi. Keyin asl simpleksni yon uzunligi 1 sm dan kam bo'lgan soddaliklarga uchburchak qilish mumkin. Keyin sub-simpleksdagi barcha yorliqlar har xil bo'lgan har bir nuqta (taxminan) hasadsiz bo'limga to'g'ri keladi.

Simmons protokoli har bir sherikga juda ko'p miqdordagi maydalashni tayinlashi mumkin bo'lgan boshqa hasadsiz protokollardan farqli o'laroq, har bir sherikga bitta bog'langan qismni beradi. Bundan tashqari, agar asl kek to'rtburchaklar bo'lsa, unda har bir parcha to'rtburchakdir.

Ushbu algoritm nashr etilganidan bir necha yil o'tgach, bog'langan qismlarga ega bo'lgan hasadsiz bo'limlarni cheklangan protokollar bilan topish mumkin emasligi isbotlandi.[3] Demak, taxminiy algoritm biz cheklangan vaqt ichida umid qiladigan eng yaxshisidir. Hozirda Simmons algoritmi - bu ulangan qismlar bilan hasadsiz tortni kesish uchun yagona taxminiy algoritm.

Simmons algoritmi - bu amalga oshirilgan va Internetga joylashtirilgan bir nechta adolatli bo'linish algoritmlaridan biridir.[4]

Algoritmning bir yaxshi tomoni shundaki, sheriklardan so'raladigan so'rovlar juda oddiy: ular har bir bo'limda qaysi qismini afzal ko'rishlari kerak. Bu boshqa algoritmdan farqli o'laroq, masalan, "1/3 qiymatiga ega bo'lakni kesib olish" va hokazo kabi raqamli so'rovlar.

Ish vaqti murakkabligi

Bog'langan qismlar bilan hasadsiz bo'linishni yuqoridagi protokol yordamida har qanday aniqlikka yaqinlashtirish mumkin bo'lsa-da, yaqinlashish uzoq vaqt talab qilishi mumkin. Jumladan:[5]

  • Agar kommunal funktsiyalarga faqat oracle orqali kirish mumkin bo'lsa, hasadga erishish uchun so'rovlar soni ϵ dan kam .
  • Yordamchi funktsiyalar polinomial vaqt algoritmlari bilan aniq berilsa, hasadsiz tortni kesish muammosi a ni topish bilan bir xil murakkablikka ega Brouwer belgilangan nuqta, ya'ni PPAD - to'liq.

Ijara kelishuvi

Asosiy maqola: Ijara kelishuvi § Su

Ushbu muammoda, n uy bekalari ijaraga olishga qaror qilishdi n- uy egasi tomonidan belgilangan ijaraga beriladigan xonali uy. Har bir uy bekasi turli xil imtiyozlarga ega bo'lishi mumkin - biri katta xonani, boshqasi ko'rinadigan xonani va boshqalarni afzal ko'rishi mumkin. Quyidagi ikkita muammo bir vaqtning o'zida echilishi kerak: (a) har bir sherikga xona ajratib bering, (b) ijara haqini aniqlang. har bir sherik to'lashi kerak, shunda to'lovlar summasi ijara haqining umumiy miqdoriga teng bo'ladi. Topshiriq bo'lishi kerak hasadsiz chunki har bir sherik o'z xonasi + ijarasini boshqa uchastkalarga nisbatan zaifroq afzal ko'radi, ya'ni hech bir sherik bu xonaga ajratilgan ijaraga boshqa xonani olishni istamaydi. Ushbu muammoni hal qilish uchun protokol tomonidan ishlab chiqilgan Frensis Su 1999 yilda.[1]

Fikr quyidagicha. Umumiy ijarani 1 ga normalizatsiya qiling. Keyin har bir narxlash sxemasi an nuqtasidir - bilan o'lchovli oddiy tepaliklar . Su protokoli ushbu simpleksning dualizatsiyalangan versiyasida Simmons-Su protokollariga o'xshash tarzda tortni kesish uchun ishlaydi: dual simplex triangulyatsiyasining har bir uchi uchun, ma'lum bir narx sxemasiga mos keladi, u egasi sherikdan so'raydi " ushbu narxlash sxemasida qaysi xonani afzal ko'rasiz? ". Buning natijasida ikkita simpleksning Sperner ranglanishi paydo bo'ladi va shu bilan xonalar va ijaralarning taxminiy hasadsiz tayinlanishiga mos keladigan kichik kichik simpleks mavjud.

[6] va [7] Ijara kelishuvi protokoli bo'yicha ommalashtirilgan tushuntirishlarni taqdim etish.[8] va [9] on-layn rejimida amalga oshirishni ta'minlash.

Qarang Ijara uyg'unligi ushbu muammoga ko'proq echim topish uchun.

Chore bo'limi

Ushbu muammoda, ikkiga bo'linishi kerak bo'lgan ish bor n sheriklar, masalan, katta maydonda maysazor kesish.

Ijara kelishuvi protokoli, ijara to'lovlarini uy vazifasi deb o'ylash va xonalarni e'tiborsiz qoldirish orqali ishlarni taxminiy rashksiz tayinlashga erishish uchun ishlatilishi mumkin. Uy ishlarining bo'linishiga, ularga sarf qilingan vaqtni taqsimlash orqali erishish mumkin.[1]

Ko'p tortni kesish

Ushbu muammoni hal qilishda ikkita yoki undan ko'p pirojniy bir vaqtning o'zida ikkala yoki undan ortiq sheriklarga bo'linib, har bir sherikga har bir tortdan bitta bo'lak berilishi kerak. Albatta, agar imtiyozlar mustaqil bo'lsa (ya'ni, ajratish foydasi - bu har bir keksdagi ajratilgan qismdan olingan kommunal xizmatlarning yig'indisi), unda muammoni bitta tortga bo'lish usullari bilan hal qilish mumkin - shunchaki hasadsiz bo'linishni bajaring har bir tort alohida. Hamkorlar keklarga nisbatan imtiyozlarni bog'lashganida, qiziqish paydo bo'ladi, unda sherik afzal ko'rgan bitta pirojniy qismiga unga ajratilgan boshqa pirojnoe ta'sir qiladi. Masalan, agar "pirojnoe" ketma-ket ikki kun ichida ish smenalari vaqti bo'lsa, odatdagi ishchi har kuni bir xil smenada ishlashni afzal ko'rishi mumkin (masalan, ertalab-ertalab yoki kechqurun-kechqurun), keyin har xil smenada ishlash.

Ushbu muammoni 2 sherik va 2 yoki 3 pirojnoe uchun echimi 2009 yilda nashr etilgan.[10] Agar pirojnoe soni bo'lsa m, va har bir pirojnoe bo'linadi k bo'laklar, keyin bo'limlar maydoni an bilan ifodalanishi mumkin n-vertex d- o'lchovli politop, qayerda d=m(k - 1) va n = km. A Sperner lemmasining politoplarga umumlashtirilishi[11] agar ushbu politop uchburchak shaklida va tegishli tarzda etiketlangan bo'lsa, hech bo'lmaganda borligiga kafolat beradi n − d to'liq yorliqli pastki oddiyliklar; ushbu soddaliklarning har biri (taxminiy) hasadsiz taqsimotga mos keladi, unda har bir sherik qismlarning turli xil kombinatsiyasini oladi. Biroq, kombinatsiyalar bir-biriga mos kelishi mumkin: bir sherik "ertalab" va "kechqurun" smenalarini olishi mumkin, ikkinchisi esa "kechqurun" va "oqshom" ni olishi mumkin. Garchi bular turli xil tanlovlar bo'lsa-da, ular mos kelmaydi. 4-qism [10] agar ikkala sherikga hasadsiz bo'linishni bo'lak bo'laklari bilan ajratib bo'lmasligini isbotlasa m = k = 2, lekin har doim ham mumkin m = 2 va k = 3 (ya'ni kamida bitta tort uchta bo'lakka bo'linadi, har bir sherik har bir tortdan bitta bo'lak oladi va kamida bitta bo'lak tashlanadi). Shunga o'xshash natijalar uchta kek uchun isbotlangan.

Shuningdek qarang

Adabiyotlar

  1. ^ a b v Su, F. E. (1999). "Ijara uyg'unligi: Spernerning Lemmasi adolatli bo'limda". Amerika matematikasi oyligi. 106 (10): 930–942. doi:10.2307/2589747. JSTOR  2589747.
  2. ^ Stromkist, Valter (1980). "Kekni qanday qilib odilona kesib olish kerak". Amerika matematikasi oyligi. 87 (8): 640–644. doi:10.2307/2320951. JSTOR  2320951.
  3. ^ Stromvist, Valter (2008). "Cheksiz hasadsiz tort bo'linishlarini cheklangan protokollar bilan topish mumkin emas" (PDF). Kombinatorika elektron jurnali. 15. doi:10.37236/735. Olingan 26 avgust 2014.
  4. ^ Frensis Su, Elisha Peterson va Patrik Winograd tomonidan amalga oshiriladigan dastur quyidagi manzilda mavjud: https://www.math.hmc.edu/~su/fairdivision/
  5. ^ Deng X .; Qi, Q .; Saberi, A. (2012). "Hasadsiz tortni kesish uchun algoritmik echimlar". Amaliyot tadqiqotlari. 60 (6): 1461. doi:10.1287 / opre.1120.1116. S2CID  4430655.
  6. ^ Quyosh, Albert. "Ijarani taqsimlash uchun uchburchakdan boshlang". NY Times. Olingan 26 avgust 2014.
  7. ^ Prokaktsiya, Ariel. "Adolatli bo'linish va faylasuflarning shivirlashi muammosi". Tyuringning ko'rinmas qo'li. Olingan 26 avgust 2014.
  8. ^ https://www.math.hmc.edu/~su/fairdivision/
  9. ^ https://www.nytimes.com/interactive/2014/science/rent-division-calculator.html
  10. ^ a b Klotye, J .; Nyman, K. L .; Su, F. E. (2010). "Ikki o'yinchi hasadsiz ko'p tortli bo'linma". Matematik ijtimoiy fanlar. 59: 26–37. arXiv:0909.0301. doi:10.1016 / j.mathsocsci.2009.09.002. S2CID  15381541.
  11. ^ De Loera, J. A.; Peterson, E .; Edvard Su, F. (2002). "Sperner Lemmasining polytopal umumlashtirilishi". Kombinatoriya nazariyasi jurnali, A seriyasi. 100: 1–26. doi:10.1006 / jcta.2002.3274.