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

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

Параметр

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

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

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

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

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

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

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

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

Заявления

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

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

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

Следствия

Консенсусный раздел

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

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

Т.е. среди всех партнеров существует согласие в том, что ценность части j в точности равна $w_{j}$.

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

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

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

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

Часть касающаяся выпуклости, означает, что: теоремы DS,

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

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

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

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

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

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

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

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

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

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

Суперпропорциональное деление

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

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

Т.е. кусок, отведенный партнеру $i$ строго для него более ценно, чем то, что он заслуживает. Следующее утверждение представляет собой теорему Дубинса-Спанье о существовании суперпропорционального деления.

Теорема . С этими обозначениями пусть $w_{1},w_{2},...,w_{n}$ — веса, сумма которых равна 1, предположим, что точка $w:=(w_{1},w_{2},...,w_{n})$ является внутренней точкой (n-1)-мерного симплекса с попарно различными координатами, и предположим, что значение измеряется $V_{1},...,V_{n}$ нормализованы таким образом, что каждый партнер оценивает весь торт ровно как 1 (т. е. они являются неатомарными вероятностными мерами). Если хотя бы две из мер $V_{i},V_{j}$ не равны( $V_{i}\neq V_{j}$), то существуют сверхпропорциональные подразделения.

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

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

Эскиз доказательства

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

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

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

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

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

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

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

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

Утилитарно-оптимальное деление

Перегородка для торта $X$ до n штук (по одной штуке на партнера) называется утилитарно -оптимальной, если она максимизирует сумму значений. То есть, это максимизирует:

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

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

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

сразу следует, что: компактности Из части теоремы DS о

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

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

В этом особом случае неатомарность не требуется: если все меры стоимости счетно-аддитивны, то существует утилитарно-оптимальное разделение.

Оптимальное для чтения деление

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

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

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

${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 о

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

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

Дальнейшие разработки

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

См. также

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