Fórum: Játékelmélet

> .. én arra gondoltam, hogy a naiv döntések mindig jók, ha a kísérlet a valóságban realizálható, azaz ha lejátható tetszőlegesen sokszor.

Na jó, ez általánosan nyilvánvalóan nem igaz. A várható értékre való hajtás pont azt jelenti, amit. Rengeteg különböző döntési elv létezik. Például egy másik a maximin vagyis a pesszimista/óvatos döntés. Egy maximin például nem kezd bele olyan játékba ahol veszthet is, nem csak nyerhet.

(Például a Szentpétervár paradoxonnál jól látszik hogy aki a várható értékre hajt, az jól pórul jár, míg aki rögtön megáll, annak megmarad az 1 dollárja.)

De talán ha a természet ellen játszunk, és akárhányszor játszhatunk, akkor a várható értékre szokás hajtani.

Két borítékos paradoxon

Eléd raknak egy X és egy Y feliratú borítékot, pénzzel bennük.

Elárulják neked, hogy a bennük levő pénz eloszlása (forintban)

\(\displaystyle P[X=2^k \text{ és } Y=2^{k+1}] ~~~=~~~ P[X=2^{k+1} \text{ és } Y=2^{k}] ~~~=~~~ \frac{2^{k-1}}{3^{k+1}}. \)

a) Melyik borítékot kéred a kettő közül?
b) Megmutatják hogy az X borítékban mennyi van. Most melyik borítékot kéred?
c) Megmutatják hogy az X borítékban mennyi van, majd lehetőséget adnak hogy az X boríték helyett megvehesd az Y borítékot 1 fillérért. Most melyik borítékot kéred?
d) Egyik boríték tartalmát sem mutatják meg. Az Y borítékért fizetned kell 1 fillért, az X boríték ingyen van. Most melyik borítékot kéred?

A célod az, hogy olyan stratégiát válassz, hogy maximalizáld a nyereséged várható értékét. (Egyet játszhatsz.)

Kapcsolódó wiki szócikk (+ hivatkozások a cikkben)

- - -

Mondjuk naiv döntésnek nevezem az olyan döntéseket vagy döntéssorozatokat, amikor a természet ellen játszunk, van egy adott eloszlásunk, és szeretnénk a várható értéket maximalizálni. (az elnevezés a naiv halmazelmélet mintájára – amíg valaki nem ad jobbat)

Például: ha eltalálom egy pénzfeldobás értékét, és az fej akkor kapok 2 csilliárd forintot a banktól, ha az írás, akkor 2 forintot, ha nem találom el, akkor semennyit. Itt a naiv stratégia azt adja, hogy érdemes fejre tippelnem.

Milyen értelemben jó ez a döntés 1 játék esetén?
Mik a feltételei annak, hogy ez a döntés ebben az értelemben jó legyen? (két boríték esetén talán nem jó az ilyen típusú döntés)

.. én arra gondoltam, hogy a naiv döntések mindig jók, ha a kísérlet a valóságban realizálható, azaz ha lejátható tetszőlegesen sokszor.
((BROOME szerint ez az eloszlás megkonstruálható egy \(\displaystyle 1/3 - 2/3\) ferde pénz dobálásával; de szerintem még ha 0 esélyű is, előfordulhat hogy végtelen sokáig dobálunk. Ahogy talán még számítógéppel sem közelíthető meg az eloszlás úgy, hogy az mindig megálljon.))
Azaz szerintem ha a természetnek véges sok lehetősége van, akkor ez a döntés valamilyen értelemben kívánatos eredményt ad, már 1 játék esetén is. Persze ezt nem csak bebizonyítani nem tudom, de megfogalmazni sem.

Miben különbözik ez a két leveles döntés mondjuk egy tőzsdei döntéstől ahol ezt az eloszlást feltételezzük?

Mik a jó stratégiák a-d) -re (ha a feladat a várható nyeremény maximalizálása)?

Helyes megoldás.

A hiányzó utolsó kaméleonos részfeladat megoldása: tehát kell 2 stratégia, amelyeknél a lépések számának eloszlása nem azonos!

