Elamur Research⌕
☰
home / papers / 2013 / Emergence of Gricean Maxims from Multi-Agent Decision Theory

Emergence of Gricean Maxims from Multi-Agent Decision Theory

Paper · 2013 · Adam Vogel, Max Bodoia, Christopher Potts et al.

Summary

Grice's cooperative principle and maxims (quality, relation, quantity, manner) are usually stated as norms. This paper asks whether they can instead arise from plain rational planning by agents that share a goal. The authors model two players of a simplified Cards game as a Dec-POMDP. The players must both reach the Ace of Spades in a maze while seeing only part of the board. Exact Dec-POMDP solving is NEXP-complete, so they add cognitively motivated approximations that reduce the problem to a single-agent POMDP, which existing solvers can handle. Spatial meanings come from annotated human transcripts of the Cards corpus and are grounded as distributions over board squares. ListenerBot only takes advice. DialogBot also tracks a summary of its partner's beliefs and can speak. Pairs of DialogBots succeed more often and use fewer moves. Their messages turn out truthful, relevant and informative without any rule enforcing this. This supports the view that pragmatic behaviour can be derived from decision theory rather than stipulated.

Key points

  • Data. The Cards corpus (Potts, 2012) has 1,266 human–human game transcripts.

    • 599 location statements are annotated as a domain plus a conjunction of semantic literals, for example BOARD(top ∧ right).
    • The board has 231 open squares.

  • State-space reduction. Each square is described by a 136-dimensional vector of how likely each distinct expression refers to it.

    • k-means clustering with k = 16 groups squares into semantically coherent regions.
    • Without this, positions of two players and a card would need over 12 million states.

  • Semantics classifiers. These are log-linear bag-of-words models, evaluated with 10-fold cross-validation on 577 utterances.

    • Full representation exactly right: 56.3%.
    • Domain correct: 89.3%.
    • Primitives: precision .861, recall .780, F1 .818.

  • Task results. On 500 random starting configurations (success means both agents reach the card within 50 moves):

    PairSuccessAverage moves
    LB & LB84.4%19.8
    LB & DB87.2%17.5
    DB & DB90.6%16.6

  • Four approximations make the problem solvable:

    • merging low-level states into meaningful regions;
    • tracking only an averaged summary of the partner's possible beliefs;
    • nesting beliefs only one level deep;
    • simplifying the model of the partner to cut uncertainty.

Interesting ideas

  • I1. Spatial words are grounded by counting where human speakers actually stood when using an expression, then smoothing the counts into a probability map; this turns vague words into checkable distributions.
  • I2. States are clustered by how people talk about them rather than by raw geometry, so the planner reasons over linguistically natural chunks and stays tractable.
  • I3. Gricean maxims are not coded as rules; they fall out of a shared reward plus modelling the partner's beliefs, and early lying policies get discarded because they lower utility.
  • I4. Evaluation crosses agent types (naive+naive, naive+belief-modelling, both modelling), so the gain from partner modelling shows up as a graded ablation rather than a single score.
  • I5. Generation picks a real corpus sentence carrying the desired semantics, avoiding a full generator while keeping output natural.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

  • I1 (world): Vague locatives and degree words could be compiled into graded regions or value distributions, rather than crisp predicates, in the world of the text.
  • I2 (world): Entity locations or states in a story could be bucketed by the descriptions the text uses, keeping the world model small and explainable.
  • I3 (frames): Implicature in crate prag could be justified by asking which utterance best serves a cooperative goal given the hearer's beliefs, yielding an explicit reason trace for each inference.
  • I4 (learn): Mova components could be tested in mixed pairs (with and without coreference or pragmatic reasoning) as built-in negative controls that measure each module's contribution.
  • I5 (back): A first text-from-graph path could retrieve attested sentences whose parsed frames match the target meaning, before full surface realisation is available.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Stanford UniversityStanford · United States310 works · 284,480 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

🧭 Topics 1Research subjects and languages the work is about.Implicature · 72 works

Cite

