Dubins-Speniers satser

Dubins-Spanier- satserna är flera satser i teorin om rättvis kakskärning . De publicerades av Lester Dubins och Edwin Spanier 1961 [1] . Även om det ursprungliga syftet med dessa satser var problemet med rättvis division , är de i själva verket generella måttteorem .

Villkor

Det finns en uppsättning och en uppsättning , som är en sigma-algebra av delmängder av uppsättningen . $U$ $\mathbb {U}$ $U$

Det finns deltagare. Varje deltagare har ett personligt preferensmått . Denna funktion avgör hur värdefull varje delmängd är för deltagaren. $n$ $i$ $V_{i}:\mathbb {U} \to \mathbb {R}$ $U$

Låt vara en partition i mätbara uppsättningar : . Låt oss definiera en matris som en matris : $X$ $U$ $k$ ${\displaystyle U=X_{1}\sqcup \cdots \sqcup X_{k))$ $M_{X}$ $n\ gånger k$

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

Denna matris innehåller poängen för alla spelare för alla delar av partitionen.

Låt vara mängden av alla sådana matriser (för samma preferensmått, samma värde och olika partitioner): ${\mathbb {M}}$ $k$

\mathbb {M} =\{M_{X}\mid X

är en k -partition

U\}

Dubins-Spaniers satser handlar om de topologiska egenskaperna hos en mängd . ${\mathbb {M}}$

Uttalanden

Om alla preferensmått är räknat additiva och icke- atomära , då: $V_i$

${\mathbb {M}}$ kompakt ;
${\mathbb {M}}$ konvex .

Detta har redan bevisats av Dvoretsky, Wald och Vol'fovich [2] .

Konsekvenser

Konsekvent uppdelning

Att skära kakan i k delar kallas konsekvent skärning med vikter (de talar också om exakt uppdelning ) om: $X$ ${\displaystyle 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}

Det vill säga: alla deltagare är överens om att värdet på pjäsen j är lika med exakt . ${\displaystyle w_{j))$

Antag nu att det är vikter, vars summa är lika med 1: ${\displaystyle w_{1},w_{2},\ldots ,w_{k))$

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

och måttvärdena normaliseras så att varje deltagare utvärderar värdet på hela kakan till exakt 1:

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

Av konvexiteten i Dubins-Spaniers sats följer att [3] :

Om alla mätvärden är räknat additiva och icke-atomära, då finns en konsekvent partition.

Bevis: För alla definierar vi en partition enligt följande ${\displaystyle j\in \{1,\dots ,k\))$ $X^{j}$

X_{j}^{j}=U

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

I partitionen är alla poäng för deltagarna i den i:te delen lika med 1, och poängen för alla andra bitar är lika med 0. Därför innehåller matrisen endast ettor i den i:te kolumnen och nollor i alla andra. platser. $X^{j}$ $j$ $M_{X^{j))$ $j$

Enligt konvexiteten finns det en skiljevägg sådan att $X$

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

I denna matris innehåller den e kolumnen endast värdet . Detta betyder att i partitionen är alla uppskattningar av deltagarna i det -e stycket exakt lika med . $j$ ${\displaystyle w_{j))$ $X$ $j$ ${\displaystyle w_{j))$

Obs : Denna följd bekräftar Hugo Steinhaus tidigare påstående . Det ger också ett positivt svar på Nilen (floden) problemet, som säger att det bara finns ett begränsat antal översvämningshöjder.

Superproportionell division

Att skära kakan i n bitar (en för varje deltagare i divisionen) kallas en viktad superproportionell division om $X$ ${\displaystyle w_{1},w_{2},...,w_{n))$

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

Det vill säga att en pjäs som strikt är tilldelad en deltagare är mer att föredra för honom än en pjäs som han har rätt till. Följande påstående är Dubins-Spaniers sats om förekomsten av superproportionell division. $i$

Sats Låt vara vikter vars summa är lika med 1. Antag att punkten är en inre punkt i en (n-1)-dimensionell simplex med parvis distinkta koordinater och låt nyttomåtten normaliseras så att varje deltagare uppskattar hela kakan till exakt 1 (det vill säga måtten är icke-atomära sannolikhetsmått). Om minst två mått inte sammanfaller ( ), så existerar superproportionell division. ${\displaystyle w_{1},w_{2},...,w_{n))$ $w:=(w_{1},w_{2},...,w_{n})$ $V_{1},...,V_{n}$ $V_{i},V_{j}$ ${\displaystyle V_{i}\neq V_{j))$

Villkoret att nyttoåtgärder inte alla är identiska är nödvändigt. Annars leder summan till en motsägelse. $V_{1},...,V_{n}$ $\sum _{i=1}^{n}V_{i}(X_{i})=\summa _{i=1}^{n}V_{1}(X_{i})>\ summa _{i=1}^{n}w_{i}=1$

Sedan, om alla nyttomått är räknat additiva och icke-atomära, och det också finns två deltagare så att , så existerar superproportionell division. Det vill säga att ett nödvändigt villkor också är tillräckligt. $I j$ ${\displaystyle V_{i}\neq V_{j))$

Skiss av beviset

Antag utan förlust av allmänhet att . Sen finns det någon tårtbit som . Låt det vara ett tillägg . Sedan . Detta betyder att . Dock . Därför antingen , eller . Antag utan förlust av allmänhet att ojämlikheterna och är sanna. $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}\leqslant 1$ $V_{1}(Z)>w_{1}$ $V_{2}({\overline {Z)))>w_{2}$ $V_{1}(Z)>V_{2}(Z)$ $V_{1}(Z)>w_{1}$

Vi definierar följande snitt:

$X^{1}$ : ett snitt som ger bort medlem 1, medlem 2 och ingenting till de andra medlemmarna. $Z$ ${\overline {Z))$
${\displaystyle X^{i))$ (för ): styckning som ger hela kakan till den tävlande och ingenting till de andra. $i\geqslant 2$ $i$

Här är vi bara intresserade av diagonalen på matrisen , som representerar deltagarnas poäng från deras egna bitar: $M_{X^{j))$

I en matris är det första elementet , det andra elementet är , och de återstående elementen är 0. ${\textrm {diag}}(M_{X^{1}})$ $V_{1}(Z)$ $V_{2}({\overline {Z)))$
I en matris (för ) är ett element 1 och de andra elementen är 0. ${\textrm {diag}}(M_{X^{i}})$ $i\geqslant 2$ $i$

Genom konvexitetsvillkoret finns det för varje uppsättning vikter en skiljevägg sådan att $z_{1},z_{2},...,z_{n}$ $X$

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

Det är möjligt att välja vikterna på ett sådant sätt att de på diagonalen är i samma förhållande som vikterna . Eftersom vi antog att , kan vi bevisa det , så det är en superproportionell uppdelning. $z_{i}$ $M_{X}$ $w_{i}$ $V_{1}(Z)>w_{1}$ $\forall i\in 1\dots n:V_{i}(X_{i})>w_{i}$ $X$

Utilitaristisk-optimal division

Att skära tårtan i n bitar (en bit för varje deltagare) sägs vara utilitaristiskt – optimalt om det maximerar summan av nyttopoängen. Det vill säga den maximerar $X$

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

Utilitaristiskt optimala uppdelningar finns inte alltid. Låt oss till exempel säga att det är uppsättningen av positiva heltal. Låt det vara två deltagare, som båda utvärderar värdet av hela uppsättningen till 1. Deltagare 1 tilldelar ett positivt värde till varje heltal, och deltagare 2 tilldelar 0 till valfri ändlig delmängd. Ur en utilitaristisk synvinkel är det bäst att ge den första medlemmen en stor finit delmängd och ge resten till den andra medlemmen. När uppsättningen som ges till den första deltagaren blir större och större, kommer summan av värdena närmare och närmare 2, men vi kommer aldrig att få värdet 2. Det finns alltså ingen utilitaristisk-optimal uppdelning. $U$ $U$

Problemet i exemplet ovan är att måttet på användbarheten för medlem 2 är ändligt additiv, men inte räknat additiv .

Kompaktheten i Dubins -Spaniers sats antyder omedelbart att [4] :

Om alla preferensmått är räknat additiva och icke-atomära, då finns en utilitaristisk-optimal uppdelning.

I det här speciella fallet krävs inte icke-atomicitet - om alla preferensmått är countably additiva, då existerar en utilitaristisk-optimal division [4] .

Leximin-optimal division

Att skära tårtan i n bitar (en bit för varje deltagare) sägs vara leximinoptimalt med vikter om det maximerar en lexikografiskt ordnad vektor av relativa värden. Det vill säga, den maximerar följande vektor: $X$ ${\displaystyle 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}}

där medlemmar indexeras så att:

{V_{1}(X_{1}) \over w_{1}}\leqslant {V_{2}(X_{2}) \over w_{2}}\leqslant \dots \leqslant {V_{ n}(X_{n}) \över w_{n}}

Leximin-optimal skivning maximerar värdet av den fattigaste medlemmen (enligt deras vikt), sedan den näst fattigaste medlemmen, och så vidare.

Kompaktheten i Dubins -Spaniers sats antyder omedelbart att [5] :

Om alla preferensmått är räknat additiva och icke-atomära, då finns en leximinoptimal uppdelning.

Ytterligare forskning

Kriteriet på leximinoptimalitet, som introducerades av Dubins och Spanier, studerades därefter intensivt. I synnerhet för problemet med rättvis skärning av kakor studerades kriteriet av Marco Del Aglio [6] .

Se även

Lyapunovs vektormåttsats [7]
Wellers sats

Anteckningar

↑ Dubins och Spanier, 1961 , sid. ett.
↑ Dvoretzky, Wald, Wolfowitz, 1951 , sid. 59.
↑ Dubins och Spanier, 1961 , sid. 5.
↑ 1 2 Dubins, Spanien, 1961 , sid. 7.
↑ Dubins och Spanier, 1961 , sid. åtta.
↑ Dall'Aglio, 2001 , sid. 17.
↑ Neyman, 1946 , sid. 843–845.

Litteratur

Lester Eli Dubins, Edwin Henry Spanier. Hur man skär en tårta rättvist // The American Mathematical Monthly. - 1961. - T. 68 . - doi : 10.2307/2311357 . — .
Dvoretzky A., Wald A., Wolfowitz J. Relationer mellan vissa områden av vektormått // Pacific Journal of Mathematics. - 1951. - T. 1 . - doi : 10.2140/pjm.1951.1.59 .
Marco Dall Aglio. Optimeringsproblemet Dubins–Spanier i teorin om rättvis division // Journal of Computational and Applied Mathematics. - 2001. - T. 130 . - doi : 10.1016/S0377-0427(99)00393-3 .
Neyman J. Un théorem dʼexistence // CR Acad. Sci .. - 1946. - T. 222 .