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

 

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

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

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

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

 

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

 

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

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

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

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

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

Пример 1. Пусть имеется трое мужчин и три женщины, т.е. М = { m ₁, m ₂, m ₃}, W = { w ₁, w ₂, w ₃} и предпочтения участников имеют вид:

P (m ₁) = w ₂, w ₁, w ₃; P (w ₁) = m ₁, m ₂, m ₃

P (m ₂) = w ₁, w ₃, w ₂; P (w ₂) = m ₃, m ₁, m ₂;

P (m ₃) = w ₁, w ₂, w ₃; P (w ₃) = m ₃, m ₁, m ₂.

Это означает, что с точки зрения мужчины m ₁ лучшей является женщина w ₂, за ней следует женщина w ₁ и затем – женщина w ₃; с точки зрения женщины w ₁ лучшим является мужчина m ₁, за ним следует мужчина m ₂ и затем – мужчина m ₃, и т.д. Рассмотрим паросочетание

μ =

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

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

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

ν = .

Рассмотрим мужчину m ₁ и женщину w ₂. Поскольку женщине w ₂ предписан лучший, по её мне-нию, мужчина m ₁, то пара (m ₁, w ₂) не является блокирующей данное паросочетание ν. Пара (m ₁, w ₃) не является блокирующей, поскольку мужчине m ₁ предписана женщина w ₁, которая в его предпочтениях стоит перед женщиной w ₃. Пара (m ₃, w ₃) не является блокирующей, поскольку мужчине m ₃ предписана женщина w ₂, которая в его предпочтениях стоит перед женщиной w ₃. Далее, рассмотрим пару (m ₃, w ₁). Она не является блокирующей, поскольку женщине w ₁ пред-писан лучший, по её мнению, мужчина m ₁. Пара (m ₂, w ₁) не является блокирующей по той же причине (женщине w ₁ предписан лучший, по её мнению, мужчина m ₁). Наконец, пара (m ₂, w ₂) не является блокирующей, поскольку женщине w ₂ предписан лучший, по её мнению, мужчина m ₃.

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

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

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

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

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

Пример 3. Построить устойчивое паросочетание при заданных предпочтениях мужчин и женщин. Пусть имеется трое мужчин и четыре женщины, т.е. М = { m ₁, m ₂, m ₃}, W = { w ₁, w ₂, w ₃, w ₄} и предпочтения участников имеют вид:

P (m ₁) = w ₂, w ₁, w ₄, w ₃; P (w ₁) = m ₂, m ₁, m ₃;

P (m ₂) = w ₂, w ₃, w ₄, w ₁; P (w ₂) = m ₃, m ₂, m ₁;

P (m ₃) = w ₁, w ₄, w ₃, w ₂; P (w ₃) = m ₃, m ₁, m ₂;

P (w ₄) = m ₁, m ₃, m ₂.

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

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

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

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

Шаг 1.

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

.

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

.

Запомним, что мужчину m ₁ отвергла женщина w ₂.

Шаг 2.

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

.

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

.

Запомним, что мужчину m ₃ отвергла женщина w ₁.

Шаг 3.

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

.

Поскольку всем мужчинам сопоставлены разные женщины, то искомое паросочетание найдено и алгоритм прекращает работу. В результате мужчина m ₂ получает предпочитаемую им женщину, мужчины m ₁ и m ₃ получают женщин w ₁ и w ₄, вторых по их предпочтениям. Женщи-нам w ₁, w ₂ и w ₄ достаются мужчины m ₁, m ₂ и m ₃, вторые по их предпочтениям. Женщина w ₃ остаётся одна ■

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

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

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

P (m 1) = w 2, w 3, w 1; P (w 1) = m 2, m 1, m 3; P (m 2) = w 2, w 1, w 3; P (w 2) = m 3, m 2, m 1; P (m 3) = w 1, w 3, w 2; P (w 3) = m 3, m 1, m 2.	P (m 1) = w 2, w 3, w 1; P (w 1) = m 2, m 1, m 3; P (m 2) = w 1, w 3, w 2; P (w 2) = m 3, m 2, m 1; P (m 3) = w 2, w 1, w 3; P (w 3) = m 3, m 1, m 2.
P (m 1) = w 2, w 1, w 3; P (w 1) = m 2, m 1, m 3; P (m 2) = w 2, w 3, w 1; P (w 2) = m 3, m 2, m 1; P (m 3) = w 1, w 3, w 2; P (w 3) = m 3, m 1, m 2.	P (m 1) = w 2, w 1, w 3; P (w 1) = m 2, m 1, m 3; P (m 2) = w 1, w 3, w 2; P (w 2) = m 3, m 2, m 1; P (m 3) = w 2, w 3, w 1; P (w 3) = m 3, m 1, m 2.
P (m 1) = w 1, w 3, w 2; P (w 1) = m 2, m 1, m 3; P (m 2) = w 2, w 3, w 1; P (w 2) = m 3, m 2, m 1; P (m 3) = w 2, w 1, w 3; P (w 3) = m 3, m 1, m 2.	P (m 1) = w 1, w 3, w 2; P (w 1) = m 2, m 1, m 3; P (m 2) = w 2, w 1, w 3; P (w 2) = m 3, m 2, m 1; P (m 3) = w 2, w 3, w 1; P (w 3) = m 3, m 1, m 2.
P (m 1) = w 2, w 3, w 1; P (w 1) = m 2, m 3, m 1; P (m 2) = w 2, w 1, w 3; P (w 2) = m 3, m 1, m 2; P (m 3) = w 1, w 3, w 2; P (w 3) = m 3, m 2, m 1.	P (m 1) = w 2, w 3, w 1; P (w 1) = m 2, m 3, m 1; P (m 2) = w 1, w 3, w 2; P (w 2) = m 3, m 1, m 2; P (m 3) = w 2, w 1, w 3; P (w 3) = m 3, m 2, m 1.
P (m 1) = w 2, w 1, w 3; P (w 1) = m 2, m 3, m 1; P (m 2) = w 2, w 3, w 1; P (w 2) = m 3, m 1, m 2; P (m 3) = w 1, w 3, w 2; P (w 3) = m 3, m 2, m 1.	P (m 1) = w 2, w 1, w 3; P (w 1) = m 2, m 3, m 1; P (m 2) = w 1, w 3, w 2; P (w 2) = m 3, m 1, m 2; P (m 3) = w 2, w 3, w 1; P (w 3) = m 3, m 2, m 1.
P (m 1) = w 1, w 3, w 2; P (w 1) = m 2, m 3, m 1; P (m 2) = w 2, w 3, w 1; P (w 2) = m 3, m 1, m 2; P (m 3) = w 2, w 1, w 3; P (w 3) = m 3, m 2, m 1.	P (m 1) = w 1, w 3, w 2; P (w 1) = m 2, m 3, m 1; P (m 2) = w 2, w 1, w 3; P (w 2) = m 3, m 1, m 2; P (m 3) = w 2, w 3, w 1; P (w 3) = m 3, m 2, m 1.
P (m 1) = w 2, w 1, w 3; P (w 1) = m 3, m 2, m 1; P (m 2) = w 2, w 3, w 1; P (w 2) = m 2, m 3, m 1; P (m 3) = w 1, w 3, w 2; P (w 3) = m 2, m 3, m 1.	P (m 1) = w 2, w 1, w 3; P (w 1) = m 3, m 2, m 1; P (m 2) = w 1, w 3, w 2; P (w 2) = m 2, m 3, m 1; P (m 3) = w 2, w 3, w 1; P (w 3) = m 2, m 3, m 1.
P (m 1) = w 1, w 3, w 2; P (w 1) = m 3, m 2, m 1; P (m 2) = w 2, w 3, w 1; P (w 2) = m 2, m 3, m 1; P (m 3) = w 2, w 1, w 3; P (w 3) = m 2, m 3, m 1.	P (m 1) = w 2, w 3, w 1; P (w 1) = m 2, m 1, m 3; P (m 2) = w 2, w 1, w 3; P (w 2) = m 3, m 2, m 1; P (m 3) = w 1, w 3, w 2; P (w 3) = m 3, m 1, m 2.
P (m 1) = w 2, w 3, w 1; P (w 1) = m 2, m 1, m 3; P (m 2) = w 1, w 3, w 2; P (w 2) = m 3, m 2, m 1; P (m 3) = w 2, w 1, w 3; P (w 3) = m 3, m 1, m 2.	P (m 1) = w 2, w 1, w 3; P (w 1) = m 2, m 1, m 3; P (m 2) = w 2, w 3, w 1; P (w 2) = m 3, m 2, m 1; P (m 3) = w 1, w 3, w 2; P (w 3) = m 3, m 1, m 2.
P (m 1) = w 2, w 1, w 3; P (w 1) = m 2, m 1, m 3; P (m 2) = w 1, w 3, w 2; P (w 2) = m 3, m 2, m 1; P (m 3) = w 2, w 3, w 1; P (w 3) = m 3, m 1, m 2.	P (m 1) = w 1, w 3, w 2; P (w 1) = m 2, m 1, m 3; P (m 2) = w 2, w 3, w 1; P (w 2) = m 3, m 2, m 1; P (m 3) = w 2, w 1, w 3; P (w 3) = m 3, m 1, m 2.
P (m 1) = w 1, w 3, w 2; P (w 1) = m 2, m 1, m 3; P (m 2) = w 2, w 1, w 3; P (w 2) = m 3, m 2, m 1; P (m 3) = w 2, w 3, w 1; P (w 3) = m 3, m 1, m 2.	P (m 1) = w 2, w 3, w 1; P (w 1) = m 2, m 3, m 1; P (m 2) = w 2, w 1, w 3; P (w 2) = m 3, m 1, m 2; P (m 3) = w 1, w 3, w 2; P (w 3) = m 3, m 2, m 1.
P (m 1) = w 2, w 3, w 1; P (w 1) = m 2, m 3, m 1; P (m 2) = w 1, w 3, w 2; P (w 2) = m 3, m 1, m 2; P (m 3) = w 2, w 1, w 3; P (w 3) = m 3, m 2, m 1.	P (m 1) = w 2, w 1, w 3; P (w 1) = m 2, m 3, m 1; P (m 2) = w 2, w 3, w 1; P (w 2) = m 3, m 1, m 2; P (m 3) = w 1, w 3, w 2; P (w 3) = m 3, m 2, m 1.
P (m 1) = w 2, w 1, w 3; P (w 1) = m 2, m 3, m 1; P (m 2) = w 1, w 3, w 2; P (w 2) = m 3, m 1, m 2; P (m 3) = w 2, w 3, w 1; P (w 3) = m 3, m 2, m 1.	P (m 1) = w 1, w 3, w 2; P (w 1) = m 2, m 3, m 1; P (m 2) = w 2, w 3, w 1; P (w 2) = m 3, m 1, m 2; P (m 3) = w 2, w 1, w 3; P (w 3) = m 3, m 2, m 1.
P (m 1) = w 1, w 3, w 2; P (w 1) = m 2, m 3, m 1; P (m 2) = w 2, w 1, w 3; P (w 2) = m 3, m 1, m 2; P (m 3) = w 2, w 3, w 1; P (w 3) = m 3, m 2, m 1.	P (m 1) = w 2, w 1, w 3; P (w 1) = m 3, m 2, m 1; P (m 2) = w 2, w 3, w 1; P (w 2) = m 1, m 3, m 2; P (m 3) = w 1, w 3, w 2; P (w 3) = m 2, m 3, m 1.
P (m 1) = w 2, w 1, w 3; P (w 1) = m 3, m 2, m 1; P (m 2) = w 1, w 3, w 2; P (w 2) = m 1, m 3, m 2; P (m 3) = w 2, w 3, w 1; P (w 3) = m 2, m 3, m 1.	P (m 1) = w 1, w 3, w 2; P (w 1) = m 3, m 2, m 1; P (m 2) = w 2, w 3, w 1; P (w 2) = m 1, m 3, m 2; P (m 3) = w 2, w 1, w 3; P (w 3) = m 2, m 3, m 1.
P (m 1) = w 1, w 3, w 2; P (w 1) = m 3, m 2, m 1; P (m 2) = w 2, w 1, w 3; P (w 2) = m 1, m 3, m 2; P (m 3) = w 2, w 3, w 1; P (w 3) = m 2, m 3, m 1.	P (m 1) = w 2, w 3, w 1; P (w 1) = m 2, m 1, m 3; P (m 2) = w 2, w 1, w 3; P (w 2) = m 3, m 2, m 1; P (m 3) = w 1, w 3, w 2; P (w 3) = m 3, m 1, m 2.

