Emergence of Gricean Maxims from Multi-Agent Decision Theory

Proceedings of NAACL-HLT 2013, pages 1072–1081, Atlanta, Georgia, 9–14 June 2013. c⃝2013 Association for Computational Linguistics Emergence of Gricean Maxims from Multi-Agent Decision Theory Adam Vogel, Max Bodoia, Christopher Potts, and Dan Jurafsky Stanford University Stanford, CA, USA {acvogel,mbodoia,cgpotts,jurafsky}@stanford.edu Abstract Grice characterized communication in terms of the cooperative principle, which enjoins speakers to make only contributions that serve the evolving conversational goals. We show that the cooperative principle and the associ- ated maxims of relevance, quality, and quan- tity emerge from multi-agent decision theory. We utilize the Decentralized Partially Observ- able Markov Decision Process (Dec-POMDP) model of multi-agent decision making which relies only on basic definitions of rationality and the ability of agents to reason about each other’s beliefs in maximizing joint utility. Our model uses cognitively-inspired heuristics to simplify the otherwise intractable task of rea- soning jointly about actions, the environment, and the nested beliefs of other actors. Our experiments on a cooperative language task show that reasoning about others’ belief states, and the resulting emergent Gricean commu- nicative behavior, leads to significantly im- proved task performance. 1 Introduction Grice (1975) famously characterized communica- tion among rational agents in terms of an overarch- ing cooperative principle and a set of more specific maxims, which enjoin speakers to make contribu- tions that are truthful, informative, relevant, clear, and concise. Since then, there have been many at- tempts to derive the maxims (or perhaps just their ef- fects) from more basic cognitive principles concern- ing how people make decisions, formulate plans, and collaborate to achieve goals. This research traces to early work by Lewis (1969) on signaling systems. It has recently been the subject of ex- tensive theoretical discussion (Clark, 1996; Merin, 1997; Blutner, 1998; Parikh, 2001; Beaver, 2002; van Rooy, 2003; Benz et al., 2005; Franke, 2009) and has been tested experimentally using one-step games in which the speaker produces a message and the hearer ventures a guess as to its intended refer- ent (Rosenberg and Cohen, 1964; Dale and Reiter, 1995; Golland et al., 2010; Stiller et al., 2011; Frank and Goodman, 2012; Krahmer and van Deemter, 2012; Degen and Franke, 2012; Rohde et al., 2012). To date, however, these theoretical models and ex- periments have not been extended to multi-step in- teractions extending over time and involving both language and action together, which leaves this work relatively disconnected from research on planning and goal-orientation in artificial agents (Perrault and Allen, 1980; Allen, 1991; Grosz and Sidner, 1986; Bratman, 1987; Hobbs et al., 1993; Allen et al., 2007; DeVault et al., 2005; Stone et al., 2007; DeVault, 2008). We attribute this in large part to the complexity of Gricean reasoning itself, which requires agents to model each other’s belief states. Tracking these as they evolve over time in re- sponse to experiences is extremely demanding. Our approach complements slot-filling dialog systems, where the focus is on managing speech recogni- tion uncertainty (Young et al., 2010; Thomson and Young, 2010). However, recent years have seen significant ad- vances in multi-agent …

Content truncated to 500 words