{
"cells": [
{
"cell_type": "markdown",
"id": "d8d13ed7",
"metadata": {},
"source": [
"# 1. Zmrzlináři na úsečce\n",
"Mějme pláž ve tvaru úsečky, například o délce $1$. V každém bodě pláže jsou lidé, kteří mají zájem o nákup zmrzliny. Poptávka v bodě $x$ se značí $d(x)$. \n"
]
},
{
"cell_type": "markdown",
"id": "5df61049",
"metadata": {},
"source": [
"\n",
"Na pláž mohou hráči, tzv. *zmrzlináři*, umísťovat stánky se zmrzlinou. Předpokládá se, že všechny stánky prodávají zmrzlinu za stejnou cenu. Lidé proto kupují zmrzlinu u stánku, který je nejblíže. Je-li nějakému bodu pláže nejblíže více zmrzlinářů, dělí se poptávka rovným dílem mezi ně.\n",
"Zmrzlináři obecně usilují o to, aby prodali co nejvíce zmrzliny.\n",
"\n",
"## 1.1. zmrzlinář s konstantní poptávkou\n",
"Řekněme, že poptávka po zmrzlině v jednotlivých bodech je konstantní, např. $d(x) = 1$."
]
},
{
"cell_type": "markdown",
"id": "8e306bba",
"metadata": {},
"source": [
"**Úloha 1.1:** Jak vypadá funkce výplaty zmrzlináře $f_1(x_1)$ v závislosti na pozici $x_1$ zmzlináře? Jak vypadá množina optimálních pozic zmrzlináře? \n",
"\n",
"Řešení
\n",
"Na pozici stánku nezáleží, v každém bodě pláže zmrzlinář získá poptávku $1$. Délka pláže je $1$, tedy $f_1(x_1) = 1\\cdot 1=1$. Množina optimálních pozic je celá úsečka $[0,1]$.\n",
" "
]
},
{
"cell_type": "markdown",
"id": "106855cd",
"metadata": {},
"source": [
"## 1.2. 1 zmrzlinář s lineárně klesající poptávkou\n",
"Řekněmě, že poptávka po zmrzlině lineárně klesá tempem $a$ se vzdáleností od stánku, nemůže však přitom klesnout pod hodnotu 0. Je-li pozice stánku $x_1$, $d(x) = \\max(0,1 - a \\lvert x - x_1 \\rvert$)."
]
},
{
"cell_type": "markdown",
"id": "6cbfeb11",
"metadata": {},
"source": [
"**Úloha 1.2:** Jak vypadá funkce výplaty zmrzlináře $f_1(x_1)$ v závislosti na pozici $x_1$ zmrzlináře pro $a=3$? Jak vypadá množina optimálních pozic? \n",
"\n",
"Řešení
\n",
"\n",
"V místě stánku je poptávka $1$. Se vzdáleností od stánku se lineárně snižuje; nemůže přitom být Nulová poptávka je ve vzdálenosti $\\frac{1}{3}$. \n",
"\n",
"Pokud by pláž byla nekonečně dlouhá, stačilo by uvažovat úhrn poptávky na intervalu $[x_1-\\frac{1}{3}, x_1 + \\frac{1}{3}]$. Tento úhrn je roven obsahu $2$ pravoúhlých trojúhelníků o výšce $1$ a základně $\\frac{1}{3}$, což dává obsah $2\\cdot \\frac{1}{2} \\cdot 1 \\cdot \\frac{1}{3} = \\frac{1}{3}$.\n",
"\n",
"Pláž však nekonečně dlouhá není. Na jedné či druhé straně od $x_1$ může být $x_1 - \\frac{1}{3}\n",
" < 0$ nebo $x_1 + \\frac{1}{3} > 1$. Pak v do úhrnu poptávky nebudou započítány části výše zmíněných pravoúhlých trojúhelníků, např. nalevo od $x_1$ by šlo o část odpovídající pozicím pláže $[x_1 - \\frac{1}{3}, 0]$. Tahle část je sama o sobě pravoúhlým trojúhelníkem o základně $\\delta_l(x_1) \\coloneqq \\max(0, -(x_1 - \\frac{1}{3}))$ a výšce $a \\delta_l(x_1)$. Obsah tohoto nezapočítávaného trojúhelníku je tedy $\\frac{1}{2}a(\\delta_l(x_1))^2$. \n",
"Podobně lze vyjádřit i obsah nezapočítávaného trojúhelníku napravo, jen místo $\\delta_l(x_1)$ použijeme délku základny pravého trojúhelníka, konkrétně $\\delta_p(x_1) \\coloneqq \\max(0, x_1+\\frac{1}{3} -1 )$.\n",
"$$ f_1(x_1) = \\frac{1}{3} - \\frac{1}{2}a((\\delta_l(x_1))^2 - (\\delta_p(x_1))^2)$$ \n",
"\n",
"Zřejmě, výplata bude maximální pro taková $x_1$, pro která se od obsahu $\\frac{1}{3}$ nebude nic odečítat. Označíme-li $x_1^*$ optimální pozici zmrzlináře, můžeme tvrdit, že $$x_1^* \\in \\left\\{x_1 \\in [0,1] \\mid x_1 -\\frac{1}{3} \\ge 0 \\land x_1 + \\frac{1}{3} \\le 1 \\right\\} = \\left[\\frac{1}{3},\\frac{2}{3}\\right]$$\n",
" "
]
},
{
"cell_type": "markdown",
"id": "df150aa3",
"metadata": {},
"source": [
"**Úloha 1.3:** Jak vypadá funkce výplaty zmrzlináře $f_1(x_1)$ v závislosti na pozici $x_1$ zmrzlináře pro obecné $a>0$? Jak vypadá množina optimálních pozic?\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "0bb5e6e3",
"metadata": {},
"outputs": [],
"source": [
"def delta_l(x1, a=3):\n",
" return max(0, -(x1 - 1/a))\n",
"\n",
"def delta_p(x1, a=3):\n",
" return max(0, x1 + 1/a -1)\n",
"\n",
"def f1(x1, a=3):\n",
" return 1/a - a/2 * (delta_l(x1, a)**2 + delta_p(x1, a)**2)"
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "c8865e35",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"x=0.000, f1=0.166667\n",
"x=0.083, f1=0.239583\n",
"x=0.167, f1=0.291667\n",
"x=0.250, f1=0.322917\n",
"x=0.333, f1=0.333333\n",
"x=0.400, f1=0.333333\n",
"x=0.500, f1=0.333333\n",
"x=0.583, f1=0.333333\n",
"x=0.667, f1=0.333333\n",
"x=0.833, f1=0.291667\n",
"x=0.917, f1=0.239583\n",
"x=1.000, f1=0.166667\n"
]
}
],
"source": [
"a = 3\n",
"test = [0, 1/12, 1/6, 1/4, 1/3, 2/5, 1/2, 7/12, 2/3, 5/6, 11/12, 1]\n",
"for x in test:\n",
" print(f\"x={x:.3f}, f1={f1(x, a):.6f}\")"
]
},
{
"cell_type": "markdown",
"id": "348e05bc",
"metadata": {},
"source": [
"**Důležité je, že *optimální* nebo *racionální* chování je takové, které hráč/rozhodovatel nemá motivaci měnit, protože by změnou nedosáhl zvýšení výplaty.**\n",
"\n",
"## 1.3. 2 Zmrzlináři s konstantní poptávkou\n",
"Vraťme se ke konstantní poptávce po zmrzlině v jednotlivých bodech, tj. $d(x) = 1$. Označme $x_1, x_2$ pozice, na které umístí své stánky zmrzlináři; ty budeme označovat 1 a 2. \n",
"\n",
"**Stejně jako v předchozím případě považujme za *optimální* chování takové, které hráči nemají motivaci měnit. Pokud se hráči svými volbami ovlivňují, je nutné *optimalitu* posuzovat v kontextu chování všech hráčů najednou.**"
]
},
{
"cell_type": "markdown",
"id": "e8f5168b",
"metadata": {},
"source": [
"**Úloha 1.4:** Jak vypadají výplatní funkce $f_1(x_1, x_2)$ a $f_2(x_1, x_2)$ zmrzlinářů?\n",
"Řešení
\n",
"\n",
"Protože veškerá poptávka se bude realizovat u některého ze zmrzlinářů, nezávisle na dvojici pozic $(x_1, x_2)$ bude \n",
"$$ f_1(x_1, x_2) + f_2(x_1, x_2) = 1 \\cdot 1 = 1.$$ \n",
"Stačí proto říci, že $f_2(x_1, x_2) = 1-f_1(x_1, x_2)$ a zabývat se jen podobou funkce $f_1$.\n",
"\n",
"O zmrzlináři, ke kterému je to z nějakého bodu pláže nejblíže, budeme říkat, že daný bod *ovládá*. Podobu úseku pláže, který bude zmrzlinář 1 ovládat, závisí na tom, který ze zmrzlinářů stojí více nalevo. Pokud $x_1 < x_2$, ovládá zmrzlinář 1 úsek v intervalu $\\left[0,\\frac{x_1+x_2}{2}\\right]$, pokud $x_1 > x_2$, jde naopak o úsek $\\left[\\frac{x_1+x_2}{2},1\\right]$. Pokud $x_1 = x_2$, ovládají oba zmrzlináři celou pláž, ale o poptávku se dělí rovným dílem.\n",
"\n",
"Protože poptávka ve všech bodech pláže je stejná (jednotková), je úhrn poptávky realizované u zmrzlináře závislý délce že. Výplatní funkci zmrzlináře 1 lze zapsat takto:\n",
"$$\n",
"f_1(x_1,x_2) = \\begin{cases} \\frac{x_1+x_2}{2} & \\text{ pokud } x_1 < x_2, \\\\ 1- \\frac{x_1+x_2}{2} & \\text{ pokud } x_1 > x_2,\\\\ 0.5& \\text{ jinak (pokud $x_1 = x_2$).}\\end{cases}\n",
"$$\n",
"Řešení
\n",
"\n",
"Pojďme dokázat, že jediné optimální chování je dvojice pozic $(0.5, 0.5)$. Potřebujeme udělat dvě věci:\n",
"1. Ukázat, že $(0.5, 0.5)$ je optimální, \n",
"2. ukázat, že jakákoli jiná dvojice pozic optimálním chováním není a alespoň jeden z hráčů by měl motivaci své chování měnit. \n",
"\n",
"Věnujme se nejprve bodu 2. \n",
"Zabývejme se dvojicemi pozic $(x_1, x_2)$, kde $x_1 \\not = 0.5$ a ukažme, že nemohou být optimálním chováním. Dvojice, ve kterých $x_2 \\not = 0.5$ rozebírat nemusíme, protože je pozice hráčů ve hře symetrická v tom smyslu, že je lze jakkoli přejmenovat -- toto plyne z faktu, že $f_1(x',x'') = f_2(x'', x')$. \n",
"Klíčovým pozorováním je to, že zmrzlinář 2 může $x_2$ nastavit na hodnotu libovolně blízkou $x_1$ ze směru od $\\frac{1}{2}$, například o $2\\varepsilon$ vedle pro dostatečně malé $\\varepsilon > 0$. Pak je výplata zmrzlináře 2 následující: pro $x_1 < 0.5$ je $f_2(x_1,x_1+2\\varepsilon) = 1 - (x_1 + \\varepsilon)>0.5$, pro $x_1 > 0.5$ je $f_2(x_1,x_1-2\\varepsilon) = x_1 - \\varepsilon > 0.5$. V obou případech je výplata tím větší, čím blíže je $\\varepsilon$ nulové hodnotě. Pro každé $x_2$ ve dvojici $(x_1,x_2)$ tak existuje ještě lepší $x'_2$.\n",
"\n",
"Co se týče bodu 1, opět stačí zabývat se potenciálními pozicemi hráče 1. Případné změny pozice hráče 2 můžeme modelovat přeznačením hráčů. Pro dvojici pozic $(0.5, 0.5)$ má hráč 1 výplatu $f_1(0.5, 0.5) = 0.5$. Máme-li $\\varepsilon \\in (0, 0.25]$, hráč 1 může změnit svoji pozici buď na $x'_1 = x_1 -2\\varepsilon < 0.5$, nebo na $x'_1 = x_1 + 2\\varepsilon$. V obou případech výplata hráče 1 klesne na $0.5 - \\varepsilon$.\n",
"\n",
"**Za povšimnutí stojí, že pro pevné $x_1 \\not 0.5$ neexistuje optimální chování druhého zmrzlináře, které by maximalizovalo jeho výplatu. Naproti tomu pokud $x_1 = 0.5$, je optimálním chováním druhého zmrzlináře $x_2=0.5$.**\n",
"