Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

    Belépés
    címtáras azonosítással
    vissza a tantárgylistához   nyomtatható verzió    

    Algoritmikus játékelmélet

    A tantárgy angol neve: Algorithmic Game Theory

    Adatlap utolsó módosítása: 2024. január 3.

    Budapesti Műszaki és Gazdaságtudományi Egyetem
    Villamosmérnöki és Informatikai Kar

    Mérnökinformatikus, BSc

    Információs rendszerek specializáció, SZIT ágazat főtárgy 

     
    Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
    VISZAC01 5 2/2/0/v 5  
    3. A tantárgyfelelős személy és tanszék Dr. Fleiner Tamás,
    A tantárgy tanszéki weboldala www.cs.bme.hu/alje
    4. A tantárgy előadója dr. Fleiner Tamás, egyetemi tanár, SZIT
    5. A tantárgy az alábbi témakörök ismeretére épít Kombinatorika, gráfelmélet 
    6. Előtanulmányi rend
    Ajánlott:
    Bevezetés a számításelméletbe 2 sikeres vizsga vagy Kombinatorika és gráfelmélet 1. sikeres vizsga
    7. A tantárgy célkitűzése A kurzus célja, hogy a hallgatók megismerkedjenek néhány olyan játékelméleti fogalommal és ezekhez kapcsolódó algoritmussal, amit nem csupán a mérnöki munka során lehet közvetlenül felhasználni, de mindezen ismeretekből olyan szemléletmód is fakad, ami bizonyos mérnöki problémák átfogóbb megközelítését teszi lehetővé. 
    8. A tantárgy részletes tematikája

    1. 1. Kombinatorikus játékok definíciója, éles játék, betli játék, játék magja. Nyerő stratégia létezése, stratégialopás. Játékok összege, nim játék, Grundy-számok, Sprague-Grundy-tétel. Pozíciós játékok, Erdős-Selfridge-tétel. 

    1. 2. Stratégiai játékok, normál forma, kifizetés mátrix, stratégia, játékosok racionalitása. Nevezetes stratégia játékok: fogolydilemma, nemek harca, gyáva nyúl, azonos érmék. Domináns stratégiák, iterált eliminálás, tiszta- és kevert Nash-egyensúly. Neumann tétele kétszemélyes 0-összegű játékokra. 

    1. 3. Közlekedési játékok, Braess-paradoxon. Az anarchia ára az atomos és a nem atomos modellben.  Mechanizmustervezési problémák  

    1. 4. Folytonos osztozkodási játékok, arányos és irígységmentes eljárások: Fink módszere, a Dubins-Spanier-féle mozgó késes és az Even-Paz eljárás, Simmons és Su tétele, Selfridge és Conway algortimusa. Irígységmentes lakbérelosztás. 

    1. 5. Elosztási probléma, elosztási szabályok tulajdonságai, nevezetes elosztási eljárások: arányos, egyenletes nyereség, egyenletes veszteség, talmudi szabály. 

    1. 6. Szavazási mechanizmusok, többségi szavazás taktikai manipulálhatósága, Borda-pontozás, Condorcet-győztes, Arrow tétele és a Gibbard-Satterthwaite-tétel. 

    1. 7. Árverési mechanizmusok: legmagasabb áras és Vickrey-árverés, igazmondásra ösztönző (taktikázásbiztos) tulajdonság, VCG-mechanizmus, fordított, angol, és hátizsák árverés. 

    1. 8. Újraosztási feladatok, a felső körcsere (TTC) eljárás, a kapott megoldás tulajdonságai, Pareto-optimális megoldás keresése. 

    1. 9. Kifizetéses kooperatív játékok, mag, kernel, Shapley-érték, nukleólusz, a Shapley-Shubik és a Banzhaf-féle hatalmi indexek. 

    A gyakorlatokon az előadáson elhangzott elméletet felhasználó feladatokat oldunk meg, erősen ösztönözve a hallgatók aktív részvételét akár egyéni, akár csoportos munkában. 
     
    9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium)

    A tárgyból hetente 2 óra előadás és 2 óra kiscsoportos gyakorlat van. 

    Az előadásokon az új elmélet kerül bemutatásra, ennek gyakorlása és feladatok megoldásában történő alkalmazása zajlik a gyakorlatokon. A gyakorlatok mindig szorosan kapcsolódnak a megfelelő előadás anyagához, ezért azokon az előadáson tanult anyag ismerete elvárás a hallgatóktól. Az előadásokon tárgyalt fogalmak és ismeretek begyakorlása, elmélyítése a gyakorlatokon zajlik, az itt zajló munka a tanulási folyamat alapvető fontosságú része. Az előadások a legtöbb esetben szorosan épülnek a korábbi hetek anyagára, ezek ismerete nélkül az új anyag általában nem követhető. 

    10. Követelmények

    Szorgalmi időszakban:

    A félév folyamán egy zárthelyit íratunk. A félévvégi aláírás megszerzésének (vagyis a vizsgára bocsátásnak) feltétele a zárthelyin elért legalább 40%-os teljesítmény. 

    Azok a hallgatók, akik egy korábbi félévből érvényes aláírással rendelkeznek, megkísérelhetik újból megírni a zárthelyit, hogy a korábbi zárthelyik eredményein javítsanak. Erre az esetre az alábbi feltételek vonatkoznak: 

    • Ha sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor a vizsgajegybe (lásd lentebb) az így kapott eredmény számít bele (akkor is, ha ez rosszabb). 

    • Ha nem sikerül újra teljesíteni az aláíráshoz szükséges feltételeket, akkor az aláírás nem vész el, de a vizsgajegybe csak az aláírás megszerzéséhez szükséges minimális pontszámot számítjuk be. 

    Ha egy érvényes aláírással rendelkező hallgató az aktuális félévben legalább egy zárthelyin megjelenik, azt úgy tekintjük, hogy az illető kísérletet tett az aláírás feltételeinek újbóli teljesítésére (és rá a fenti feltételek vonatkoznak). Ellenkező esetben a legutolsó olyan félévbeli teljesítményt vesszük figyelembe, amikor a hallgató megkísérelte az aláírás feltételeinek teljesítését. 


    Vizsgaidőszakban: 

    Vizsgára az jelentkezhet, aki érvényes aláírással rendelkezik.  

    A vizsga ebből a tárgyból szóbeli. 

    A vizsgajegyet a zárthelyi eredményéből és a vizsgán nyújtott szóbeli teljesítményből alakítjuk ki olyan módon, hogy abba a zárthelyi 2 súllyal, a szóbeli vizsga pedig 3 súllyal számít bele. Ha a szóbeli vizsga elégtelen, akkor a vizsgajegy is elégtelen (függetlenül a zárthelyi eredményétől). Ismétlő vizsga esetén a zárthelyikből származó eredmények változatlanul érvényesek. 

    A végső osztályzatot a vizsgán szerzett (legfeljebb 60) és a ZH-n kapott (legfeljebb 40) pont összegéből képezzük az alábbiak szerint. 

     0-39: elégtelen, 40-54: elégséges, 55-69: közepes, 70-84: jó, 85-100: jeles. 

    A tárgyhoz tartozó vizsgatételsor félévről félévre változik, az aktuális félévre érvényes vizsgatételsor a tárgy tanszéki weboldaláról tölthető le a szorgalmi időszak utolsó hetétől. 

     

    11. Pótlási lehetőségek

    A zárthelyihez biztosítunk egy pótlási alkalmat (a szorgalmi időszakban vagy a pótlási héten). Ezt fel lehet használni a zárthelyi dolgozat pótlására vagy az eredményének a javítására. Az utóbbi esetben mindenképpen az új pontszám lesz érvényes, akkor is, ha az rosszabb, mint az eredeti. Ez alól egy kivétel van: a már megszerzett aláírást és az adott zárthelyin a megszerzéséhez tartozó minimális pontszámot egy balsikerű javítási kísérlettel nem lehet elveszíteni. Ha valaki egy pótzárthelyin megjelenik (és a feladatsort átveszi), azt úgy tekintjük, hogy az illető kísérletet tett a dolgozat megírására (és így rá a fenti feltételek vonatkoznak). 

     

    A szóbeli vizsga javítása ill. pótlása a hatályos TVSZ-ben előírtak szerint történik. 

    12. Konzultációs lehetőségek A zárthelyi és a vizsgák előtt konzultációs lehetőséget biztosítunk. 
    13. Jegyzet, tankönyv, felhasználható irodalom

    Végh László, Király Tamás, Pap Júlia: Játékelmélet jegyzet http://tkiraly.web.elte.hu/students/jatekelmelet_jegyzet.pdf

    Tasnádi Attila: Igazságos elosztások 

    http://unipub.lib.uni-corvinus.hu/2436/1/Tasnadi_Igazsagos_elosztasok.pdf

    Nisan, Roughgarden, Tardos, Vazirani: Algorithmic Game Theory 

    14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
    Kontakt óra56
    Félévközi készülés órákra25
    Felkészülés zárthelyire16
    Házi feladat elkészítése5
    Kijelölt írásos tananyag elsajátítása
    Vizsgafelkészülés48
    Összesen150
    15. A tantárgy tematikáját kidolgozta dr. Fleiner Tamás, egyetemi tanár, SZIT 
    IMSc tematika és módszer IMSC pontokat a hatékonyabb tanulásért és az anyag magasabb szintű, mélyebb elsajátításáért kapják a hallgatók. 
    IMSc pontozás

    A ZH-n szerepel egy IMSC feladat, ami a ZH eredményébe nem számít, de legfeljebb 15 IMSC pont szerezhető a megoldásával. A ZH-n így megszerzett IMSC pontszámot akkor jár, ha a hallgatónak a kurzuson kapott végső osztályzata jeles.  

    A szóbeli vizsgán a hallgató tudását egy 0 és 75 közötti pontszámmal értékeljük. A 60 feletti pontszámot IMSC pontként írjuk jóvá (azzal, hogy a tárgyból legfeljebb 25 IMSC pont szerezhető).