Глава 13. Неигровые модели взаимодействия

 

1. Обобщённые паросочетания

2. Справедливый делёж

3. Пропорциональное представительство

4. Предметный указатель

 

В этой главе рассматривается взаимодействие участников, которое хотя обычно и не рас-сматривается в рамках традиционной теории игр, всё же носит в себе черты как конфликта, так и сотрудничества. При таком взаимодействии интересы участников, хотя и не совсем совпада-ют, всё же не являются полностью противоположными, как в матричных играх двух лиц с нуле-вой суммой. Ещё более принципиальное отличие состоит в том, что суть дела в рассматривае-мых здесь случаях состоит не в достижении оптимального результата отдельными игроками, а в определении таких правил взаимодействия участников, которые представляются разумными. Разумность правил означает, что попытка достижения своих целей каждым участником в от-дельности в рамках этих правил приводит к результатам, которые с некоторой общей точки зрения представляются целесообразными и справедливыми. Напомним, что лица или организа-ции, определяющие правила взаимодействия участников и заинтересованные в результатах это-го взаимодействия, иногда называются метаигроками.

 

Обобщённые паросочетания

В главе 6 было введено понятие двудольного графа. Далее, в главе 9, рассматривались свя-занные с такими графами задача о максимальном паросочетании и задача назначения. В этих за-дачах вершины одной доли графа интерпретируются как исполнители, а вершины другой – как задания, которые могут быть выполнены определёнными исполнителями. При поиске паросоче-тания требовалось обеспечить максимальную эффективность соответствующего назначения, т.е. сопоставления работ исполнителям. При этом интересы самих исполнителей не только не принимались во внимание, но даже и не рассматривались.

Однако во многих случаях обеим частям двудольного графа (а не только исполнителям) естественно сопоставляются некоторые интересы. Примером может служить распределение вы-пускников медицинского вуза между больницами, распределение выпускников военной акаде-мии между воинскими частями, и т.д. Другим примером служит распределение рукописей меж-ду рецензентами в научном издательстве. Конечно, рукописи сами по себе не обладают никаки-ми мнениями относительно рецензентов, однако такими мнениями обладают редакторы изда-тельства, которые понимают, какие рецензенты лучше подходят для работы с той или иной ру-кописью.

Общепринято рассматривать ситуации, в которых элементы каждой из двух сторон имеют предпочтения относительно элементов другой стороны, в гендерных терминах. Предполагается, что имеются мужчины и женшины: с точки зрения любого мужчины, все женщины ранжирова-ны от лучшей к худшей, а с точки зрения любой женщины, так же ранжированы все мужчины. Все эти ранжировки могут быть совершенно произвольными.

Задача брачного агенства состоит в поиске разумного паросочетания (об оптимальных в такой деликатной ситуации вряд ли стоит говорить). Для того, чтобы формализовать понятие разумности паросочетания, рассмотрим некоторые примеры. Здесь и далее предполагается, что участники могут свободно обмениваться информацией о своих предпочтениях, а брачное агент-ство, естественно, знает их все.

Пример 1. Пусть имеется трое мужчин и три женщины, т.е. М = {m1, m2, m3}, W = {w1, w2, w3} и предпочтения участников имеют вид:

P(m1) = w2, w1, w3; P(w1) = m1, m2, m3

P(m2) = w1, w3, w2; P(w2) = m3, m1, m2;

P(m3) = w1, w2, w3; P(w3) = m3, m1, m2.

Это означает, что с точки зрения мужчины m1 лучшей является женщина w2, за ней следует женщина w1 и затем – женщина w3; с точки зрения женщины w1 лучшим является мужчина m1, за ним следует мужчина m2 и затем – мужчина m3, и т.д. Рассмотрим паросочетание

μ =

и мужчину m1. Ему паросочетанием μ предписывается жениться на женщине w1, при том, что более предпочтительным для него вариантом является женитьба на w2. В то же время женщина w2 должна, согласно паросочетанию μ, выйти замуж за m2, хотя мужчина m1 для неё более предпочтителен. Но тогда пара (m1, w2)может отказаться принимать условия, предлагаемые па-росочетанием μ, поскольку они оба предпочитают друг друга более, чем предлагаемых им парт-нёров. Если брачное агентство предлагает своим клиентам устроить браки в соответствии с дан-ным паросочетанием μ, то пара (m1,w2) не будем следовать советам этого агенства ■

