Finkův protokol

Fink Protocol [1] (také známý jako Consecutive Pairs [2] nebo Single Chooser [3] ) je proporcionální protokol sdílení koláčů .

Hlavní výhodou protokolu je, že funguje online, i když není předem znám počet účastníků dělení. Když se nový člen připojí k divizi, stávající divize je přestavěna tak, aby byla pro nováčka spravedlivá divize s minimálním dopadem na stávající členy.

Hlavní nevýhodou protokolu je, že místo jednoho souvislého kusu protokol přiděluje účastníkovi velké množství „drobků“.

Protokol

Protokol popisujeme induktivně zvýšením počtu účastníků.

Když se soutěžící č. 1 připojí do party, vezme si celý dort. Hodnota jeho akcií je 1.

Když soutěžící č. 2 dorazí, soutěžící č. 1 rozřeže dort na dva kusy, které jsou v jejich očích stejné. Nový účastník si vybere kousek, který je v jeho očích lepší. Hodnota pro každého účastníka je nyní alespoň 1/2 (jako v protokolu rozděl a vyber ).

Když se připojí účastník č. 3, oba účastníci č. 1 a č. 2 si v očích rozdělí své podíly na 3 stejné části. Nový účastník si vybere jeden kus od každého účastníka. Hodnoty pro účastníky #1 a #2 jsou alespoň 2/3 jejich předchozí hodnoty, která byla 1/2. Jejich nová hodnota tedy není menší než 1/3. Hodnota pro soutěžícího č. 3 je alespoň 1/3 plátku č. 1 a 1/3 plátku 2, což mu dává alespoň 1/3 celého koláče.

Obecně platí, že když se účastník #i připojí ke skupině, předchozí účastníci i -1 rozdělí své podíly na i stejné díly a nový účastník si vybere figurku z každé hromádky. Opět lze ukázat, že hodnota pro každého účastníka je alespoň 1/ n celkové hodnoty, takže řez je proporcionální.

Počet řezů

Přímá aplikace algoritmu dá kousky, i když ve skutečnosti jen asi , protože každý účastník potřebuje škrty, když dorazí -tý účastník.

Aplikace

Fink protokol se používá jako pomocný algoritmus v jiných protokolech pro spravedlivé rozdělení koláče:

Poznámky

  1. ↑ Fink, 1964 , str. 341.
  2. ↑ Saaty, 1970 .
  3. ↑ Brams a Taylor 1996 , str. 40.

Literatura