Legyen az első stratégiám az, hogy minden lépésben kiválasztok a leggyakoribb és a legritkább színű kaméleonok közül egyet-egyet (, ha több leggyakoribb/legritkább szín van, akkor ezen színek közül véletlenül választok egyet). A második stratégiám pedig, hogy a két legritkább szín közül választok egy-egy kaméleont. Az első stratégia esetén pozitív (\(\displaystyle n>1\)-re \(\displaystyle \frac {1}{2^{n-2}}\)) annak a valószínűsége, hogy a játék (pontosan) \(\displaystyle n-1\) lépés alatt véget ér (az első lépés után mindig a leggyakoribb színnek kell győznie). Míg a második stratégia esetén \(\displaystyle n>3\)-ra a játék nem érhet véget \(\displaystyle n-1\) lépés alatt (az első lépés után marad 2 szín amikből csak egy-egy kaméleon van, így legalább 2+(n-2)=n lépés kell). Így a 2 stratégia várható lépéseinek eloszlása is különböző \(\displaystyle n>3\) esetén, míg \(\displaystyle n\le 3\)-ra viszont azonos (ekkor egyébként nem csak az eloszlás azonos, hanem még \(\displaystyle n=3\)-ra is lényegében \(\displaystyle 1\) stratégia van, ha a szimmetriáktól eltekintünk).

Most, hogy így kifejted, már értem a bizonyításodat. Igen, ez egy jó bizonyítás, és egyszerűbb, mint amiket eddig hallottam. Köszönöm.

Most már értem, teljesen jó a megoldásod. És itt \(\displaystyle \frac {n*E}{2}=\frac {n(n-1)}{2}\) a lépések várható száma, függetlenül a stratégiától.

Nem szeretném ilyen sorrendben lejátszani. Szerintem nem bizonytalan az állítás. Ha van valamennyi zöld és "nem zöld" kaméleonom, akkor a zöldeket érintõ lépések száma akkor is tönkremenési feladat, és a várható értéke akkor is fix, ha a "nem zöld" kaméleonokkal is lépek közben. Akár egy színre hozom a nem zöldeket, akár egyáltalán nem lépek velük, akár teljesen random stratégia szerint lépek, a zöld-lépések számának várható értéke független.

(Csak megismételtem amit írtam.)

Fogalmam sincs, de egy lónál természetesen dupla vastag fal kéne. Szerintem nem lehet megállítani a lovat.

Elmondom még egyszerűbben: egy "menet"-ben \(\displaystyle k\) egyforma színű kaméleon legyen, míg a többi \(\displaystyle (n-k)\) kaméleon páronként különböző színű és a \(\displaystyle k\) kaméleontól is különböző színű. Használjuk azt a még bizonyítatlan állítást, hogy a várható érték ftlen a stratégiától. Legyen az a stratégiám, hogy a \(\displaystyle k\) egyforma kaméleon és egy rögzített másik színű kaméleonok között választok mindig \(\displaystyle 2\) kaméleont. Ez pont egy tönkremenési probléma (az \(\displaystyle (1,k)\) helyről indított \(\displaystyle p=q=\frac 12\) valószínűséggel): a menet végén (k+1) egyforma színű kaméleonunk lesz. A menet várhatóan \(\displaystyle k\) ideig tart (ez ismert a tönkremenési problémánál), így a teljes játék várható lépéseinek száma \(\displaystyle \frac{n(n-1)}{2}\).

Egy szimuláció is álljon itt: \(\displaystyle n=8\)-ra és véletlen stratégiával, azaz véletlenül választok ki mindig \(\displaystyle 2\) különböző színű kaméleont. \(\displaystyle 10^6\) esetet szimulálva az össz lépésszám \(\displaystyle 28010126\) volt, azaz átlagosan \(\displaystyle 28.010126\) lépés kellett, meglehetősen közel van ez az elméleti \(\displaystyle 28\)-hoz.

Erre nem érkezett megerõsítés. Arra gondoltam hogy az összes lépések száma = ( sum k. színben tett lépések száma ) / 2. Egy konkrét színben tett lépések pedig egy (1,n-1) -rõl indított p=1/2-es tönkremenésnek felelnek meg. Ez utóbbi várható értéke konkrét. Az összegük várható értéke meg a várható értékeik összege (még akkor is, ha ezek a tönkremenések csatolva vannak, és ha az egyik veszít, akkor egy másik szükségképpen nyer), tehát N*E/2 a lépések számának várható értéke, ahol az E a tönkremenéses játékból adódik, és, mivel ez konstans, független a stratégiától?

