Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 2.11.2020 (L) Vykreslete si svůj první matematický výraz přes MathJax!
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 15. 08. 2013 21:47

check_drummer
Příspěvky: 3183
Reputace:   86 
 

První neopakující se číslo

Ahoj,
nakonec jsem se rozhodl dát otázku do této sekce:

Nechť je dáno n hráčů a každý vybere nějaké přirozené číslo od 1 do m (případně lze vybírat ze všech přirozených čísel) aniž by ostatní hráči znali jeho volbu. Vyhrává ten, jehož číslo je nejmenší a současně žádný jiný hráč nevybral stejné číslo jako on.

Nevím, zda lze tuto úholu nějak "rozumně" řešit, ale možná pomocí teorie her by to šlo - např. zvolit nějakou strategii, která říká, že s pravděpodobností p(i) mám zvolit číslo i, apod.

To, že nějaká strategie nejspíš existuje, může naznačit to, že pokud n=3 a např. m=1000, pak úspěšnější strategií bude náhodně vybírat jedno z čísel 1,2,3,4,5,6 (se stejnou pravděpodobností 1/6) než např. náhodně vybírat mezi čísly 100 a 101 (s pravděpodobností 1/2).


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#2 16. 08. 2013 10:37 — Editoval halogan (16. 08. 2013 10:41)

halogan
Ondřej
Místo: UK
Příspěvky: 4528
Škola: IES FSV UK (09-12, Bc.)
Pozice: student
Reputace:   106 
 

Re: První neopakující se číslo

Trochu fuzzy vyjadřování, takže přesně nevim, jak to chcete vyřešit.

Z hlediska teorie her můžeme prostě a jednoduše najít ekvilibrium. Zjednoduším to prozatím na ryzí strategie. Víme, že ekvilibrium se smíšenou strategií u konečných her existuje vždy, tak se napřed podíváme na ryzí, které jsou jen variantou těch smíšených.

Mějme n=2, pak existují následující strategie, které jsou ekvlibrijní. Hráč A hraje 1, hráč B hraje cokoliv (máme tak už m strategií). Pokud hráč A hraje cokoliv mimo 1, hráč B hraje 1. Zrcadlově stejně pro prohozené role. Vypadá to asi na m^2 ryzích ekvilibrijních strategií.

Cítím potřebu po nějaké pareto optimální strategii, zkusím to rozmyslet. Společně se smíšenými. Mám takový pocit, že smíšené strategie nebudou fungovat, alespoň ne pro n=2, protože nejlepší odpověď na smíšenou strategii je ryzí, kde se hraje 1 vždy.

Offline

 

#3 17. 08. 2013 11:34

check_drummer
Příspěvky: 3183
Reputace:   86 
 

Re: První neopakující se číslo

↑ halogan:
Pokud jsou dva hráči, pak hrát vždy 1 je určitě nejlepší - nemůžu prohrát. Ale už u třech kráčů (pokud nekooperují) je to složitější - dva mohou zahrát 1 a třetí hráč 2 a ten pak zvítězí.
Když to řeknu úplně jednoduše - hledáme nějakou strategii (tj. postup jak zvolit číslo), abych po mnoha opakujících se hrách dosáhl co nejlepšího výsledku. Jednou z možných strategií je, jak píšu výše, každé hodnotě přiřadit pravděpodobnost a pak z tohoto pravděpodobnostního rozdělení náhodně vybrat číslo a to bude mým tipem. Další otázka je, zda protihráči mohou znát mou strategii nebo ne, ale předpokládejme že ne - oni by se měli asi řídit nějakým minimax pravidlem, tedy předpokládat, že já hraju co nejlépe a na základě toho volit svou vlastní strategii.

Možná by čiště pro zajímavost mohlo být zajímavé navrhnout strategii pro n=3 hráče. A pak třeba simulací určit, která je lepší. Ono to ale záleží i na tom, jak jsou všichni soupeři chytří. Když třetí hráč bude "hloupý" a bude stále tipovat číslo 100, pak se bude de facto jednat o hru dvou hráčů a tady se již vyplatí tipovat 1.


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#4 17. 08. 2013 11:47 — Editoval halogan (17. 08. 2013 11:52)

halogan
Ondřej
Místo: UK
Příspěvky: 4528
Škola: IES FSV UK (09-12, Bc.)
Pozice: student
Reputace:   106 
 

Re: První neopakující se číslo

Já mám stále problém, že úplně nevím, co a jak chcete vyřešit. Jednorázové a opakované hry mají dost odlišná řešení. U opakované hry je těžké až nemožné mít profitující strategii, když jsou všechny "hlasy" veřejné. Takže určit předem, jestli to je jednorázové nebo opakované, to drasticky mění postup.

check_drummer napsal(a):

↑ halogan:
Pokud jsou dva hráči, pak hrát vždy 1 je určitě nejlepší - nemůžu prohrát.