■

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

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

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

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

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

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

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

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

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

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

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

= = 100, (1)

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

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

Выигрыши G _A(x) и G _B(x) участников A и B при дележе x = (x ₁, …, x_N) определяются фор-мулами

G _A(x) = , G _B(x) = ). (2)

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

= 100 – G _A(x), (3а)

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

= 100 – G _B(x). (3b)

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

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

G _A(x) ≥ 50 (4a)

и

G _B(x) ≥ 50. (4b)

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

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

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

G _A(x) = G _B(x), (5)

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

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

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

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

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

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

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

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

a ₁ ⁄ b ₁ ≥ a ₂ ⁄ b ₂ ≥... ≥ a_N ⁄ b_N. (6)

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

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

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

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

≥ . (7)

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

3.1. Положим

x_r = ( – ) ⁄ (a_r + b_r). (8)

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

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

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

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

Утверждение 2. Делёж, построенный описанным выше алгоритмом ПП, является спра-ведливым для любых сравнительных важностей a ₁, …, a_N и b ₁, …, b_N. Единственный пункт, который может делиться в построенном платеже – это 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 имеем

= a ₁ = 27, = b ₂ + b ₃ + b ₄ + b ₅ = 12 + 29 + 21 + 28 = 90. Так как 27 < 90, то условие (7) не выполняется.

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