Jó ez (valahol)? Vagy teljesen hibás? (néztem a Róbert Gida megoldását a másik témában, de én egy bizonyos szint fölé nem megyek, az pedig erõsen fölötte van. Ha nem jó, akkor keresgélek még olyan "megoldást" amit én is értek, hátha van. (a feladat többi részeiben számolni kell))

Az merült fel bennem, hogy vajon egy lovat is meg tudnánk így állítani? Az is 8 helyre léphet egyszerre, persze nem lehet elé trivi módon falat emelni.

> "(b) Bizonyítsd be, hogy attól függetlenül, hogy milyen stratégiával játszol, a lépések számának a várható értéke azonos. (Vigyázz, ez nem középiskolás feladat, mert elemi módszerrel nagyon nehéz megoldani.)"

A zöld színben tett lépések várható értéke (ahol egyik kaméleon zöld) nem függ a stratégiától, a kék színben tett lépések száma sem, tehát az összegük sem?

Amikor a (legfeljebb) nyolc elérhető szomszédos mezőre léphet a rabló (illetve nálatok az angyal).

pontosan melyik változatot mondtad el a táblánál?

Így van. Pataki János ezt a feladatot rendőrrel-rablóval mondta el. k=1-re még a táblánál mondtam el a megoldást, sőt k=2-re is feladta, ami akkor ezek szerint még megoldatlan probléma volt!

Köszi, ez pont az :) És nem csak a herceg, de a király se tud elmenekülni.

Az ehhez hasonló feladatoknak neve van, lásd Angels and Devils game. A konkrét esetben azt hiszem, hogy a herceget be lehet zárni.

Van egy feladatom, nem tudom rá egyelőre megoldást.

4. feladat: Vegyünk két új sakkbábút: a Herceget, ami vízszintesen vagy függőlegesen tud egyet lépni, és a Pajzsot, ami nem tud lépni egyáltalán, de megakadályozza az ellenfelet, hogy elfoglalja a Pajzs által védett mezőt (nem üthető).

A kérdés az, hogy ha egy végtelen sakktáblán, amin kezdetben egyetlen Herceg van, felváltva lép a Herceg, majd felkerül egy új, ellentétes színű Pajzs egy addig üres mezőre, akkor véges sok lépés alatt a Pajzsok be tudják-e keríteni a Herceget. És ha igen a válasz, akkor tudunk-e körülbelüli lépésszámot mondani, ami biztosan elég.

A sorszám véletlenszerű. Az “Érdekes matekfeladatok” téma alatt már rég nagyon megkeveredtek a sorszámok, úgyhogy nem akartam az egymás utáni sorszámokat folytatni. Ha viszont véletlenszerű sorszámot választok, akkor az nem esik egybe egyik korábbi sorszámmal sem, és utólag könnyen keresni is lehet rá.

A feladat sorszáma kapcsolódik, vagy pedig random?

Ez jogos kérdés, de sokat nem tudok róla.

Az előbbi érvelés szerint minden stratégia egyforma, a te tíz kártyád és az osztó tíz kártyája között minden permutáció egyforma eséllyel fordul elő. Azt is tudjuk, hogy ugyanannyi a nyert és vesztett játék esélye, ezért elég a döntetlen esélyét megtudni.

Tíz kártyára még egyszerűen végigpróbálhatjuk mind a &tex;\displaystyle 10! = 3628800 &xet; permutációt, és följegyezhetjük a döntetlenek számát. (Tizenhat kártyára már érdemes lenne okosabb módszert keresni, és azt tippelem, van faktoriális helyett csak exponenciális időt igénylő megoldás, de tíz kártyára nem éri meg vacakolni ilyesmivel.) Az jön ki, hogy a 3628800 permutációból 985730-nél döntetlen az eredmény. Ez azt jelenti, hogy a játékok 36.4%-a nyerő, 27.2%-a döntetlen, és 36.4%-a vesztő.

Ha már kiszámoltad ugyanezt, akár kevesebb kártyára is, akkor könnyen megtalálhatod a megfelelő sorozatot az OEIS-ben. Az A062868 adja meg a döntetlen permutációk számát akárhány kártyára. Láthatod, hogy a leírás pont erre a játékra vonatkozik. Az is kiderül, hogy senki nem számolta ki a sorozatot 18-nál több kártyára, tehát az OEIS nem ismer hatékony módszert a pontos szám kiszámítására sok kártya esetén. Ez nem jelenti azt, hogy nincs is hatékony módszer. Épp ellenkezőleg, én azt gondolom, hogy van olyan módszer, amivel 30 különböző értékű kártyára is kaphatunk megoldást kivárható időben, csak még senki nem volt elég szorgalmas, hogy implementálja, ellenőrizze, és felrakja az OEIS-re. Persze körülbelüli számot könnyű mondani jóval több kártyára is, hiszen csak le kell játszanod sok véletlenszerű játékot.

Nekem nem meggyőző a magyarázat, de én is úgy érzem nem lehet, se nyerő,se vesztő stratégiát kitalálni. Adódik viszont egy feladat: A játékok hány százaléka nyerő,vesztő,döntetlen?

Róbert Gidának igaza van. Teljesen mindegy, hogy mit csinálsz, a játék mindenképpen ugyanúgy működik. Hadd próbáljak meg egy szemléletes megoldást mondani.

Képzeld el, hogy a játékot a következőképpen játszod. Nem a kezedben tartod a tíz lapot, hanem magad elé lerakod az asztalra sorba rendezve, fejjel lefelé, de így is tudod, hogy melyik lapnak mi az értéke. Minden körben az előtted fekvő tíz lap valamelyikét fordítod föl, így hívsz. Az osztó azt csinálja, hogy a játék elején megkeveri a kártyáit, majd pedig a tíz kártyát megkeverve leosztja fejjel lefelé a te kártyáid elé. Miután te hívsz egy lapot, ő azt a lapot fordítja föl, amelyik az általad hívott lap előtt van.

A játéknak ebben a változatában osztó nem a paklija tetejéről hív, de az eredmény ugyanolyan véletlenszerű: mindkét esetben amikor az osztó felfordítja a lapot, az a korábbi eseményektől függetlenül egyforma eséllyel kerül ki az osztó maradék lapjai közül, hiszen ő jól megkeverte a pakliját. Ez a változat tehát az eredmény tekintetében egyformán viselkedik az eredetivel.

Másképpen nézve viszont ebben a változatban a játék eredménye már akkor eldőlt, amikor az osztó lerakta a lapokat az asztalra, a hívások már semmin sem változtatnak. (Ezt a változatot akár egy kaparós sorsjegyen is lehetne játszani.) Valóban, le van rakva a tíz pár lap, ami a tíz ütést fogja adni, csak a sorrendjüket döntöd el, de a sorrend már nem befolyásolja az elvitt ütések számát. Ezért aztán az eredeti játékra is igaz az, hogy a stratégiád nem változtat semmin, a várható eredmény minden stratégiánál ugyanannyi.

Azt már könnyű látni, hogy ez a várható nyeremény nulla. Valóban, ha az a stratégiád, hogy te is véletlenszerűen választasz a lapjaid közül minden hívásnál, akkor a játék teljesen szimmetrikus közted és az osztó között, ezért olyankor a nyeremény várhatóan nulla.

-----

Érdemes lehet összehasonlítani ezt a feladatot a kaméleonos feladattal. Azt már föladtam ezen a fórumon két éve, de inkább elmondom most újra érthetőbben.

Kaméleonos feladat. Egy játékgyár színváltós játék-kaméleonokat árul. A kaméleonok rengeteg különböző színűek: a gyárból minden kaméleon a többitől eltérő egyedi színben kerül ki.

Ezek a játék-kaméleonok azzal a csodás tulajdonsággal rendelkeznek, hogy ha két különböző színű kaméleont összeérintesz, akkor közülük az egyik fölveszi a másik színét, míg a másiknak a színe nem változik, így utána a két kaméleon egyforma színű lesz. Csakhogy az összeérintés előtt sehogyan nem tudod befolyásolni vagy megjósolni, hogy a két kaméleon közül melyiknek fog megváltozni a színe: a korábbi eseményektől függetlenül 1/2 esély van az egyik kaméleonra, a maradék 1/2 a másikra.

A következő játékot játszod. Induláskor van &tex;\displaystyle n &xet; játék-kaméleonod, amiket most bontottál ki a csomagolásból, tehát páronként különböző színű. Itt &tex;\displaystyle n &xet; egy természetes szám, &tex;\displaystyle 4 \le n &xet;. A játék minden lépésében kiválasztasz két különböző színű kaméleont, és összeérinted őket. A játék véget ér, ha már mind az &tex;\displaystyle n &xet; kaméleon azonos színű, mert ekkor nem tudsz többet lépni.

Négy részfeladat van.

(a) Bizonyítsd be, hogy bármilyen ügyesen is játszol, a lépések számának a várható értéke véges. (A játékgyár ügyes: a játék nem játszható örökké, csak akkor, ha újabb kaméleonokat veszel.)

(b) Bizonyítsd be, hogy attól függetlenül, hogy milyen stratégiával játszol, a lépések számának a várható értéke azonos. (Vigyázz, ez nem középiskolás feladat, mert elemi módszerrel nagyon nehéz megoldani.)

(d) Lásd be viszont, hogy a lépések számának az eloszlása nem mindenképpen azonos, hanem függ attól, hogy milyen stratégiával játszol. (A kaméleonos tehát jobb játék, mint az előbbi kártyajáték, mert míg az előzőben a döntéseidnek igazából semmilyen jelentősége nincs, a kaméleonokkal többféleképpen is lehet játszani.)

(c) Mennyi a lépések számának várható értéke pontosan? (Ez a részfeladat mutatja meg, miért olyan ügyes a játékgyár. Minden egyes újabb kaméleon több játékélményt ad, mint az előzőek bármelyike, ezért mindig érdemes még egy kaméleont vásárolni a készletedhez azért, mert ugyanannyi pénzért most többet játszhatsz, mint bármikor máskor.)

Dehogynem, azt a lapot kell választanod, amelyre a legnagyobb a nyereményed várható értéke. De egy lap eldobása után már más feladatról van szó, ezért nem is tudsz indukciózni.

Időközben szerintem megvan a megoldás: legyen &tex;\displaystyle n-n&xet; (különböző) lap a két játékosnál, nem feltétlenül ugyanaz az &tex;\displaystyle n&xet; lap (tehát például nálam az &tex;\displaystyle 1,5&xet; ellenfélnél a &tex;\displaystyle 2,8&xet; lapok vannak). Def. az &tex;\displaystyle f&xet; fv-t úgy, hogy &tex;\displaystyle f(t)=p&xet;, ha nálam &tex;\displaystyle t&xet;, az ellenfélnél pedig volt egy &tex;\displaystyle p&xet; értékű lap, és a &tex;\displaystyle t&xet; lapomra az ellenfél lapja &tex;\displaystyle p&xet; volt. Ekkor azt állítom, hogy mind az &tex;\displaystyle n!&xet; különböző fv-nek ugyanannyi a valószínűsége tetszőleges stratégia esetén!

Ez &tex;\displaystyle n=1&xet;-re trivi, egyébként indukció, legyen &tex;\displaystyle p_i&xet; annak a valsószínűsége, hogy az elsőnek eldobott lapom az &tex;\displaystyle i&xet;-edik. Rögzítsünk egy tetsz. f fv-t, ha az első eldobott lapom az &tex;\displaystyle i&xet;-edik és azon &tex;\displaystyle t&xet; szerepel, az ellenfél paklijának felső lapján &tex;\displaystyle p&xet; szerepel, akkor &tex;\displaystyle \frac 1n&xet; valószínűséggel &tex;\displaystyle f(t)=p&xet;, és indukciózhatunk: &tex;\displaystyle \frac {1}{(n-1)!}&xet; valószínűséggel a maradék &tex;\displaystyle (n-1)&xet; helyen megkapom &tex;\displaystyle f&xet;-et, így &tex;\displaystyle \sum_{i=1}^n c_i\frac{1}{n}\frac{1}{(n-1)!}=\frac{1}{n!}\sum_{i=1}^n c_i=\frac{1}{n!}&xet; a valószínűsége &tex;\displaystyle f&xet;-nek.

Az a meglepő, hogy sehol nem használtuk, hogy ez konkrétan milyen játék, azaz tetsz. játéknál a várható nyereményem megegyezik annak a stratégiának a nyereményével amikor véletlenül dobom a lapokat, azaz ugyanúgy, mint az ellenfelem. Tehát egy szimmetrikus kifizetési fv. esetén ez a várható nyeremény is nulla lesz.

Olyasmire gondolsz, hogy az első kör után a maradékot nem a legnagyobb várható értékű stratégiával játszom tovább, hanem egy olyannal, amelyik biztosabbra megy?

Kösz, akkor nézegetem még egy picit.