В случаях, аналогичных рассмотренному в примере 1, говорят, что пара (m,w) блокиру-ет паросочетание μ. Сама такая пара называется блокирующей паросочетание.

Пример 2. При тех же самых предпочтениях, как в примере 1, рассмотрим паросочетание

ν = .

Рассмотрим мужчину m1 и женщину w2. Поскольку женщине w2 предписан лучший, по её мне-нию, мужчина m1, то пара (m1,w2) не является блокирующей данное паросочетание ν. Пара (m1,w3) не является блокирующей, поскольку мужчине m1 предписана женщина w1, которая в его предпочтениях стоит перед женщиной w3. Пара (m3,w3) не является блокирующей, поскольку мужчине m3 предписана женщина w2, которая в его предпочтениях стоит перед женщиной w3. Далее, рассмотрим пару (m3,w1). Она не является блокирующей, поскольку женщине w1 пред-писан лучший, по её мнению, мужчина m1. Пара (m2,w1) не является блокирующей по той же причине (женщине w1 предписан лучший, по её мнению, мужчина m1). Наконец, пара (m2,w2) не является блокирующей, поскольку женщине w2 предписан лучший, по её мнению, мужчина m3.

Таким образом, рассмотрены все 6 пар, которые не предписаны друг другу паросочетанием ν (число таких пар всегда равно 6 при 3-ёх мужчинах и 3-ёх женщинах независимо от паросочета-ния). Ни одна из этих пар не является блокирющей ■

Паросочетание, не содержащее блокирующих пар, называется устойчивым. Пример 2 по-казывает, что при рассматриваемых предпочтениях паросочетание ν является устойчивым. Ус-тойчивость не означает, что все получают лучших – с их точки зрения – партнёров. В паросоче-тании ν каждый мужчина получает 2-ую по своему предпочтению женщину, женщины w1 иw2 получают лучших – с их точки зрения – партнёров, а женщина w3 получает мужчину m2, зани-мающего последнее место в её предпочтениях. И тем не менее пары, которая блокировала бы это паросочетание, нет.

Естественно возникающие вопросы состоят в следующем. Существует ли хотя бы одно устойчивое паросочетание состояние при любых предпочтениях участников? Как его найти, ес-ли оно существует? На 1-ый вопрос положительный ответ даёт

Утверждение 1. При любых предпочтениях участников, задаваемых строгими ранжиров-ками, устойчивые паросочетания существуют ■

Приведём алгоритм построения устойчивого паросочетания. Доказательство утверждения 1 (которое здесь не приводится) как раз и состоит в доказательстве того, что паросочетание, по-строенное данным алгоритмом, действительно устойчиво. Для упрощения изложения алгоритм демонстрируется на конкретном примере.

Пример 3.Построить устойчивое паросочетание при заданных предпочтениях мужчин и женщин. Пусть имеется трое мужчин и четыре женщины, т.е. М = {m1, m2, m3}, W = {w1, w2, w3, w4} и предпочтения участников имеют вид:

P(m1) = w2, w1, w4, w3; P(w1) = m2, m1, m3;

P(m2) = w2, w3, w4, w1; P(w2) = m3, m2, m1;

P(m3) = w1, w4, w3, w2; P(w3) = m3, m1, m2;

P(w4) =m1, m3, m2.

Алгоритм состоит из последовательно выполняемых шагов 1, 2, 3, … . Каждый шаг состо-ит из двух фаз: фазы приписывания (А) и фазы отказа (Б). В фазе приписывания каждому мужчине из тех, у кого на данный момент нет пары, приписывается женщина, следующая в его предпочтении сразу после той, которая отказала ему (отвергла его) на предыдущем шаге. (На шаге 1 в фазе приписывания каждому мужчине просто приписывается первая в его предпочте-нии женщина.)

Если на каком-то шаге после фазы приписывания всем мужчинам приписаны разные жен-щины, то искомое паросочетание найдено и алгоритм прекращает работу. В противном случае переходим к фазе отказа.

