Теоремы Дубинса–Спаньера

Теоремы Дубинса–Спаньера — это несколько теорем в теории справедливого разрезания торта . Они были опубликованы Лестером Дубинсом и Эдвином Спаниером в 1961 году. ^[1] Хотя изначальной мотивацией этих теорем было справедливое деление, на самом деле они являются общими теоремами в теории меры .

Существует множество , и множество , которое является сигма-алгеброй подмножеств .${\displaystyle U}$${\displaystyle \mathbb {U} }$${\displaystyle U}$

Есть партнеры. У каждого партнера есть личная мера ценности . Эта функция определяет, сколько каждая подгруппа стоит для этого партнера.${\displaystyle n}$${\displaystyle я}$${\displaystyle V_{i}:\mathbb {U} \to \mathbb {R} }$${\displaystyle U}$

Пусть разбиение на измеримые множества: . Определим матрицу как следующую матрицу:${\displaystyle X}$${\displaystyle U}$${\displaystyle к}$${\displaystyle U=X_{1}\sqcup \cdots \sqcup X_{k}}$${\displaystyle M_{X}}$${\displaystyle n\times k}$

${\displaystyle M_{X}[i,j]=V_{i}(X_{j})}$

Эта матрица содержит оценки всех игроков по всем частям разбиения.

Пусть будет совокупностью всех таких матриц (для одинаковых мер значений, одинаковых и разных разбиений):${\displaystyle \mathbb {M} }$${\displaystyle k}$

${\displaystyle \mathbb {M} =\{M_{X}\mid X{\text{ is a }}k{\text{-partition of }}U\}}$

Теоремы Дубинса–Спениера касаются топологических свойств .${\displaystyle \mathbb {M} }$

Если все меры стоимости являются счетно-аддитивными и неатомарными , то:${\displaystyle V_{i}}$

• ${\displaystyle \mathbb {M} }$представляет собой компактный набор ;
• ${\displaystyle \mathbb {M} }$является выпуклым множеством .

Это уже доказали Дворецкий, Вальд и Вулфовиц. ^[2]