Jak říkám, neni to tak jednoduchý. Nejde jen o to "hrát 1", ekvlibrijní je i nehrát 1, pokud ji ten druhý hraje. Strategie musíme definovat pořádněji.


n=3 je zajímavé, podívám se na to. Co jsem tak včera přemýšlel, tak bude důležité odlišit sudý a lichý počet hráčů, protože určité číslo budou hrát v ~[n/2] případech dva lidi.

(Jen takhle od boku bych řekl, že ekvilibrijních strategií bude šílený množství. Ono hrát [a,b,c], kde a=1, a < b < c je ekvilibrium [teď nepíšu strategii, jen co hrajou].)

Offline

 

#5 17. 08. 2013 12:17

check_drummer
Příspěvky: 3183
Reputace:   86 
 

Re: První neopakující se číslo

↑ halogan:
V jakém případě mohou mít jednorázové a opakované hry odlišná řešení? Nelze opakovanou hru považovat za několik jednorázových her po sobě? Jediné co mě napadá, že je rozdílné, že je možné využít toho, jak hráli soupeři, ale pokud budeme předpokládat, že ani to nám nebude známo, pak nevidím mezi oběma typy her rozdíl - snad jen v možné "jistotě" zisku: Hrát jednu hru takovou, že když padne panna, zaplatím 500tis. a když padne orel, tak získám 1mil. bych nehrál. Ale hrát tuto hru opakovaně (např. 1000x) s tím, že vyúčtování proběhne až nakonec, s tím bych souhlasil.

No, ale i kdyby bylo známo jak hráli v minulých hrách soupeři, pak je otázka, zda lze tuto informaci dále využít: Každý soupeř může přece v každém svém kroku volit jiný postup (jiné pravděpodobnostní rozdělení, apod.).

Možná jsem chybně použil slovo strategie, která už má v teorii her svou definici. Jde o to, stanovit postup, na základě kterého zvolím své číslo. Vím jen to, kolik hraje hráčů, ale neznám ani jejich postup, který při volbě svého čísla volí, ani číslo které zvolili a při opakovaných hrách budeme pro jednoduchost zkoumat případ, kdy toto neznáme ani v minulých hrách.

(Toto opakování má význam pro simulaci, ky bychom počítačem chtěli ověřit úspěšnost daných postupů. Zde je vhodné hry opakovat a "zprůměrovat" a po několika opakováních zjistit nejlepší postup - hráče, který nejčastěji vyhrál a předpokládáme, že s rostoucím opakováním her nebudou výhry jen otázkou náhody, ale spíše vhodného postupu.)

Dle mého by tímto rozumným postupem mohl být výše uevdený pravděpodobnostní přístup, ale lze zvolit libovolný jiný. Formálně by asi šlo o nějaký algoritmus, ve kterém může figurovat náhodný prvek, a jehož výsledkem je tipované číslo.

Jinak pro n=2 nevidím lepší postup než hrát stále číslo 1. Ale zde bychom měli definovat co je to lepší postup. Asi nějaká agregace (průměrný zisk) přes všechyn možné postupy. Ale tak se zase vystavujeme tomu, že do této agregaci zahrneme i "špatné" postupy, které by asi nikdo nikdo nehrál (např. v případě n=2 tipovat 100, apod.) a to dle mého také není správně. Případně bychom lepší postup mohli definovat tak, že necháme hráče s těmito postupy hrát proti sobě. Ale to může narazit na to, že postupy nemusí být co se týká výhry tranzitivní. Když A porazí B a B porazí C, pak i C může porazit A.

Možná pro n=3 bychom mohli přizvat ještě jednoho hráče a každý by si mohl promyslet svůj postup.


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#6 17. 08. 2013 12:42

halogan
Ondřej
Místo: UK
Příspěvky: 4528
Škola: IES FSV UK (09-12, Bc.)
Pozice: student
Reputace:   106 
 

Re: První neopakující se číslo

Ano, z teoretického hlediska je to to samé, jediný rozdíl by byl, pokud bychom implementovali nějaké trestací mechanismy. Je to ale diametrálně odlišné z empirického hlediska. To jsem ještě nezmiňoval, ale empirie se v teorii her často dost liší od teorie, surprise :-)

Co se týče empirického testování opakovaných her, tak se často dělá chytrá věc — hraje se třeba 10 kol a vylosuje se na konci náhodné číslo a z té hry všichni dostanou své výhry. Takže člověk nemůže trestat, nemůže akumulovat, ... jen se snaží přizpůsobit strategii ostatních.

Offline

 

#7 17. 08. 2013 21:28 — Editoval check_drummer (18. 08. 2013 19:26)

check_drummer
Příspěvky: 3183
Reputace:   86 
 

Re: První neopakující se číslo

