People can communicate successfully with almost any signal. A nod, gesture or a look can, in context, successfully convey a message without any prior agreement between the sender and receiver. This talk describes experiments in which the astonishing flexibility of human communication is illustrated. For example, subtle changes in the communicative setup and cause people to spontaneously reverse the meaning of a simple signal, without any prior agreement. Successful communication seems to require that people must agree, somehow or other, the mapping between signals and message. How is this possible? We argue that communication, and joint action more generally, requires that such agreements are reached by a process of “virtual bargaining,” which is surprisingly sophisticated.