В фазе отказа каждая женщина из тех, которым приписано более одного мужчины, остав-ляет того мужчину, который предшествует остальным из приписанных ей. Этот мужчина обра-зует с данной женщиной пару, а остальным она отказывает (отвергает их).

Посмотрим, как работает алгоритм в рассматриваемом случае.

Шаг 1.

Фаза А. Приписываем каждому мужчине предпочитаемую им женщину. Получим

.

Фаза Б. Женщине w2 приписано двое мужчин: m1 и m2. Поскольку в её предпочтении m2 пред-шествует m1, то она отвергает m1. Получаем «неполное» паросочетание

.

Запомним, что мужчину m1 отвергла женщина w2.

Шаг 2.

Фаза А. В данный момент у мужчины m1 нет пары. В соответствии с алгоритмом приписываем ему женщину, следующую в его списке сразу после отвергшей его женщиной w2. Таковой явля-ется женщина w1. В результате приписывания получаем

.

Фаза Б. Женщине w1 приписано двое мужчин: m1 и m3. Поскольку в её предпочтении m1 пред-шествует m3, то она отвергает m3. Получаем «неполное» паросочетание

.

Запомним, что мужчину m3 отвергла женщина w1.

Шаг 3.

Фаза А. В данный момент у мужчины m3 нет пары. В соответствии с алгоритмом приписываем ему женщину, следующую в его списке сразу после отвергшей его женщиной w1. Таковой явля-ется женщина w4. В результате приписывания получаем

.

Поскольку всем мужчинам сопоставлены разные женщины, то искомое паросочетание найдено и алгоритм прекращает работу. В результате мужчина m2 получает предпочитаемую им женщину, мужчины m1 и m3 получают женщин w1 и w4, вторых по их предпочтениям. Женщи-нам w1, w2 и w4 достаются мужчины m1, m2 и m3, вторые по их предпочтениям. Женщина w3 остаётся одна ■

В рассмотренном примере на 1-ом шаге в фазе приписывания женщины приписывались мужчинам. Можно использовать тот же алгоритм, в котором женщины заменены на мужчин, а мужчины на женщин, т.е. на 1-ом шаге мужчины приписываются женщинам, далее на фазе от-каза из нескольких женщин, приписанных одному мужчине, остаётся та, которая предпочти-тельней остальных, и т.д. Возможно построить несколько устойчивых паросочетаний, некото-рые из которых могут быть в каких-то отношениях лучше, чем данное. Однако используемый алгоритм гарантирует устойчивость полученного паросочетания (отсутствие блокирующих пар) при любых исходных данных.

Можно сказать, что брачное агентство является в данном случае метаигроком, который определяет правила взаимодействия участников: они указывают свои предпочтения (в виде строгих ранжировок), а участникам предлагается достаточно разумное устойчивое паросочета-ние, которое строится на основе полученной от участников информации об их предпочтениях. В большинстве случаев такие разумные (в данном случае – устойчивые) паросочетания опреде-ляются неоднозначно, однако вопрос о том, как их оценивать и как выбирать в том или ином смысле «лучшие» или «оптимальные» паросочетания, здесь не рассматривается.

Задание 1. Построить, пользуясь рассмотренным выше алгоритмом, устойчивые паросо-четания при следующих предпочтениях участников:

