Reachability Games and Friends - Thomas Brihaye

Patricia Bouyer

He is from Belgium. Which is a small country in Europe.

Thomas Brihaye

When Patricia told me about the talk I had 3 challenges

• First was that I need to prepare a talk which was understandable for students
• second I wanted to make a talk where my colleagues would not get bored, So i had to talk about things from a perspective that they might not have explored
• Third, and probably the most difficult challenge was that I had to prepare a talk that I would understand myself

• Train travel
  • there path from penzance to cambridge that goes through oxford, so If I want a path, then I would have to back track, so memory is important!
  • Homo oeconomicus
  • Types
    • Optimisitc
    • Pessimistic
    • Rational - Homo oeconomicus
    • Stochastic
• Focus of the talk - Memory and Complexity

• Strategy

  > A strategy is the next move given a previous set of moves

  • If memory is finite it can be encoded in a finite state automata
  • sequential memory is required for generalized reachability problem
  • memory is classified by the size of mealy machine that encodes it
• Complexity
  • SAT can be encoded linearly in terms of the size of formula
• Memoryless strategies suffice for reachability in Zero-Sum Games
• Generalized Reachability is P-SPACE complete and requires branching memories.