  The ad hoc coordination problem is to design an autonomous agent which is
able to achieve optimal flexibility and efficiency in a multiagent system with
no mechanisms for prior coordination. We conceptualise this problem formally
using a game-theoretic model, called the stochastic Bayesian game, in which the
behaviour of a player is determined by its private information, or type. Based
on this model, we derive a solution, called Harsanyi-Bellman Ad Hoc
Coordination (HBA), which utilises the concept of Bayesian Nash equilibrium in
a planning procedure to find optimal actions in the sense of Bellman optimal
control. We evaluate HBA in a multiagent logistics domain called level-based
foraging, showing that it achieves higher flexibility and efficiency than
several alternative algorithms. We also report on a human-machine experiment at
a public science exhibition in which the human participants played repeated
Prisoner's Dilemma and Rock-Paper-Scissors against HBA and alternative
algorithms, showing that HBA achieves equal efficiency and a significantly
higher welfare and winning rate.