P(m1) = w2, w3, w1; P(w1) = m2, m1, m3; P(m2) = w2, w1, w3; P(w2) = m3, m2, m1; P(m3) = w1, w3, w2; P(w3) = m3, m1, m2. P(m1) = w2, w3, w1; P(w1) = m2, m1, m3; P(m2) = w1, w3, w2; P(w2) = m3, m2, m1; P(m3) = w2, w1, w3; P(w3) = m3, m1, m2.
P(m1) = w2, w1, w3; P(w1) = m2, m1, m3; P(m2) = w2, w3, w1; P(w2) = m3, m2, m1; P(m3) = w1, w3, w2; P(w3) = m3, m1, m2. P(m1) = w2, w1, w3; P(w1) = m2, m1, m3; P(m2) = w1, w3, w2; P(w2) = m3, m2, m1; P(m3) = w2, w3, w1; P(w3) = m3, m1, m2.
P(m1) = w1, w3, w2; P(w1) = m2, m1, m3; P(m2) = w2, w3, w1; P(w2) = m3, m2, m1; P(m3) = w2, w1, w3; P(w3) = m3, m1, m2. P(m1) = w1, w3, w2; P(w1) = m2, m1, m3; P(m2) = w2, w1, w3; P(w2) = m3, m2, m1; P(m3) = w2, w3, w1; P(w3) = m3, m1, m2.
P(m1) = w2, w3, w1; P(w1) = m2, m3, m1; P(m2) = w2, w1, w3; P(w2) = m3, m1, m2; P(m3) = w1, w3, w2; P(w3) = m3, m2, m1. P(m1) = w2, w3, w1; P(w1) = m2, m3, m1; P(m2) = w1, w3, w2; P(w2) = m3, m1, m2; P(m3) = w2, w1, w3; P(w3) = m3, m2, m1.
P(m1) = w2, w1, w3; P(w1) = m2, m3, m1; P(m2) = w2, w3, w1; P(w2) = m3, m1, m2; P(m3) = w1, w3, w2; P(w3) = m3, m2, m1. P(m1) = w2, w1, w3; P(w1) = m2, m3, m1; P(m2) = w1, w3, w2; P(w2) = m3, m1, m2; P(m3) = w2, w3, w1; P(w3) = m3, m2, m1.
P(m1) = w1, w3, w2; P(w1) = m2, m3, m1; P(m2) = w2, w3, w1; P(w2) = m3, m1, m2; P(m3) = w2, w1, w3; P(w3) = m3, m2, m1. P(m1) = w1, w3, w2; P(w1) = m2, m3, m1; P(m2) = w2, w1, w3; P(w2) = m3, m1, m2; P(m3) = w2, w3, w1; P(w3) = m3, m2, m1.
P(m1) = w2, w1, w3; P(w1) = m3, m2, m1; P(m2) = w2, w3, w1; P(w2) = m2, m3, m1; P(m3) = w1, w3, w2; P(w3) = m2, m3, m1. P(m1) = w2, w1, w3; P(w1) = m3, m2, m1; P(m2) = w1, w3, w2; P(w2) = m2, m3, m1; P(m3) = w2, w3, w1; P(w3) = m2, m3, m1.
P(m1) = w1, w3, w2; P(w1) = m3, m2, m1; P(m2) = w2, w3, w1; P(w2) = m2, m3, m1; P(m3) = w2, w1, w3; P(w3) = m2, m3, m1. P(m1) = w2, w3, w1; P(w1) = m2, m1, m3; P(m2) = w2, w1, w3; P(w2) = m3, m2, m1; P(m3) = w1, w3, w2; P(w3) = m3, m1, m2.
P(m1) = w2, w3, w1; P(w1) = m2, m1, m3; P(m2) = w1, w3, w2; P(w2) = m3, m2, m1; P(m3) = w2, w1, w3; P(w3) = m3, m1, m2. P(m1) = w2, w1, w3; P(w1) = m2, m1, m3; P(m2) = w2, w3, w1; P(w2) = m3, m2, m1; P(m3) = w1, w3, w2; P(w3) = m3, m1, m2.
P(m1) = w2, w1, w3; P(w1) = m2, m1, m3; P(m2) = w1, w3, w2; P(w2) = m3, m2, m1; P(m3) = w2, w3, w1; P(w3) = m3, m1, m2. P(m1) = w1, w3, w2; P(w1) = m2, m1, m3; P(m2) = w2, w3, w1; P(w2) = m3, m2, m1; P(m3) = w2, w1, w3; P(w3) = m3, m1, m2.
P(m1) = w1, w3, w2; P(w1) = m2, m1, m3; P(m2) = w2, w1, w3; P(w2) = m3, m2, m1; P(m3) = w2, w3, w1; P(w3) = m3, m1, m2. P(m1) = w2, w3, w1; P(w1) = m2, m3, m1; P(m2) = w2, w1, w3; P(w2) = m3, m1, m2; P(m3) = w1, w3, w2; P(w3) = m3, m2, m1.
P(m1) = w2, w3, w1; P(w1) = m2, m3, m1; P(m2) = w1, w3, w2; P(w2) = m3, m1, m2; P(m3) = w2, w1, w3; P(w3) = m3, m2, m1. P(m1) = w2, w1, w3; P(w1) = m2, m3, m1; P(m2) = w2, w3, w1; P(w2) = m3, m1, m2; P(m3) = w1, w3, w2; P(w3) = m3, m2, m1.
P(m1) = w2, w1, w3; P(w1) = m2, m3, m1; P(m2) = w1, w3, w2; P(w2) = m3, m1, m2; P(m3) = w2, w3, w1; P(w3) = m3, m2, m1. P(m1) = w1, w3, w2; P(w1) = m2, m3, m1; P(m2) = w2, w3, w1; P(w2) = m3, m1, m2; P(m3) = w2, w1, w3; P(w3) = m3, m2, m1.
P(m1) = w1, w3, w2; P(w1) = m2, m3, m1; P(m2) = w2, w1, w3; P(w2) = m3, m1, m2; P(m3) = w2, w3, w1; P(w3) = m3, m2, m1. P(m1) = w2, w1, w3; P(w1) = m3, m2, m1; P(m2) = w2, w3, w1; P(w2) = m1, m3, m2; P(m3) = w1, w3, w2; P(w3) = m2, m3, m1.
P(m1) = w2, w1, w3; P(w1) = m3, m2, m1; P(m2) = w1, w3, w2; P(w2) = m1, m3, m2; P(m3) = w2, w3, w1; P(w3) = m2, m3, m1. P(m1) = w1, w3, w2; P(w1) = m3, m2, m1; P(m2) = w2, w3, w1; P(w2) = m1, m3, m2; P(m3) = w2, w1, w3; P(w3) = m2, m3, m1.
P(m1) = w1, w3, w2; P(w1) = m3, m2, m1; P(m2) = w2, w1, w3; P(w2) = m1, m3, m2; P(m3) = w2, w3, w1; P(w3) = m2, m3, m1. P(m1) = w2, w3, w1; P(w1) = m2, m1, m3; P(m2) = w2, w1, w3; P(w2) = m3, m2, m1; P(m3) = w1, w3, w2; P(w3) = m3, m1, m2.

Справедливый делёж

В середине 1990-х годов американскими учёными Брамсом и Тэйлором была предложена новая модель разрешения конфликтов (см. литературу в конце данной части). В этой модели конфликт состоит в разногласиях сразу по нескольким вопросам (пунктам), причём важность этих пунктов для различных участников, вообще говоря, различна. Именно эти различия позво-ляют предложить такой вариант улаживания конфликта, при котором каждый получает то, что его больше устраивает по его собственной оценке. Возвращаясь к цитате, с которой начинается данная часть, можно сказать, что модель справедливого дележа Брамса-Тэйлора, коротко опи-санная в данном разделе (и подробно в литературе, упомянутой в конце части), является фор-мальной моделью, выражающей этот очень разумный подход, призывающий к сотрудничеству даже при заметно отличающихся взглядах и целях

Пример 4. Раздел наследства. Рассмотрим реальный случай супружеской пары, которая имела собственный дом и коттеджи в штате Мэн. Когда муж умер, жена продала дом и коттед-жи и переехала во Флориду. Оставалось несколько предметов, не имевших ценности для неё, но интересовавших двух её сыновей, Брэда и Дика, которые также жили в штате Мен. Эти предме-ты перечислены в левой части приводимой ниже таблицы:

  Брэд (%) Дик (%)
Двенадцатифутовая алюминиевая гребная лодка
Лодочный мотор в 3 лошадиных силы
Пианино в хорошем состоянии
Небольшой персональный компьютер
Охотничье ружье
Набор инструментов
Трактор фирмы «Форд» 1953 года выпуска с прицепным плугом
Сравнительно старенький крытый грузовичок («пикап»)
Мопед
Мопед
ВСЕГО

Ради иллюстрации, предположим, что мы можем заглянуть в мысли сыновей и точно узнать, ка-кую долю от общей ценности представляет для них каждый предмет. За основу примем то, что Брэд получил бизнес-образование и интересуется музыкой, а Дик - спортсмен и живет в сель-ской местности. Таким образом, пианино и компьютер больше привлекают Брэда, чем Дика. С другой стороны, Дика больше привлекают лодка, мотор, трактор и грузовичок. Эти рассужде-ния позволяют предположить оценки (выраженные в виде процента от общей ценности) различ-ных предметов Брэдом и Диком, приведённые в правой части той же таблицы.

Можно рассмотреть, например такой вариант дележа (вместе с предметом указана и его оценка тем из братьев, которому достаётся данный предмет):

Набор Брэда: пианино (17%), компьютер (17%), ружье (4%), инструменты (6%), мопед

(17%) – в сумме 61%.

Набор Дика: лодка (14%), лодочный мотор (14%), трактор (21%), пикап (14%), мопед (14%) – в сумме 77%.

Не обсуждая пока, хорош или плох предложенный делёж и как его улучшить, заметим са-мое главное: каждый из братьев получает больше половины возможных баллов (100) по своей собственной оценке. Именно идея опоры на собственные оценки каждого участника и лежит в основе предложенного Брамсом и Тэйлором подхода к разрешению конфликтов ■

2.1. Формальные понятия и определения. Дадим формальное описание рассматривае-мой модели в общем виде. Предполагается, что всего имеется N пунктов (материальных благ, спорных вопросов, видов работ и пр.), совокупность разногласий по которым и составляет рас-сматриваемый конфликт между двумя участниками A и B. Натуральные (т.е. целые положи-тельные) числа a1, …, aN и b1, …, bN представляют собой сравнительную важность пунктов, составляющих конфликт, для участников A и B. Без ограничения общности можно считать, что

= = 100, (1)

интерпретируя эти числа как проценты важности соответствующих пунктов.

Делёж формально представляет собой вектор x = (x1, …, xN), где xi – вещественные числа, такие что 0 ≤ xi ≤ 1 (i = 1, …, N). Содержательно xi представляет собой долюi-го пункта, получа-емую при дележе xучастником A (при этом участник B получает долю (1–xj) того же пункта). Если i-й пункт представляет собой материальное благо (типа денег, участка земли и пр.), то по-нятие доли достаточно ясно. В других случаях оно требует дополнительного соглашения между участниками. Например, при разводе супругов, каждый из которых желает как можно больше общаться с их единственным ребёнком, таким конфликтным пунктом является время, а доля xi есть просто доля времени, которое ребёнок проводит с родителем A. В США в таких случаях достаточно часто ребёнок проводит учебное время с одним из родителей, а каникулы и празд-ники – с другим, и при этом доли определяются, как 0,75 и 0,25. В любом случае доли xi и 1–xj интерпретируются, как степени удовлетворённости участников договорённостью по i-му пунк-ту.

Выигрыши GA(x) и GB(x) участников A и B при дележе x = (x1, …, xN) определяются фор-мулами

GA(x) = , GB(x) = ). (2)

Независимо от «содержания» конфликтных пунктов эти числа всегда лежат между 0 и 100 и по сути дела представляют собой выраженные в 100-балльной шкале степени удовлетворённости участников данным дележом x «в целом». В частности, если всё достаётся участнику A, то GA(x) = 100, GB(x) = 0, а если участнику B, то GA(x) = 0, GB(x) = 100. Вряд ли участник с нуле-вым выигрышем будет считать такой делёж справедливым, да и вообще он вряд ли на него со-гласится добровольно. Из формул (2) и (1) непосредственно следует, что выигрыш участника Bс точки зрения участникаA (т.е. по оценкам A)

= 100 – GA(x), (3а)

а выигрыш участника Aс точки зрения участникаB (т.е. по оценкам B)

= 100 – GB(x). (3b)

Брамс и Тэйлор определили несколько важных свойств дележей, основываясь на выигры-шах GA(x) и GB(x) участников A и B. Положим G(x) = (GA(x), GB(x)) и назовём вектор G(x) (име-ющий две компоненты) общим выигрышем от дележа x.

Делёж x называется свободным от зависти, если

GA(x) ≥ 50 (4a)

и

GB(x) ≥ 50. (4b)

Из формул (4a) и (3a) сразу получаем, что с точки зрения участникаA выигрыш участника B не

превосходит его выигрыша, т.е. он не завидует тому, что получил участник B при дележе x; по той же причине участник B не завидует участнику A, а сам делёж и назван свободным от завис-ти.

Делёж x называется равноценным, если

GA(x) = GB(x), (5)

т.е. оба участника в равной степени удовлетворены дележом x.

Делёж x называется эффективным по Парето (или Парето-эффективным), если общий

выигрыш G(x) недоминируем по Парето на множестве всех возможных общих выигрышей. Формально это означает, что для любого другого дележа yиз GA(x) >GA(y) следует, что GB(x) <GB(y), а из GB(x) >GB(y) следует, что GA(x) <GA(y). Другими словами, результаты дележа xнельзя улучшить для одного участника, не ухудшив для другого, при любом другом дележе y.

2.2. Метод подстраивающегося победителя (ПП). Делёж x называется справедливым, если он является одновременно свободным от зависти, равноценным и Парето-эффективным.Основные естественные вопросы, возникающие при исследовании справедливых дележей, яв-ляются такими же, как и при исследовании других формально определённых математических объектов: существуют ли справедливые дележи? если да, то как их находить? какими ещё инте-ресными свойствами (кроме указанных в определениях) они обладают? если они существуют не всегда, то при каких условиях? как их можно модифицировать, чтобы гарантировать существо-вание дележей при новых условиях? и т.д.

В данном случае Брамсом и Тэйлором в рамках сформулированных выше допущений да-ны исчерпывающие ответы на эти вопросы, Кратко сформулируем эти ответы. Справедливый делёж существует для любых сравнительных важностей a1, …, aN и b1, …, bN. Он легко находится предложенным авторами методом «подстраивающегося победителя» (ПП). Важным свойством найденного методом ПП справедливого дележа является следующее: все пункты (кроме, быть может, одного, определяемого в процессе работы метода ПП) достаются целиком одному или другому участнику, и только один пункт действительно может делиться между ними.

Приведём описание алгоритма ПП. Для упрощения изложения примем соглашение о том,

что сумма = 0, если q<p (не может быть отрицательного числа слагаемых).

Предварительный шаг.Пункты, образующие конфликт, упорядочиваются так, чтобы выпол-нялось условие

a1b1a2b2 ≥ ... ≥ aNbN. (6)

Основныешаги

1. Положим r = 0.

2. Положим r = r +1.

3. Проверяем условие

. (7)

Если (7) выполняется, то сделаем следующее.

3.1. Положим

xr = ( ) ⁄ (ar+br). (8)

3.2. Положим xi= 1 (i = 1, …, r–1), xi= 0 (i = r+1, …, N).

3.3. Стоп. Алгоритм прекращает работу.

В противном случае переходим на шаг 2.

В силу равенства (1) легко понять, что условие (7) обязательно будет выполнено при ка-ком-либо r. Нетрудно проверить, что xr, определяемое формулой (8), лежит между 0 и 1. Более сложным является центральное в данном разделе

Утверждение 2. Делёж, построенный описанным выше алгоритмом ПП, является спра-ведливым для любых сравнительных важностей a1, …, aN и b1, …, bN. Единственный пункт, который может делиться в построенном платеже – это r-ый пункт, где r– минимальный индекс, удовлетворяющий условию (7) ■

Пример 5. Рассмотрим задачу дележа, данные которой представлены в таблице 1. После

Таблица 1
пп A B ai / bi
2,17
0,39
2,70
0,62
0,79

 

Таблица 2
пп A B ai / bi
1(3) 2,70
2(1) 2,17
3(5) 0,79
4(4) 0,62
5(2) 0,39

 

перенумерации пунктов в соответствии с формулой (6) получим задачу, представленную в таб-лице 2 (в 1-м столбце в скобках указаны исходные номера пунктов).

Далее последовательно проверяем, начиная с r = 1, условия (7), используя нумерацию пунктов из таблицы 2. При r = 1 имеем

= a1 = 27, = b2 + b3 + b4 + b5 = 12 + 29 + 21 + 28 = 90. Так как 27 < 90, то условие (7) не выполняется.

Далее, при r = 2,

= a1 + a2 = 27 + 26 = 53, = b3 + b4 + b5 = 29 + 21 + 28 = 78. Так как 53 < 78, то условие (7) не выполняется.

Далее, приr = 3,

= a1 + a2 + a3 = 27 + 26 + 23= 76, = b4 + b5 = 21 + 28 = 49. Так как 76 ≥ 49, то условие (7) выполняется. Поэтому, в соответствии с операциями на шаге 3, получаем

xr = ( ) ⁄ (ar+br) = (78 – 53) ⁄ (23 + 29) = 25 ⁄ 52 = 0,48.

Таким образом, построенный делёж таков: x = (1; 1; 0,48; 0; 0). Это означает, что 1-ый и 2-ой пункты целиком достаются участнику A, 4-ый и 5-ый пункты – участнику B; 3-ий пункт делится между ними в пропорции 0,48:0,52. Переходя к исходной нумерации пунктов, приве-дённой в левом столбце таблицы 2, окончательно получаем следующее. Участник A целиком получает 1-ый и 3-ий пункты, участник B – 2-ой и 4-ый пункты, а 5-ый пункт делится между участниками в той же пропорции 0,48:0,52. Поэтому окончательный делёж принимает вид: x = (1; 0; 1; 0; 0,48).

Зная делёж x, можно по формулам (2) подсчитать выигрыши участников. Имеем

GA(x) = = 26•1+11•0+27•1+13•0+23•0,48 ≈ 64,06;

GB(x) = ) = 12•0+28•1+10•0+21•1+29•0,52 ≈ 64,06.

Примерное равенство выигрышей здесь не случайное совпадение, а следствие утверждения 2. Если считать не в десятичных, а в простых дробях, получится точное равенство. Поскольку по-строенный делёж является справедливым, то оба участника получают одинаковую сумму бал-лов просто по определению справедливого дележа. Из формулы (5) ясно также, что построен-ный делёж свободен от зависти. В силу того же утверждения 2 делёж x Парето-эффективен ■

Пример 6. Рассмотрим задачу дележа, данные которой представлены в таблице 3. После

Таблица 3
пп A B ai / bi
2,17
0,39
2,70
0,62
0,79

 

Таблица 4
пп A B ai / bi
1(4) 4,50
2(2) 0,15
3(5) 0,15
4(1) 0,10
5(3) 0,10

 

перенумерации пунктов в соответствии с формулой (6) получим задачу, представленную в таб-лице 4 (в 1-м столбце в скобках указаны исходные номера пунктов). Далее последовательно проверяем, начиная с r = 1, условия (7), используя нумерацию пунктов из таблицы 4. При r = 1 имеем = a1 = 90, = b2 + b3 + b4 + b5 = 20 + 20 + 20 + 20 = 80. Так как 90 ≥ 80, то условие (7) выполняется. Поэтому, в соответствии с операциями на шаге 3, получаем

x1 = ( )(ar+br) = (100 – 0) ⁄ (90 + 20) = 100 ⁄ 110 = 10 11; x2 = x3 = x4 = x5 = 0.

Возвращаясь к исходной нумерации пунктов, приведённой в левом столбце таблицы 4, окончательно получаем следующее. Участник A получает только 10 11 4-го пункта, участник B – 1 11 4-го пункта и все остальные пункты целиком. Поэтому окончательный делёж прини-мает вид: x = (0; 0; 0; 0,91; 0). Зная делёж x, можно по формулам (2) подсчитать выигрыши учас-тников. Имеем

GA(x) = = 2•0+ 3•0+ 2•0+90•(10 11)+3•0 = 81 ;

GB(x) = ) = 20•1+20•1+20•1+20•(1 11)+20•1 =.81 ,

Как и в примере 5, легко проверить, что данный делёж является справедливым. Заметим, что выигрыш обоих участников значителен. Это происходит из-за большого различия в оценках ■

Задание 2. Найти справедливые дележи и соответствующие им выигрыши алгоритмом ПП. В качестве образца использовать примеры 5 и 6.

 

 



6912.php">39
  • 40
  • 41
  • 42
  • 43
  • Далее ⇒