↑ halogan:
Přemýšlím o triviální hře: kámen, nůžky, papír (K,N,P). Zde zřejmě neexistuje deterministický postup, jak volit symbol (K,N nebo P) v následující hře, ale na druhou stranu mi na první pohled přijde optimální postup, kdy náhodně s pravděpodobností 1/3 zvolím jeden ze symbolů. Optimální ve smyslu, že se snažím, aby "nejhorší případ byl co nejlepší" - tedy ať hraje soupeř jak hraje, chtěl bych svou ztrátu minimalizovat.

Jinak k té naší hře pro n=3 mě zatím napadlo, že postup by mohl být (nečti však za účelem, abys proti ní vymyslel postup lepší - viz text dále):



Zatím jsem se nepokoušel ani k K,N,P ani u této dokázat, že tyto postupy jsou opravdu nejlepší.

V některých hrách ale může, myslím si, nastat to, že k postupu A existuje lepší postup B než A a k němu zas lepší postup C než B, ovšem A je lepší než B (tedy relace "být lepší" není tranzitivní), psal jsem o tom i výše. To by ale znamenalo, že žádný nejlepší postup neexistuje a je jen na náhodě jaký postup zvolíme (zda A,B, nebo C). Jistě, může existovat více postupů, které jsou "horší" než A,B, i C, ale A,B,C jsou v jistém smyslu ekvivaletní, že nelze říci, který z nich je lepší. Je to vlastně takové kvaziuspořádání.

Otázka je, zda to, že se na konec po několika hrách vylosuje náhodné číslo a z té hry pak všichni dostanou své výhry, je spravedlivé: To pak může mít za následke strategii, kdy se snažím co nejvíce her vyhrát, byť i s malým ziskem, a počítat ve své strategii s tím, že několik málo her prohraju s obrovskou ztrátou. Díky náhodnosti bude pravděpodobnost, že tyto prodělečné hry budou vybrány, malá, a tedy bude tento postup vhodnější než se snažit, řekněme, polovinu her vyhrát a polovinu prohrát a zisk a ztráta se budou v každé hře rovnat. Např. pokud bychom měli strategii A, že z 100 her (přibližně) v 99 vyhraju 1Kč a v jedné prohraju 99Kč a měli bychom stratiegii B, že v 50 hrách vyhraju 1Kč a v 50 hrách prohraju 1Kč, pak nejspíš pro postup, kdy se náhodně vybere jedna ze sehraných her a podle ní se vyplatí výhry, je lepší strategie A. To ovšem platí v případě, kdy je těch 100 her sehráno jen jednou, nikoli opakovaně - jinak by asi A a B při velkém počtu sehrání těchto 100 her byly rovnocenné.


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#8 16. 01. 2021 09:05

check_drummer
Příspěvky: 3183
Reputace:   86 
 

Re: První neopakující se číslo

Napadlo mě další upřesnění: Předpokládejme, že všichni hráči budou vybírat ze stejného náhodného rozdělení. Jaké rozdělení je nejvýhodnější, abych měl co největší pravděpdoobnost výhry?

Obecně by ten problém v zadání šel možná řešit tak, že bychom nejprve náhodně vybrali nějaké rozdělení a z něj pak opět náhodně nějaké číslo. A pravděpodobnost výběru konkrétního rozdělení by byl odáno tím, jak moc je výhodné.


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

#9 10. 02. 2021 19:55

check_drummer
Příspěvky: 3183
Reputace:   86 
 

Re: První neopakující se číslo

Pokud budou hráči vybírat ze stejného náhodného rozdělení a chci, aby měl každý co největší pravděpodobnost výhry, tak mě napadlo, že hodnotu 1 zvolíme s pravděpodobností [mathjax]p_1[/mathjax] tak, aby ji průměrně zvolil 1 hráč, což podle mě vede na rovnost [mathjax]{p_1}^n=\frac{1}{n}[/mathjax], tj. [mathjax]p_1=\sqrt[n]{\frac{1}{n}}[/mathjax]. A stejně tak by bylo rozumné volit, že čísla 1,2 vyberou průměrně 2 hráči, takže označím-li jako [mathjax]s_2[/mathjax] pravděpodobnost, že hráč zvolí 1 nebo 2, tak chceme, aby [mathjax]{s_2}^n=\frac{2}{n}[/mathjax], tj. [mathjax]s_2=\sqrt[n]{\frac{i}{n}}[/mathjax], a pak bude [mathjax]p2=s_2-p_1[/mathjax] pravděpodobnost, že zvolíme právě hodnotu 2. A tak lze postuupovat dále. (Případně nakonec všechna [mathjax]p_i[/mathjax] znormujeme jejich součtem, abychom dostali úplnou pravděpodobnost.)
Asi to není úplně korektní, ale bylo by zajimavé nějakou simulací zjistit, zda je toto lepší (tj. zda má každý hráč větší šanci na výhru) než např. rovnoměrné rozdělení, kdy jen náhodně zvolím jedno číslo mezi 1 a n.


Popelka - pohádka o neprosté funkci nabývající minima v jediném bodě

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson