--- _id: '2163' abstract: - lang: eng text: We consider multi-player graph games with partial-observation and parity objective. While the decision problem for three-player games with a coalition of the first and second players against the third player is undecidable in general, we present a decidability result for partial-observation games where the first and third player are in a coalition against the second player, thus where the second player is adversarial but weaker due to partial-observation. We establish tight complexity bounds in the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness for parity objectives. The symmetric case of player 1 more informed than player 2 is much more complicated, and we show that already in the case where player 1 has perfect observation, memory of size non-elementary is necessary in general for reachability objectives, and the problem is decidable for safety and reachability objectives. From our results we derive new complexity results for partial-observation stochastic games. acknowledgement: "This research was partly supported by European project Cassting (FP7-601148).\r\nTechnical Report under https://research-explorer.app.ist.ac.at/record/5418\r\n" alternative_title: - LNCS author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Laurent full_name: Doyen, Laurent last_name: Doyen citation: ama: 'Chatterjee K, Doyen L. Games with a weak adversary. In: Lecture Notes in Computer Science. Vol 8573. Springer; 2014:110-121. doi:10.1007/978-3-662-43951-7_10' apa: 'Chatterjee, K., & Doyen, L. (2014). Games with a weak adversary. In Lecture Notes in Computer Science (Vol. 8573, pp. 110–121). Copenhagen, Denmark: Springer. https://doi.org/10.1007/978-3-662-43951-7_10' chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” In Lecture Notes in Computer Science, 8573:110–21. Springer, 2014. https://doi.org/10.1007/978-3-662-43951-7_10. ieee: K. Chatterjee and L. Doyen, “Games with a weak adversary,” in Lecture Notes in Computer Science, Copenhagen, Denmark, 2014, vol. 8573, no. Part 2, pp. 110–121. ista: 'Chatterjee K, Doyen L. 2014. Games with a weak adversary. Lecture Notes in Computer Science. ICALP: Automata, Languages and Programming, LNCS, vol. 8573, 110–121.' mla: Chatterjee, Krishnendu, and Laurent Doyen. “Games with a Weak Adversary.” Lecture Notes in Computer Science, vol. 8573, no. Part 2, Springer, 2014, pp. 110–21, doi:10.1007/978-3-662-43951-7_10. short: K. Chatterjee, L. Doyen, in:, Lecture Notes in Computer Science, Springer, 2014, pp. 110–121. conference: end_date: 2014-07-11 location: Copenhagen, Denmark name: 'ICALP: Automata, Languages and Programming' start_date: 2014-07-08 date_created: 2018-12-11T11:56:04Z date_published: 2014-01-01T00:00:00Z date_updated: 2023-02-23T12:25:29Z day: '01' department: - _id: KrCh doi: 10.1007/978-3-662-43951-7_10 ec_funded: 1 external_id: arxiv: - '1404.5453' intvolume: ' 8573' issue: Part 2 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1404.5453 month: '01' oa: 1 oa_version: Preprint page: 110 - 121 project: - _id: 2584A770-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: P 23499-N23 name: Modern Graph Algorithmic Techniques in Formal Verification - _id: 25863FF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S11407 name: Game Theory - _id: 2581B60A-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '279307' name: 'Quantitative Graph Games: Theory and Applications' - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: Lecture Notes in Computer Science publication_status: published publisher: Springer publist_id: '4821' quality_controlled: '1' related_material: record: - id: '5418' relation: earlier_version status: public status: public title: Games with a weak adversary type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 8573 year: '2014' ...