Research map / Multi-agent systems and games / Games and equilibria
Sequential Decision Making in Stochastic Games with Incomplete Preferences over Temporal Objectives
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Synthesizes non-dominated almost-sure winning strategies for two-player stochastic games on graphs where players have opposing incomplete preferences over LTLf temporal goals, using a rank metric on a product game and showing such strategy profiles are Nash equilibria.
Problem
Strategy synthesis in two-player stochastic games on graphs where players hold adversarial, possibly incomplete (combinative) preferences over LTLf temporal goals, which utility-based approaches cannot handle.
Approach
Introduces the non-dominated almost-sure winning (NDASWin) solution concept and a scalar integer 'rank' derived from the undominance principle on the product game of the stochastic game and preference automata; NDASWin strategies minimize maximum rank via iterated almost-sure winning computations and form Nash equilibria.
Key results
- Proposes a rank metric such that NDASWin strategies can be synthesized by iterating almost-sure winning computations (Algorithm 1), with quadratic complexity in game size and linear in maximum rank.
- Proves that every strategy profile consisting of NDASWin strategies is a Nash equilibrium in the product game under risk-averse worst-case evaluation.
- In a 5x5 drone delivery example, the paper identifies the starting cells for drone A that achieve rank 0 against any drone B strategy, while cells where B can block all pickups have rank 3.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Start at a cell with rank 0 instead of one of the cited rank 3 cells | Drone A using an NDASWin strategy · Drone delivery gridworld | rank: 3 -> 0 | Helped |
Surprising findings
- Treating incomparability as indifference can exclude meaningful Nash equilibria, motivating the incomplete-preference treatment.
Limitations
- Rank is a scalar that does not capture the full complexity of incomplete preferences; multi-utility representation is not replaced.
- Results are qualitative (almost-sure) and restricted to proper strategies over finite traces.
- Evaluation is a single small illustrative drone delivery gridworld example.
Experimental setup
Benchmarks: drone delivery gridworld (5x5 stochastic gridworld)
Metrics: rank achievable by drone A under NDASWin strategy
Builds on: almost-sure winning in stochastic games LTLf preference automata (preference LTLf) undominance principle
Closest papers by meaning
- A Minimaximalist Approach to Reinforcement Learning from Human Feedback (ICML 2024 · similarity 0.89)
- Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning (ICML 2025 · similarity 0.88)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.87)
- Robust Nash Alignment under Preference Uncertainty (NeurIPS 2026 · similarity 0.87)
- Regret Minimization in Stackelberg Games with Side Information (NeurIPS 2024 · similarity 0.87)
- Adversarial Policy Optimization for Offline Preference-based Reinforcement Learning (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.