Төмен кесілген процедура - Undercut procedure

The астынан кесу процедурасы үшін рәсім болып табылады әділетті тағайындау екі адам арасында. Бұл толықтай болады қызғанышсыз заттар тағайындау мұндай тағайындау болған кезде. Оны Брамс пен Килгур және Кламлер ұсынды[1] және Азиз жеңілдеткен және кеңейтілген.[2]

Болжамдар

Төмендетілген процедура адамдарға келесі әлсіз болжамдарды ғана қажет етеді:

  • Әр адамның әлсізі бар артықшылықты қатынас элементтердің жиынтықтары бойынша.
  • Әрбір артықшылық қатынас болып табылады қатаң монотонды: әр жиынтық үшін және элемент , адам қатаң түрде көреді дейін .

Бұл емес агенттер бар деп болжады жауап беретін артықшылықтар.

Негізгі ой

Төмендегі процедураны жалпылама ретінде қарастыруға болады бөліп ал бөлінетін ресурстардан бөлінбейтін ресурстарға протокол. Бөлу және таңдау протоколы бір адамнан ресурстарды екі тең бөлікке бөлуді талап етеді. Бірақ, егер ресурс бөлінбейтіндігімен қамтылса, дәл тең кесу мүмкін болмауы мүмкін. Тиісінше, төмен түсірілген процедура жұмыс істейді теңдей кесулер. Адамның шамамен тең кесіндісі - бұл элементтер жиынтығының екі біріктірілген ішкі жиынға бөлінуі (X, Y), мысалы:

  • Адам әлсіз X-тен Y-ге артықшылық береді;
  • Егер қандай да бір элемент X-тен Y-ге ауыстырылса, онда адам қатаң түрде Y-ден X-ге дейін (яғни, барлық x-дегі X үшін адам) дейін ).

Процедура

Әр адам өзінің барлық теңестірілгендері туралы хабарлайды. Екі жағдай бар:

  • 1-жағдай: есептер әр түрлі, мысалы, Элис үшін тең дәрежеде, бірақ Джордж үшін емес (X, Y) бөлімі бар. Содан кейін, бұл бөлім Джорджға ұсынылады. Джордж оны қабылдай да, қабылдамай да алады:
    • Джордж бөлімді қабылдайды, егер ол Y-ден X-ге артық болса, онда Элис Х-ны, ал Джордж Y-ді қабылдайды және нәтижесінде бөліну қызғанышсыз болады.
    • Джордж бөлімді жоққа шығарады, егер ол X-тен Y-ге артықшылық берсе, (X, Y) Джордж үшін тең дәрежеде емес. Демек, Дж-де Джордж ұнататын x элементі бар дейін . Джордж хабарлайды ; біз Джордж деп айтамыз ішкі сызықтар X. (X, Y) Элис үшін теңдей кесінді болғандықтан, Алиса көреді дейін . Содан кейін Джордж қабылдайды және Алиса алады және нәтижесінде бөлу қызғанышсыз болады.
  • 2-жағдай: есептер бірдей, яғни Алиса мен Джордждың бірдей кесінділер жиынтығы бар. Содан кейін, процедура олардан тең кесінділердің біреуі дәл тең кесінді екенін сұрайды. Қатаң-монотондылық жорамалы бойынша, (X, Y) дәл тең кесінді, егер-және-тек, егер екеуі де (X, Y) және (Y, X) тең тең кесінділер болса. Сондықтан, 2-жағдайда Алиса мен Джордж дәл бірдей-бірдей кесінділер жиынтығына ие. Екі кіші жағдай бар:
    • Оңай жағдай: дәл тең кесінді бар (X, Y). Сонда бір адам (кім болса да) Х, ал екіншісі Y алады және бөліну қызғанышсыз болады.
    • Қиын жағдай: дәл тең кесу жоқ. Содан кейін процедура қайтарады және «қызғанышсыз бөлу жоқ» деп хабарлайды.

Процедураның дұрыстығын дәлелдеу үшін, қиын жағдайда қызғанышсыз бөлу болмайтынын дәлелдеу жеткілікті. Шынында да, қызғанышсыз бөлу бар (X, Y). Біз қатты жағдайда болғандықтан, (X, Y) дәл тең кесінді емес. Сонымен, бір адам (мысалы, Джордж) Y-тен X-ге дейін, ал екінші бір адам (Alice) X-ден Y-ге әлсіз артықшылық береді. Егер (X, Y) Алиса үшін тең кесінді болмаса, онда біз кейбір элементтерді X-ден жылжытамыз Y-ге дейін, біз Элис үшін теңдей кесінді бөлімді (X ', Y') алғанға дейін. Элис әлі де X 'мен Y' -ді әлсіз көреді. Монотондылық жорамалы бойынша Джордж әлі күнге дейін Y-ден X-ге дейін артықшылық береді. Бұл дегеніміз (X ', Y') Джордж үшін тең дәрежеде емес. Бірақ қиын жағдайда екі агент те бірдей кесілген жиынтыққа ие - қайшылық.

