---
title: "Implicatures and Nested Beliefs in Approximate — Vogel 2013"
description: "Gricean implicatures require agents to reason about what others believe about their own beliefs."
authors: ["Adam Vogel", "Christopher Potts", "Dan Jurafsky"]
year: 2013
venue: "Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)"
source: "https://aclanthology.org/P13-2014/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/papers/vogel-2013-implicatures-nested-beliefs-approximate-decentralized/"
---
[Elamur Research](https://md.research.elamur.ai/) · [this page in HTML](https://research.elamur.ai/free/papers/vogel-2013-implicatures-nested-beliefs-approximate-decentralized/)

[home](https://md.research.elamur.ai/) / [papers](https://md.research.elamur.ai/free/papers/) / [2013](https://md.research.elamur.ai/free/papers/2013/) / Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs

# Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs

**Authors:** Adam Vogel, [Christopher Potts](https://md.research.elamur.ai/free/authors/christopher-potts/), [Dan Jurafsky](https://md.research.elamur.ai/free/authors/dan-jurafsky/) · **Year:** 2013 · **Venue:** Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/P13-2014/) · [PDF](https://aclanthology.org/P13-2014.pdf) · [OpenAlex](https://openalex.org/W2250281182)

**Citations:** 35 citations (openalex-snapshot · 2026-10-14) · [10](#cited-by) in our library, of the 140673 papers whose bibliographies we read

## Summary
Gricean implicatures require agents to reason about what others believe about their own beliefs. Such nested reasoning is hard to model computationally. Vogel, Potts and Jurafsky treat communication as a decision problem inside a Decentralized-POMDP (Dec-POMDP), in which two agents share a reward. Exact Dec-POMDP solving is NEXP complete, so they instead adopt the approximation from Vogel et al. (2013), which recasts the problem as a POMDP for a single agent. That method adds a copy of the world state to the state space for each level of belief nesting and folds the partner's possible observations into the transition model. They build listeners and speakers of increasing sophistication: literal, level-one, and level-two.

They test the approach in two settings. One is a classic three-referent reference game. The other is a simplified navigation task grounded in the Cards corpus. In both, pragmatically enriched readings such as scalar implicatures and mutual exclusivity arise naturally when agents optimize joint utility. No special pragmatic rules are needed. This links decision-theoretic planning with formal pragmatics and gives a route toward dialogue agents that act and talk together.

## Key points
- Agents assume their partner models one fewer level of belief. Policies are computed with Perseus, a point-based value iteration solver. A level-two listener L(S(L)) reasons over an S×S×S state space.
- In the reference game, the messages are 'moustache', 'glasses' and 'hat', and the referents are r1–r3.
  - Literally, only 'hat' is unambiguous.
  - The level-two listener learns that 'glasses' picks out r2 and 'moustache' picks out r1, which yields the full one-to-one mapping.
- The Cards corpus provides 1266 chat transcripts of a two-player maze game. The model uses nine spatial expressions, such as 'top', 'top right' and 'middle'. Each is represented as a vague distribution over grid cells.
- Literal meanings were estimated from every token containing a term, which removes the effects of pragmatic usage. Under the level-one listener L(S), meanings become much sharper. For example, the entropy of 'middle' falls from 7.16 to 2.35, and 'top' falls from 6.68 to 3.46.
- The corpus does not record interpretations, so direct evaluation was impossible. Instead, the predictions were compared with exact-match token distributions, which approximate speaker intent, and the two closely resembled each other. Sampling-based methods are proposed for deeper nesting.

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

Fields: [Linguistics & languages](https://md.research.elamur.ai/free/shelves/linguistics/)

Topics: [Implicature](https://md.research.elamur.ai/free/topics/implicature/)

## Cited by

Cited by

10 papers of our library cite it (of the 140673 whose bibliographies we read); 4 of them have a page here, 6 not yet.

- [Pragmatics in Language Grounding: Phenomena, Tasks, and Modeling Approaches](https://md.research.elamur.ai/free/papers/fried-2023-pragmatics-language-grounding-phenomena-tasks/)
- [Planning, Inference and Pragmatics in Sequential Language Games](https://md.research.elamur.ai/free/papers/khani-2018-planning-inference-pragmatics-sequential-language/)
- [The Pragmatics of Indirect Commands in Collaborative Discourse](https://md.research.elamur.ai/free/papers/lamm-2017-pragmatics-indirect-commands-collaborative-discourse/)
- [Colors in Context: A Pragmatic Neural Model for Grounded Language Understanding](https://md.research.elamur.ai/free/papers/monroe-2017-colors-context-pragmatic-neural-model/)

## Cite

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

```bibtex
@inproceedings{vogel2013implicatures,
  title = {{Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs}},
  author = {Vogel, Adam and Potts, Christopher and Jurafsky, Dan},
  booktitle = {Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)},
  year = {2013},
  url = {https://aclanthology.org/P13-2014/}
}
```

- [← previous Holistic Discourse Coherence Annotation for Noisy Essay Writing](https://md.research.elamur.ai/free/papers/burstein-2013-holistic-discourse-coherence-annotation-noisy/)
- [next → Implicitation of Discourse Connectives in (Machine) Translation](https://md.research.elamur.ai/free/papers/meyer-2013-implicitation-discourse-connectives-machine-translation/)
- [↑ back to papers of 2013](https://md.research.elamur.ai/free/papers/2013/)

## References

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

1. Leon Bergen, Noah D. Goodman, and Roger Levy. 2012. That’s what she (could have) said: How alternative utterances affect language use. In Proceedings of the Thirty-Fourth Annual Conference of the Cognitive Science Society. [find](https://scholar.google.com/scholar?q=Leon+Bergen%2C+Noah+D%2E+Goodman%2C+and+Roger+Levy%2E+2012%2E+That%E2%80%99s+what+she+%28could+have%29+said%3A+How+alternative+utterances+affect+language+use%2E+In+Proceedings+of+the+Thirty%2DFourth+Annual+Conference+of+the+Cogn)
2. 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. [↗](https://doi.org/10.1287/moor.27.4.819.297)
3. Colin F. Camerer, Teck-Hua Ho, and Juin-Kuan Chong. 2004. A cognitive hierarchy model of games. The Quarterly Journal of Economics, 119(3):861–898, August. [↗](https://doi.org/10.1162/0033553041502225)
4. Herbert H. Clark and Deanna Wilkes-Gibbs. 1986. Referring as a collaborative process. Cognition, 22(1):1–39. [↗](https://doi.org/10.1016/0010-0277(86)90010-7)
5. Eve V. Clark. 1987. The principle of contrast: A constraint on language acquisition. In Brian MacWhinney, editor, Mechanisms of Language Acquisition, pages 1–33. Erlbaum, Hillsdale, NJ. [find](https://scholar.google.com/scholar?q=Eve+V%2E+Clark%2E+1987%2E+The+principle+of+contrast%3A+A+constraint+on+language+acquisition%2E+In+Brian+MacWhinney%2C+editor%2C+Mechanisms+of+Language+Acquisition%2C+pages+1%E2%80%9333%2E+Erlbaum%2C+Hillsdale%2C+NJ%2E)
6. Robert Dale and Ehud Reiter. 1995. Computational interpretations of the Gricean maxims in the generation of referring expressions. Cognitive Science, 19(2):233–263. [↗](https://doi.org/10.1207/s15516709cog1902_3) [our card](https://md.research.elamur.ai/free/papers/dale-1995-computational-interpretations-gricean-maxims-generation/)
7. Judith Degen and Michael Franke. 2012. Optimal reasoning about referential expressions. In Proceedings of SemDIAL 2012, Paris, September. [find](https://scholar.google.com/scholar?q=Judith+Degen+and+Michael+Franke%2E+2012%2E+Optimal+reasoning+about+referential+expressions%2E+In+Proceedings+of+SemDIAL+2012%2C+Paris%2C+September%2E)
8. David DeVault and Matthew Stone. 2007. Managing ambiguities across utterances in dialogue. In Ron Artstein and Laure Vieu, editors, Proceedings of DECALOG 2007: Workshop on the Semantics and Pragmatics of Dialogue. [find](https://scholar.google.com/scholar?q=David+DeVault+and+Matthew+Stone%2E+2007%2E+Managing+ambiguities+across+utterances+in+dialogue%2E+In+Ron+Artstein+and+Laure+Vieu%2C+editors%2C+Proceedings+of+DECALOG+2007%3A+Workshop+on+the+Semantics+and+Pragmatic)
9. Prashant Doshi and Piotr J. Gmytrasiewicz. 2009. Monte carlo sampling methods for approximating interactive pomdps. J. Artif. Int. Res., 34(1):297– 337, March. [↗](https://doi.org/10.1613/jair.2630)
10. Michael C. Frank and Noah D. Goodman. 2012. Predicting pragmatic reasoning in language games. Science, 336(6084):998. [↗](https://doi.org/10.1126/science.1218633) [our card](https://md.research.elamur.ai/free/papers/frank-2012-predicting-pragmatic-reasoning-language-games/)
11. Michael C. Frank, Noah D. Goodman, and Joshua B. Tenenbaum. 2009. Using speakers’ referential intentions to model early cross-situational word learning. Psychological Science, 20(5):579–585. [↗](https://doi.org/10.1111/j.1467-9280.2009.02335.x)
12. Michael Franke. 2009. Signal to Act: Game Theory in Pragmatics. ILLC Dissertation Series. Institute for Logic, Language and Computation, University of Amsterdam. [find](https://scholar.google.com/scholar?q=Michael+Franke%2E+2009%2E+Signal+to+Act%3A+Game+Theory+in+Pragmatics%2E+ILLC+Dissertation+Series%2E+Institute+for+Logic%2C+Language+and+Computation%2C+University+of+Amsterdam%2E)
13. Gerald Gazdar. 1979. Pragmatics: Implicature, Presupposition and Logical Form. Academic Press, New York. [find](https://scholar.google.com/scholar?q=Gerald+Gazdar%2E+1979%2E+Pragmatics%3A+Implicature%2C+Presupposition+and+Logical+Form%2E+Academic+Press%2C+New+York%2E)
14. Piotr J. Gmytrasiewicz and Prashant Doshi. 2005. A framework for sequential planning in multi-agent settings. Journal of Artificial Intelligence Research, 24:24–49. [↗](https://doi.org/10.1613/jair.1579)
15. 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](https://scholar.google.com/scholar?q=Dave+Golland%2C+Percy+Liang%2C+and+Dan+Klein%2E+2010%2E+A+game%2Dtheoretic+approach+to+generating+spatial+descriptions%2E+In+Proceedings+of+the+2010+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C)
16. 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. [↗](https://doi.org/10.1163/9789004368811_003)
17. Robert M. Harnish. 1979. Logical form and implicature. In Linguistic Communication and Speech Acts, pages 313–391. MIT Press, Cambridge, MA. [find](https://scholar.google.com/scholar?q=Robert+M%2E+Harnish%2E+1979%2E+Logical+form+and+implicature%2E+In+Linguistic+Communication+and+Speech+Acts%2C+pages+313%E2%80%93391%2E+MIT+Press%2C+Cambridge%2C+MA%2E)
18. Julia Hirschberg. 1985. A Theory of Scalar Implicature. Ph.D. thesis, University of Pennsylvania. [find](https://scholar.google.com/scholar?q=Julia+Hirschberg%2E+1985%2E+A+Theory+of+Scalar+Implicature%2E+Ph%2ED%2E+thesis%2C+University+of+Pennsylvania%2E)
19. Laurence R Horn. 1972. On the Semantic Properties of Logical Operators in English. Ph.D. thesis, UCLA, Los Angeles. [find](https://scholar.google.com/scholar?q=Laurence+R+Horn%2E+1972%2E+On+the+Semantic+Properties+of+Logical+Operators+in+English%2E+Ph%2ED%2E+thesis%2C+UCLA%2C+Los+Angeles%2E)
20. Gerhard Jäger. 2007. Game dynamics connects semantics and pragmatics. In Ahti-Veikko Pietarinen, editor, Game Theory and Linguistic Meaning, pages 89–102. Elsevier, Amsterdam. [find](https://scholar.google.com/scholar?q=Gerhard+Ja%CC%88ger%2E+2007%2E+Game+dynamics+connects+semantics+and+pragmatics%2E+In+Ahti%2DVeikko+Pietarinen%2C+editor%2C+Game+Theory+and+Linguistic+Meaning%2C+pages+89%E2%80%93102%2E+Elsevier%2C+Amsterdam%2E)
21. Gerhard Jäger. 2012. Game theory in semantics and pragmatics. In Maienborn et al. (Maienborn et al., 2012). [find](https://scholar.google.com/scholar?q=Gerhard+Ja%CC%88ger%2E+2012%2E+Game+theory+in+semantics+and+pragmatics%2E+In+Maienborn+et+al%2E+%28Maienborn+et+al%2E%2C+2012%29%2E)
22. Emiel Krahmer and Kees van Deemter. 2012. Computational generation of referring expressions: A survey. Computational Linguistics, 38(1):173–218. [↗](https://doi.org/10.1162/coli_a_00088)
23. Claudia Maienborn, Klaus von Heusinger, and Paul Portner, editors. 2012. Semantics: An International Handbook of Natural Language Meaning, volume 3. Mouton de Gruyter, Berlin. [find](https://scholar.google.com/scholar?q=Claudia+Maienborn%2C+Klaus+von+Heusinger%2C+and+Paul+Portner%2C+editors%2E+2012%2E+Semantics%3A+An+International+Handbook+of+Natural+Language+Meaning%2C+volume+3%2E+Mouton+de+Gruyter%2C+Berlin%2E)
24. 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](https://scholar.google.com/scholar?q=Christopher+Potts%2E+2012%2E+Goal%2Ddriven+answers+in+the+Cards+dialogue+corpus%2E+In+Nathan+Arnett+and+Ryan+Bennett%2C+editors%2C+Proceedings+of+the+30th+West+Coast+Conference+on+Formal+Linguistics%2C+Somerville%2C+)
25. 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](https://scholar.google.com/scholar?q=Hannah+Rohde%2C+Scott+Seyfarth%2C+Brady+Clark%2C+Gerhard+Ja%CC%88ger%2C+and+Stefan+Kaufmann%2E+2012%2E+Communicating+with+cost%2Dbased+implicature%3A+A+game%2Dtheoretic+approach+to+ambiguity%2E+In+The+16th+Workshop+on+the+Sem)
26. Seymour Rosenberg and Bertram D. Cohen. 1964. Speakers’ and listeners’ processes in a word communication task. Science, 145:1201–1203. [↗](https://doi.org/10.1126/science.145.3637.1201)
27. 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. [↗](https://doi.org/10.1613/jair.1659)
28. 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](https://scholar.google.com/scholar?q=Alex+Stiller%2C+Noah+D%2E+Goodman%2C+and+Michael+C%2E+Frank%2E+2011%2E+Ad%2Dhoc+scalar+implicature+in+adults+and+children%2E+In+Proceedings+of+the+33rd+Annual+Meeting+of+the+Cognitive+Science+Society%2C+Boston%2C+July%2E)
29. Adam Vogel, Max Bodoia, Dan Jurafsky, and Christopher Potts. 2013. Emergence of Gricean maxims from multi-agent decision theory. In Human Language Technologies: The 2013 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Atlanta, Georgia, June. Association for Computational Linguistics. [find](https://scholar.google.com/scholar?q=Adam+Vogel%2C+Max+Bodoia%2C+Dan+Jurafsky%2C+and+Christopher+Potts%2E+2013%2E+Emergence+of+Gricean+maxims+from+multi%2Dagent+decision+theory%2E+In+Human+Language+Technologies%3A+The+2013+Annual+Conference+of+the+North)