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