Synthesis with Combined Qualitative and Quantitative Objectives

37 concepts26 papers1 proposal

Traditional reactive synthesis operates in a binary world. A system either satisfies its specification or it does not. Using temporal logics or parity games, we can guarantee that an autonomous vehicle will never crash (safety) and will eventually reach its destination (liveness).

However, real-world systems must operate under physical and economic constraints. It is not enough for the vehicle to reach its destination; it must do so while minimizing fuel consumption or maximizing battery life. As Arjan van der Schaft points out in a foundational behavioral framework, managing the conjunction of these diverse qualitative and quantitative requirements within a unified mathematical structure remains a core challenge in control theory and formal methods.

To bridge this gap, modern reactive synthesis combines qualitative objectives (infinite-horizon logical conditions) with quantitative objectives (numerical performance metrics) into a single game-theoretic framework.

The Core Mechanism: Mean-Payoff Parity Games

The standard mathematical engine for combining these objectives is the Mean-Payoff Parity Game. In this graph-based game, two players (the system and the environment) move a token along the edges of a directed graph. To capture both logic and performance, every state or edge is assigned two distinct values:

  1. A qualitative priority (an integer): Used to define a parity condition. The system wins qualitatively if the maximum priority visited infinitely often is even. This models $\omega$-regular properties like liveness and safety.
  2. A quantitative weight (a numerical reward or cost): Used to calculate the long-term average reward over an infinite run (the mean-payoff).
[State s1: Priority 2, Weight +5] ---> [State s2: Priority 3, Weight -2]
       ^                                      |
       |______________________________________|

In Better Quality in Synthesis through Quantitative Objectives, Krishnendu Chatterjee et al. demonstrated that these two disparate dimensions can be optimized simultaneously. Instead of choosing between a safe-but-inefficient strategy or an efficient-but-dangerous one, we can synthesize controllers that maximize long-term average utility subject to satisfying the underlying parity specification.

The primary challenge is that the strategies required to satisfy a parity condition might conflict with those needed to optimize a mean-payoff. For a long time, solving these combined games was computationally expensive. However, Laure Daviaud et al. provided a major theoretical breakthrough in A pseudo-quasi-polynomial algorithm for solving mean-payoff parity games, showing that the interplay between priority-based task ordering and average resource consumption can be resolved much faster than previously thought.

Satisficing via Automata Intersection

We do not always need absolute mathematical optimization. Often, a system designer simply wants a guarantee that resource consumption will remain below a specific threshold—a concept known as satisficing.

Why does satisficing make the problem easier? As the authors demonstrate in On Satisficing in Quantitative Games, we can represent quantitative thresholds directly as finite automata. This allows us to "qualitativize" the quantitative constraint.

By transforming a numerical threshold (e.g., "average energy cost $\le K$") into an automaton, the synthesis problem reduces to a standard automata intersection. The system can directly compose the performance requirement with qualitative temporal logic goals (like LTL or parity conditions). This modularity allows the synthesis tool to treat safety and resource thresholds as conjuncts in a single, unified language.

This relationship between different resource models is deep. For instance, in Energy Parity Games, Laurent Doyen et al. proved a surprising polynomial equivalence between energy parity games (where a system must maintain a positive battery level at all times) and mean-payoff parity games. This equivalence means that algorithms designed to optimize long-term averages can be directly repurposed to guarantee absolute resource safety.

Managing Uncertainty and Strategic Agents

When we move from closed, deterministic graphs to open, real-world environments, we introduce two complications: probabilistic uncertainty and strategic multi-agent interactions.

Stochastic Environments

In a probabilistic setting, the environment behaves like a Markov Decision Process (MDP) or a stochastic game. Here, the synthesis problem becomes a balancing act between absolute guarantees and average-case performance. Nir Piterman maps this out in Combinations of Qualitative Winning for Stochastic Parity Games, showing how to design systems that achieve "sure winning" (probability 1) for critical safety constraints while maintaining "almost-sure winning" or high expected rewards for general performance goals.

To make this practical, Jan Kretinsky showed in LTL-Constrained Steady-State Policy Synthesis that by translating qualitative LTL specifications into Limit-Deterministic Büchi Automata (LDBAs), the combined problem of satisfying logic, frequency constraints, and average rewards can be reduced to a single, computationally efficient linear program.

Multi-Agent Rational Verification

In multi-player environments, such as those modeled by the verification tool PRISM-games (Taolue Chen 0001 et al.), we must assume that external agents act in their own self-interest. This is the domain of rational verification: ensuring a system property holds assuming all agents choose strategies that achieve their own goals (a Nash Equilibrium).

Qualitative LTL Goals Only  =======> Strategy space explodes (2EXPTIME-complete)
Mean-Payoff Utilities Only  =======> Solvable via Linear Programming (NP/PSPACE)

When agent goals are expressed purely in qualitative temporal logic, finding a Nash equilibrium is notoriously difficult (2EXPTIME-complete). However, shifting the modeling paradigm to quantitative utilities changes the underlying math.

As Michael J. Wooldridge et al. demonstrate in On the complexity of rational verification, modeling agent objectives as mean-payoff utilities replaces binary win/loss conditions with continuous, long-term average rewards. This mathematical shift allows verification tools to bypass complex temporal logic tracking and instead use systems of linear inequalities. By leveraging efficient linear programming solvers, the complexity of rational verification drops dramatically to NP-complete or PSPACE, making the automated synthesis of strategic, multi-agent systems computationally feasible.

Key Foundational Work

A behavioral framework for compositionality: linear systems, discrete event systems and hybrid systems (2004) — contributed 1 concept elements to this direction.
Generalized Parity Games (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_multi_objective_reactive_synthesis_b9fbb6cb,
  title = {multi-objective reactive synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-objective-reactive-synthesis/rdr_b9fbb6cb801d4ecb80ec85e92efc6332},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_multi_objective_reactive_synthesis_b9fbb6cb_v1,
  title = {multi-objective reactive synthesis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-objective-reactive-synthesis/rdr_b9fbb6cb801d4ecb80ec85e92efc6332/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake