Objectives of coalitions are described using temporal logic.

Concurrent Game structures

is a finite non empty set of agents is a finite non empty set of states : finite set of actions is a labelling specifying a truth assignment for each state.

is the action manager. It means that for each pair (a,s), the agent a must have some action to do at the state s. set of agents that can be executed by the agent a from the state s transition function is undefined if there is some agent a such that , This is called joint action. It is a partial function.

Coalition joint action a joint strategy of the coalition

so we assume that at the same state, they do the same transitions.

Turn based CGS

At each state, there is atmost one agent that can perform more than one action. So at most one agent is deciding what to do, the action.

Strategic Ability

To express that a coalition of agents have a collective strategy to enforce some property and to reason on it.

ATL is a way to quantify over strategies by a coalition

ATL

coalition A has a collective strategy to enforce the temporal property

A collective strategy is a tuple of individual strategies.

We encode several modalities in one over here. This has a term —

In turn based CGS, we can push the negation of to inside and becomes

do we have history deterministic strategies? not required! only positional strategies suffice. so we only have finitely many strategies to brute force our way through.

variant semantics of ATL

  • plans instead of strategies
  • finite memory / memoryfull strategies ( not required for ATL, but ATL for example)
  • quanitify over strategies

strategic logic

We quantify over strategies. ( like monadic second order logic )

We are “internalising” the semantics of ATL, ATL

incomplete information in ATL

Some states cannot be distinguished by a player. For example for Agent