Interactive repair and computational complexity

A simple form of repair can alleviate computational demands of pragmatic reasoning. Agent-based simulations and complexity analysis comparing repairers (interactive repair-capable agents, without reasoning) and reasoners (pragmatic reasoning-capable agents without repair) across three lexicon sizes (shown here in three shades) with moderate ambiguity. (A) Reasoners suffer decreasing communicative success with growing lexicon size. (B) Computational complexity rises quadratically with lexicon size for reasoners and only linearly for repairers. (C) When needed, repair-capable agents take additional turns to reduce entropy (uncertainty about meaning) in cost-effective ways.

In short, this modelling work suggests that a simple form of interactive repair can be a significantly less computationally costly strategy than pragmatic reasoning for securing communicative success. Simulation data and complexity calculations are from van Arkel et al. 2023; this image is from Dingemanse & Enfield 2024..

Dingemanse, M., & Enfield, N. J. (2024). Interactive repair and the foundations of language. Trends in Cognitive Sciences, 28(1), 30–42. doi: 10.1016/j.tics.2023.09.003 PDF
Arkel, J. van, Woensdregt, M., Dingemanse, M., & Blokpoel, M. (2020). A simple repair mechanism can alleviate computational demands of pragmatic reasoning: simulations and complexity analysis. Proceedings of the 24th Conference on Computational Natural Language Learning. doi: 10.18653/v1/2020.conll-1.14 PDF