= a ₁ + a ₂ = 27 + 26 = 53, = b ₃ + b ₄ + b ₅ = 29 + 21 + 28 = 78. Так как 53 < 78, то условие (7) не выполняется.

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

= a ₁ + a ₂ + a ₃ = 27 + 26 + 23= 76, = b ₄ + b ₅ = 21 + 28 = 49. Так как 76 ≥ 49, то условие (7) выполняется. Поэтому, в соответствии с операциями на шаге 3, получаем

x_r = ( – ) ⁄ (a_r + b_r) = (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) подсчитать выигрыши участников. Имеем

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

G _B(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 имеем = a ₁ = 90, = b ₂ + b ₃ + b ₄ + b ₅ = 20 + 20 + 20 + 20 = 80. Так как 90 ≥ 80, то условие (7) выполняется. Поэтому, в соответствии с операциями на шаге 3, получаем

x ₁ = ( – ) ⁄ (a_r + b_r) = (100 – 0) ⁄ (90 + 20) = 100 ⁄ 110 = 10 ⁄ 11; x ₂ = x ₃ = x ₄ = x ₅ = 0.

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

G _A(x) = = 2•0+ 3•0+ 2•0+90•(10 ⁄ 11)+3•0 = 81 ;

G _B(x) = ) = 20•1+20•1+20•1+20•(1 ⁄ 11)+20•1 =.81 ,

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

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

 

 

пп A B	пп A B	пп A B	пп A B	пп A B	пп A B	пп A B
пп A B	пп A B	пп A B	пп A B	пп A B	пп A B	пп A B
пп A B	пп A B	пп A B	пп A B	пп A B ⇐ Предыдущая30313233343536373839Следующая ⇒ Поделиться с друзьями: Дата добавления: 2016-10-07; Мы поможем в написании ваших работ!; просмотров: 1367 | Нарушение авторских прав Поиск на сайте: Лучшие изречения: Неосмысленная жизнь не стоит того, чтобы жить. © Сократ ==> читать все изречения... 2311 - | 2016 - © 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.014 с.