Дәрежелік-максималды бөлу - Rank-maximal allocation

Дәрежелік-максималды (RM) үлестіру үшін ереже әділ бөлу бөлінбейтін заттар. Кейбір заттарды адамдар арасында бөлуіміз керек делік. Әр адам заттарды жақсыдан жаманға қарай бағалай алады. RM ережесінде біз мүмкіндігінше көп адамға ең жақсы затты беруіміз керек делінген. Осыған сәйкес, біз мүмкіндігінше көп адамға келесі ең жақсы (# 2) затты беруіміз керек және т.б.

Әр адам бір затты алуы керек ерекше жағдайда (мысалы, «заттар» тапсырма болғанда және әр тапсырманы жалғыз адам орындауы керек болғанда), проблема деп аталады максималды сәйкестік немесе ашкөз сәйкестік.

Идеясы сол сияқты утилитарлық торт кесу мұндағы мақсат - барлық қатысушылардың коммуналдық қызметтерінің максималды сомасын арттыру. Алайда утилитарлық ереже жұмыс істейді негізгі (сандық) утилиталық функциялар, ал RM ережесі жұмыс істейді коммуналдық қызметтер (рейтинг).

Анықтама

Бірнеше заттар мен бірнеше агенттер бар. Әр агентте жалпы тапсырыс заттар бойынша. Агенттер кейбір заттар арасында немқұрайлы болуы мүмкін; әр агент үшін біз бірдей деңгейдегі заттарды қамтитын заттарды эквиваленттік сыныптарға бөле аламыз. Мысалы, егер Алистің қалауы-қатынасы болса x> y, z> w, бұл Алистің бірінші таңдауы х екенін білдіреді, ол оған барлық басқа заттарға қарағанда жақсы; Алистің екінші таңдауы - оның көзінде бірдей жақсы, бірақ х-ке тең емес y және z; және Элистің үшінші таңдауы - бұл w, ол оны барлық заттардан нашар деп санайды.

Заттардың агенттерге бөлінуі үшін біз оны құрамыз ранг-вектор келесідей. Вектордағы №1 элемент - бұл иелері үшін бірінші таңдау болып табылатын элементтердің жалпы саны; № 2 элемент - бұл иелері үшін екінші таңдау болып табылатын заттардың жалпы саны; және тағы басқа.

A максималды дәрежеде бөлу бұл ранг-вектор максимум болатын (лексикографиялық тәртіпте).

Мысал

X y және z үш элементті үш агенттің арасында бөлу керек, олардың рейтингі:

  • Алиса: x> y> z
  • Боб: x> y> z
  • Карл: y> x> z

Бөлу кезінде (х, ж, з), Алиса бірінші таңдауды алады (х), Боб өзінің екінші таңдауын алады (ж) және Карл өзінің үшінші таңдауын алады (з). Ранк-вектор осылайша (1,1,1) болады.

Бөлу кезінде (х,з,ж), Алиса да, Карл да бірінші таңдауды алады, ал Боб өзінің үшінші таңдауын алады. Сонымен, ранг-вектор (2,0,1), бұл лексикографиялық жағынан (1,1,1) -дан жоғары - бұл көп адамға олардың бірінші таңдауын береді.

Ешқандай бөлу лексикографиялық тұрғыдан жоғары дәрежелі-векторға әкелмейтінін тексеру оңай. Демек, бөлу (х,з,ж) максималды. Сол сияқты, бөлу (з,х,ж) дәрежелік-максималды болып табылады - ол бірдей ранг-векторды шығарады (2,0,1).

Алгоритмдер

RM сәйкестіктерін алдымен Роберт Ирвинг зерттеді, ол оларды атады ашкөз сәйкестіктер. Ол RM уақытына сәйкес келетін алгоритм ұсынды , қайда n агенттердің саны және c - бұл агенттер тізімінің ең үлкен ұзындығы.[1]

Кейінірек уақытында жұмыс істейтін жетілдірілген алгоритм табылды , қайда м - бұл барлық таңдаулы тізімдердің жалпы ұзындығы (графиктегі жиектердің жалпы саны) және C - RM сәйкестігінде қолданылатын элементтің максималды дәрежесі (яғни оңтайлы ранг векторындағы нөлдік емес элементтердің максималды саны).[2]

Басқа шешім максималды салмақтағы сәйкестіктер, ұқсас жұмыс уақытына жетеді - .[3]

Нұсқалар

Мәселенің бірнеше нұсқалары бар.

1. жылы максималды-кардиналды RM сәйкестігі, мақсаты әр түрлі RM сәйкестіктерінің ішінен ең көп сәйкестік санын табу.

2. жылы әділ сәйкестік, мақсат - шектердің минималды саны болатын максималды кардиналды сәйкестікті табу р ескеріле отырып қолданылады - ранг шеттерінің минималды саны р−1 қолданылады және т.б.

RM максималды-сәйкестігін де, әділ сәйкестігін де салмақтың максималды деңгейіне дейін азайту арқылы табуға болады.[3]

3. жылы сыйымды RM сәйкестігі Мәселе, әр агенттің алатын қабілеттерінің жалпы санының жоғарғы шекарасын көрсететін жоғары қабілеті бар. Әр тармақта бөлуге болатын әртүрлі агенттер санының жоғарғы шегін білдіретін жоғарғы квота бар. Алдымен оны Мельхорн мен Михаил зерттеді, олар жұмыс уақытымен алгоритм берді .[4] Жұмыс уақытымен жақсартылған алгоритм бар , қайда B агенттердің квоталары мен заттар квоталарының қосындысының минимумы болып табылады. Бұл кеңейтуге негізделген Галлай-Эдмондстың ыдырауы көп қырлы сәйкестіктерге дейін.[5]

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Ирвинг, Роберт В. (2003). Ашкөздік сәйкестіктер. Глазго университеті. Tr – 2003–136 бб. CiteSeerX  10.1.1.119.1747.
  2. ^ Ирвинг, Роберт В. Кавитха, Теликепалли; Мехлхорн, Курт; Михаил, Димитриос; Палуч, Катарзына Е. (1 қазан 2006). «Рейтинг-максималды сәйкестіктер». ACM транс. Алгоритмдер. 2 (4): 602–610. дои:10.1145/1198513.1198520. ISSN  1549-6325.
  3. ^ а б Михаил, Димитриос (10 желтоқсан 2007). «Салмақты максималды және максималды сәйкестендіруді азайту». Теориялық информатика. 389 (1): 125–132. дои:10.1016 / j.tcs.2007.08.004. ISSN  0304-3975.
  4. ^ Курт Мехлхорн және Димитриос Михаил (2005). «Полиномдық емес салмақ пен қосымшаның желілік мәселелері».
  5. ^ Палуч, Катарзына (2013 ж. 22 мамыр). Сыйымдылығы бойынша дәрежелік-максималды сәйкестіктер. Алгоритмдер және күрделілік. Информатика пәнінен дәрістер. 7878. Шпрингер, Берлин, Гейдельберг. 324–335 бб. дои:10.1007/978-3-642-38233-8_27. ISBN  978-3-642-38232-1.