Жұмыс уақытының күрделілігі

Ең нашар жағдайда агенттерге барлық мүмкін бумаларды бағалау қажет болуы мүмкін, сондықтан жұмыс уақыты элементтер саны бойынша экспоненциалды болуы мүмкін.

Бұл таңқаларлық емес, өйткені астыртын процедураны шешу үшін қолдануға болады бөлім мәселесі: екі агент те бірдей және аддитивті бағалауға ие деп болжанып, төменгі процедураны жүргізеді; егер ол қызғанышсыз бөлуді тапса, онда бұл бөлу тең бөлімді білдіреді. Бөлім мәселесі NP-мен аяқталғандықтан, оны полиномдық уақыт алгоритмімен шешу мүмкін емес.

Тең емес құқықтар

Агенттер тең емес құқықтарға ие болған кезде, сондай-ақ, асты сызылған процедура жұмыс істей алады.[2] Әр агент делік бөлшекке құқылы заттардың. Содан кейін, шамамен тең кесінді анықтамасы (агент үшін) ) келесідей өзгертілсін:

  • , және
  • Барлық x in X үшін

Ұрпақ кезеңі

Бастапқыда,[1] астына түсірілген процедураның алдында келесілер болады генерация фазасы:

  • Үстелде заттар бар:
    • Әр адам өзінің ең жақсы заты туралы есеп береді.
      • Егер есептер әр түрлі болса, онда әр адам өзінің ең жақсы затын алады.
      • Егер есептер бірдей болса, онда ең жақсы элемент а-ға қойылады даулы үйінді.

Содан кейін жоғарыда сипатталған төмен түсірілген процедура тек таласқан үйіндіде орындалады.

Бұл фаза бөлу процедурасын тиімдірек етуі мүмкін: таласқан қадалар бастапқы элементтер жиынтығынан кішірек болуы мүмкін, сондықтан теңдей кесінділерді есептеу және есеп беру оңайырақ болуы мүмкін.

АлисаДжордж
w91
х84
ж73
з62

Алайда генерация кезеңінің бірнеше кемшіліктері бар:[2]

  1. Бұл процедураны қызғанышсыз бөлуді өткізіп жіберуі мүмкін. Мысалы, төрт элемент бар делік және олардың бағасы көршілес кестедегідей. Алисаға {w, z} және Джорджға {x, y} беретін бөлу қызғанышсыз. Шынында да, оны ашық сызылған процедура арқылы табуға болады, өйткені бөлім ({w, z}, {x, y}) Алиса үшін теңдей кесінді, бірақ Джордж үшін емес, ал Джордж бұл бөлімді қабылдайды. Бірақ генерация кезеңінде бастапқыда Алиса w алады, ал Джордж х алады және басқа элементтер {y, z} дауласқан үйіндіге қойылады және таласқан үйінді қызғанышсыз бөлу болмайды, сондықтан процедура сәтсіз аяқталады.
  2. Бұл адамдардан тағы қандай заттарды алатынын білмей, өздерінің «ең жақсы затын» таңдауды талап етеді. Бұл заттар деген болжамға сүйенеді тәуелсіз тауарлар. Сонымен қатар, ол a-ға сүйенеді жауаптылық жорамал: егер бумада бір зат жақсырақ затпен ауыстырылса, онда алынған бума жақсырақ болады (ол тығыз байланысты әлсіз қоспа артықшылықтар).
  3. Агенттер тең емес шағымдар болған кезде жұмыс істемейді.
  4. Ол стратегиялық айла-шарғыға ұшырайтын дәйекті бөлуге сүйенеді.

Пайдаланылған әдебиеттер

  1. ^ а б Брамс, Стивен Дж .; Килгур, Д.Марк; Кламлер, Кристиан (2011). «Төмендетілген процедура: бөлінбейтін заттарды қызғанышсыз бөлудің алгоритмі» (PDF). Әлеуметтік таңдау және әл-ауқат. 39 (2–3): 615. дои:10.1007 / s00355-011-0599-1.
  2. ^ а б c Азиз, Харис (2015). «Төмендетілген процедура туралы жазба». Әлеуметтік таңдау және әл-ауқат. 45 (4): 723–728. arXiv:1312.6444. дои:10.1007 / s00355-015-0877-4.