Cite as Adam Vogel, Max Bodoia, Christopher Potts and Daniel Jurafsky. 2013. Emergence of Gricean Maxims from Multi-Agent Decision Theory. Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{vogel2013emergence,
  title = {{Emergence of Gricean Maxims from Multi-Agent Decision Theory}},
  author = {Adam Vogel, Max Bodoia, Christopher Potts and Daniel Jurafsky},
  booktitle = {Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies},
  year = {2013},
  url = {https://aclanthology.org/N13-1127/}
}

References

42 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Carlos E. Alchourronón, Peter Gärdenfors, and David Makinson. 1985. On the logic of theory change: Partial meets contradiction and revision functions. Journal of Symbolic Logic, 50(2):510–530. find
  2. James F. Allen, Nathanael Chambers, George Ferguson, Lucian Galescu, Hyuckchul Jung, Mary Swift, and William Taysom. 2007. PLOW: A collaborative task learning agent. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, pages 1514–1519. AAAI Press, Vancouver, British Columbia, Canada. find
  3. James F. Allen. 1991. Reasoning About Plans. Morgan Kaufmann, San Francisco. find
  4. David Beaver. 2002. Pragmatics, and that’s an order. In David Barker-Plummer, David Beaver, Johan van Benthem, and Patrick Scotto di Luzio, editors, Logic, Language, and Visual Information, pages 192–215. CSLI, Stanford, CA. find
  5. Anton Benz, Gerhard Jäger, and Robert van Rooij, editors. 2005. Game Theory and Pragmatics. Palgrave McMillan, Basingstoke, Hampshire. find
  6. Daniel S. Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. 2002. The complexity of decentralized control of Markov decision processes. Mathematics of Operations Research, 27(4):819–840. ↗
  7. Reinhard Blutner. 1998. Lexical pragmatics. Journal of Semantics, 15(2):115–162. find
  8. Michael Bratman. 1987. Intentions, Plans, and Practical Reason. Harvard University Press. find
  9. Herbert H. Clark. 1996. Using Language. Cambridge University Press, Cambridge. find
  10. Robert Dale and Ehud Reiter. 1995. Computational interpretations of the Gricean maxims in the generation of referring expressions. Cognitive Science, 19(2):233–263. ↗
  11. Judith Degen and Michael Franke. 2012. Optimal reasoning about referential expressions. In Proceedings of SemDIAL 2012, Paris, September. find
  12. David DeVault, Natalia Kariaeva, Anubha Kothari, Iris Oved, and Matthew Stone. 2005. An information-state approach to collaborative reference. In Proceedings of the ACL Interactive Poster and Demonstration Sessions, pages 1–4, Ann Arbor, MI, June. Association for Computational Linguistics. find
  13. David DeVault. 2008. Contribution Tracking: Participating in Task-Oriented Dialogue under Uncertainty. Ph.D. thesis, Rutgers University, New Brunswick, NJ. ↗
  14. Eduardo Fermé and Sven Ove Hansson. 2011. AGM 25 years: Twenty-five years of research in belief change. Journal of Philosophical Logic, 40(2):295–331. find
  15. Michael C. Frank and Noah D. Goodman. 2012. Predicting pragmatic reasoning in language games. Science, 336(6084):998. ↗
  16. Michael Franke. 2009. Signal to Act: Game Theory in Pragmatics. ILLC Dissertation Series. Institute for Logic, Language and Computation, University of Amsterdam. find
  17. Peter Gärdenfors. 1988. Knowledge in Flux: Modeling the Dynamics of Epistemic States. MIT Press. find
  18. Piotr J. Gmytrasiewicz and Prashant Doshi. 2005. A framework for sequential planning in multi-agent settings. Journal of Artificial Intelligence Research, 24:24–49. ↗
  19. Dave Golland, Percy Liang, and Dan Klein. 2010. A game-theoretic approach to generating spatial descriptions. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 410–419, Cambridge, MA, October. ACL. find
  20. Noah D. Goodman and Andreas Stuhlmüller. 2012. Knowledge and implicature: Modeling language understanding as social cognition. In Proceedings of the Thirty-Fourth Annual Conference of the Cognitive Science Society. ↗
  21. H. Paul Grice. 1975. Logic and conversation. In Peter Cole and Jerry Morgan, editors, Syntax and Semantics, volume 3: Speech Acts, pages 43–58. Academic Press, New York. ↗
  22. Barbara J. Grosz and Candace L. Sidner. 1986. Attention, intentions, and the structure of discourse. Comput. Linguist., 12(3):175–204, July. ↗
  23. William G. Hayward and Michael J. Tarr. 1995. Spatial language and spatial representation. Cognition, 55:39–84. ↗
  24. Jerry Hobbs, Mark Stickel, Douglas Appelt, and Paul Martin. 1993. Interpretation as abduction. Artificial Intelligence, 63(1–2):69–142. find
  25. Emiel Krahmer and Kees van Deemter. 2012. Computational generation of referring expressions: A survey. Computational Linguistics, 38(1):173–218. ↗
  26. David Lewis. 1969. Convention. Harvard University Press, Cambridge, MA. Reprinted 2002 by Blackwell. find
  27. Michael L. Littman, Anthony R. Cassandra, and Leslie Pack Kaelbling. 1995. Learning policies for partially observable environments: Scaling up. In Armand Prieditis and Stuart J. Russell, editors, ICML, pages 362–370. Morgan Kaufmann. ↗
  28. Arthur Merin. 1997. If all our arguments had to be conclusive, there would be few of them. Arbeitspapiere SFB 340 101, University of Stuttgart, Stuttgart. find
  29. Christos Papadimitriou and John N. Tsitsiklis. 1987. The complexity of markov decision processes. Math. Oper. Res., 12(3):441–450, August. ↗
  30. Prashant Parikh. 2001. The Use of Language. CSLI, Stanford, CA. find
  31. C. Raymond Perrault and James F. Allen. 1980. A plan-based analysis of indirect speech acts. American Journal of Computational Linguistics, 6(3–4):167–182. ↗
  32. Christopher Potts. 2012. Goal-driven answers in the Cards dialogue corpus. In Nathan Arnett and Ryan Bennett, editors, Proceedings of the 30th West Coast Conference on Formal Linguistics, Somerville, MA. Cascadilla Press. find
  33. David V. Pynadath and Milind Tambe. 2002. The communicative multiagent team decision problem: Analyzing teamwork theories and models. Journal of Artificial Intelligence Research, 16:2002. ↗
  34. Hannah Rohde, Scott Seyfarth, Brady Clark, Gerhard Jäger, and Stefan Kaufmann. 2012. Communicating with cost-based implicature: A game-theoretic approach to ambiguity. In The 16th Workshop on the Semantics and Pragmatics of Dialogue, Paris, September. find
  35. Robert van Rooy. 2003. Questioning to resolve decision problems. Linguistics and Philosophy, 26(6):727– 763. find
  36. Seymour Rosenberg and Bertram D. Cohen. 1964. Speakers’ and listeners’ processes in a word communication task. Science, 145:1201–1203. ↗
  37. Matthijs T. J. Spaan and Nikos Vlassis. 2005. Perseus: Randomized point-based value iteration for POMDPs. Journal of Artificial Intelligence Research, 24(1):195– 220, August. ↗
  38. Matthijs T. J. Spaan, Frans A. Oliehoek, and Nikos Vlassis. 2008. Multiagent planning under uncertainty with stochastic communication delays. In In Proc. of the 18th Int. Conf. on Automated Planning and Scheduling, pages 338–345. find
  39. Alex Stiller, Noah D. Goodman, and Michael C. Frank. 2011. Ad-hoc scalar implicature in adults and children. In Proceedings of the 33rd Annual Meeting of the Cognitive Science Society, Boston, July. find
  40. Matthew Stone, Richmond Thomason, and David De-Vault. 2007. Enlightened update: A computational architecture for presupposition and other pragmatic phenomena. To appear in Donna K. Byron; Craige Roberts; and Scott Schwenter, Presupposition Accommodation. find
  41. Blaise Thomson and Steve Young. 2010. Bayesian update of dialogue state: A pomdp framework for spoken dialogue systems. Comput. Speech Lang., 24(4):562– 588, October. ↗
  42. Steve Young, Milica Gašić, Simon Keizer, François Mairesse, Jost Schatzmann, Blaise Thomson, and Kai Yu. 2010. The hidden information state model: A practical framework for pomdp-based spoken dialogue management. Comput. Speech Lang., 24(2):150–174, April. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/vogel-2013-emergence-gricean-maxims-multi-agent/