Разбиение торта на k частей называется консенсусным разбиением с весами (также называется точным делением ), если:${\displaystyle X}$${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$

${\displaystyle \forall i\in \{1,\dots ,n\}:\forall j\in \{1,\dots ,k\}:V_{i}(X_{j})=w_{j}}$

Т.е., все партнеры пришли к единому мнению, что стоимость детали j составляет ровно .${\displaystyle w_{j}}$

Предположим, что — веса, сумма которых равна 1:${\displaystyle w_{1},w_{2},\ldots ,w_{k}}$

${\displaystyle \sum _{j=1}^{k}w_{j}=1}$

и меры ценности нормализуются таким образом, что каждый партнер оценивает весь торт ровно в 1:

${\displaystyle \forall i\in \{1,\dots ,n\}:V_{i}(U)=1}$

Выпуклая часть теоремы DS подразумевает, что: ^{[1] : 5}

Если все меры стоимости являются счетно-аддитивными и неатомарными,

тогда существует консенсусное разделение.

ДОКАЗАТЕЛЬСТВО: Для каждого определите раздел следующим образом:${\displaystyle j\in \{1,\dots ,k\}}$${\displaystyle X^{j}}$

${\displaystyle X_{j}^{j}=U}$

${\displaystyle \forall r\neq j:X_{r}^{j}=\emptyset }$

В разбиении все партнеры оценивают -ю часть как 1, а все остальные части как 0. Следовательно, в матрице в -м столбце стоят единицы, а во всех остальных столбцах — нули.${\displaystyle X^{j}}$${\displaystyle j}$${\displaystyle M_{X^{j}}}$${\displaystyle j}$

По выпуклости существует разбиение такое, что:${\displaystyle X}$

${\displaystyle M_{X}=\sum _{j=1}^{k}w_{j}\cdot M_{X^{j}}}$

В этой матрице -й столбец содержит только значение . Это означает, что в разделе все партнеры оценивают -й кусок как ровно .${\displaystyle j}$${\displaystyle w_{j}}$${\displaystyle X}$${\displaystyle j}$${\displaystyle w_{j}}$

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

Раздел торта на n частей (по одной части на партнера) называется сверхпропорциональным разделом с весами , если:${\displaystyle X}$${\displaystyle w_{1},w_{2},...,w_{n}}$

${\displaystyle \forall i\in 1\dots n:V_{i}(X_{i})>w_{i}}$

То есть, кусок, отведенный партнеру , строго более ценен для него, чем тот, которого он заслуживает. Следующее утверждение — теорема Дубинса-Спаньера о существовании сверхпропорционального дележа ^{: 6}${\displaystyle i}$

Гипотеза о том, что меры стоимости не идентичны, является необходимой. В противном случае сумма приводит к противоречию.${\displaystyle V_{1},...,V_{n}}$${\displaystyle \sum _{i=1}^{n}V_{i}(X_{i})=\sum _{i=1}^{n}V_{1}(X_{i})>\sum _{i=1}^{n}w_{i}=1}$

А именно, если все меры стоимости являются счетно-аддитивными и неатомарными, и если есть два партнера, такие что , то существует сверхпропорциональный дележ. То есть необходимое условие является также и достаточным.${\displaystyle i,j}$${\displaystyle V_{i}\neq V_{j}}$

Предположим, что wlog, что . Тогда есть некоторый кусок пирога, , такой, что . Пусть будет дополнением к ; тогда . Это означает, что . Однако, . Следовательно, либо , либо . Предположим, что wlog, что и истинны.${\displaystyle V_{1}\neq V_{2}}$${\displaystyle Z\subseteq U}$${\displaystyle V_{1}(Z)>V_{2}(Z)}$${\displaystyle {\overline {Z}}}$${\displaystyle Z}$${\displaystyle V_{2}({\overline {Z}})>V_{1}({\overline {Z}})}$${\displaystyle V_{1}(Z)+V_{2}({\overline {Z}})>1}$${\displaystyle w_{1}+w_{2}\leq 1}$${\displaystyle V_{1}(Z)>w_{1}}$${\displaystyle V_{2}({\overline {Z}})>w_{2}}$${\displaystyle V_{1}(Z)>V_{2}(Z)}$${\displaystyle V_{1}(Z)>w_{1}}$

Определите следующие разделы:

• ${\displaystyle X^{1}}$: раздел, который дает партнеру 1, партнеру 2 и ничего всем остальным.${\displaystyle Z}$${\displaystyle {\overline {Z}}}$
• ${\displaystyle X^{i}}$(для ): раздел, который отдает весь торт партнеру и ничего всем остальным.${\displaystyle i\geq 2}$${\displaystyle i}$

Здесь нас интересуют только диагонали матриц , которые представляют оценки партнеров по отношению к их собственным частям:${\displaystyle M_{X^{j}}}$

• В запись 1 — это , запись 2 — это , а остальные записи — 0.${\displaystyle {\textrm {diag}}(M_{X^{1}})}$${\displaystyle V_{1}(Z)}$${\displaystyle V_{2}({\overline {Z}})}$
• В (для ) запись равна 1, а остальные целые равны 0.${\displaystyle {\textrm {diag}}(M_{X^{i}})}$${\displaystyle i\geq 2}$${\displaystyle i}$

В силу выпуклости для каждого набора весов существует разбиение такое, что:${\displaystyle z_{1},z_{2},...,z_{n}}$${\displaystyle X}$

${\displaystyle M_{X}=\sum _{j=1}^{n}{z_{j}\cdot M_{X^{j}}}.}$

Можно выбрать веса так, чтобы в диагонали элементы находились в тех же соотношениях, что и веса . Поскольку мы предположили, что , можно доказать, что , поэтому является сверхпропорциональным делением.${\displaystyle z_{i}}$${\displaystyle M_{X}}$${\displaystyle w_{i}}$${\displaystyle V_{1}(Z)>w_{1}}$${\displaystyle \forall i\in 1\dots n:V_{i}(X_{i})>w_{i}}$${\displaystyle X}$

Раздел торта на n частей (по одной части на партнера) называется утилитарно -оптимальным, если он максимизирует сумму ценностей. То есть, он максимизирует:${\displaystyle X}$

${\displaystyle \sum _{i=1}^{n}{V_{i}(X_{i})}}$

Утилитарно-оптимальные дележи существуют не всегда. Например, предположим, что есть множество положительных целых чисел. Есть два партнера. Оба оценивают весь набор как 1. Партнер 1 присваивает положительное значение каждому целому числу, а партнер 2 присваивает нулевое значение каждому конечному подмножеству. С утилитарной точки зрения лучше всего дать партнеру 1 большое конечное подмножество и отдать остаток партнеру 2. Когда множество, данное партнеру 1, становится все больше и больше, сумма значений становится все ближе и ближе к 2, но она никогда не приближается к 2. Таким образом, утилитарно-оптимального дележа не существует.${\displaystyle U}$${\displaystyle U}$

Проблема с приведенным выше примером заключается в том, что мера ценности партнера 2 является конечно-аддитивной, но не счетно-аддитивной .

Из компактной части теоремы DS немедленно следует, что: ^{[1] : 7}

Если все меры стоимости являются счетно-аддитивными и неатомарными,

тогда существует утилитарно-оптимальное разделение.

В этом особом случае неатомарность не требуется: если все меры стоимости являются счетно-аддитивными, то существует утилитарно-оптимальное разбиение. ^{[1] : 7}

Разделение торта на n частей (по одной части на партнера) называется лексимин -оптимальным с весами , если оно максимизирует лексикографически упорядоченный вектор относительных значений. То есть, оно максимизирует следующий вектор:${\displaystyle X}$${\displaystyle w_{1},w_{2},...,w_{n}}$

${\displaystyle {V_{1}(X_{1}) \over w_{1}},{V_{2}(X_{2}) \over w_{2}},\dots ,{V_{n}(X_{n}) \over w_{n}}}$

где партнеры индексируются таким образом, что:

${\displaystyle {V_{1}(X_{1}) \over w_{1}}\leq {V_{2}(X_{2}) \over w_{2}}\leq \dots \leq {V_{n}(X_{n}) \over w_{n}}}$

Оптимальное по лексимину разбиение максимизирует ценность самого бедного партнера (относительно его веса); при этом оно максимизирует ценность следующего самого бедного партнера (относительно его веса) и т. д.

Из компактной части теоремы DS немедленно следует, что: ^{[1] : 8}

Если все меры стоимости являются счетно-аддитивными и неатомарными,

то существует лексимин-оптимальное деление.

• Критерий лексиминной оптимальности, введенный Дубинсом и Спаниером, был впоследствии подробно изучен. В частности, в задаче разрезания торта его изучал Марко Далл'Альо. ^[3]

• Теорема Ляпунова о векторной мере ^[4]
• Теорема Веллера