Grounding Strategic Conversation: Using Negotiation Dialogues to Predict Trades in a Win-Lose Game

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 357–368, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Grounding Strategic Conversation: Using negotiation dialogues to predict trades in a win-lose game Ana¨ıs Cadilhac IRIT Univ. Toulouse, France cadilhac@irit.fr Nicholas Asher IRIT, CNRS Toulouse, France asher@irit.fr Farah Benamara IRIT Univ. Toulouse, France benamara@irit.fr Alex Lascarides School of Informatics Univ. Edinburgh, UK alex@inf.ed.ac.uk Abstract This paper describes a method that predicts which trades players execute during a win- lose game. Our method uses data collected from chat negotiations of the game The Set- tlers of Catan and exploits the conversation to construct dynamically a partial model of each player’s preferences. This in turn yields equilibrium trading moves via principles from game theory. We compare our method against four baselines and show that tracking how preferences evolve through the dialogue and reasoning about equilibrium moves are both crucial to success. 1 Introduction Rational agents act so as to maximise their expected utilities—an optimal trade off between what they prefer and what they believe they can achieve (Sav- age, 1954). Solving a game problem involves find- ing equilibrium strategies: an optimal action for each player that maximises his expected utility, as- suming that the other players perform their speci- fied action (Shoham and Leyton-Brown, 2009). Cal- culating equilibria thus requires knowledge of the other players’ preferences but almost all bargaining games occur under the handicap of imperfect infor- mation about this (Osborne and Rubinstein, 1994). Players therefore try to extract their opponents’ pref- erences from what they say, likewise revealing their own preferences in their own utterances. These elicited preferences guide an agent’s decisions, like choosing to make such and such a bargain with such and such a person. Tracking preferences through dialogue is thus crucial for analyzing the agents’ strategic reasoning in real game scenarios. In this paper, we design a model that maps what people say in a win-lose game into a prediction of exactly which players, if any, trade with each other, and exactly what resources they exchange. We use both statistics and logic: we use a corpus of nego- tiation dialogues to learn classifiers that map each utterance to its speech act and to other acts perti- nent to bargaining; and we develop a symbolic al- gorithm that, from the classifiers’ output, dynami- cally constructs a model of each player’s preferences as the conversation proceeds (for instance, the pref- erence to receive a certain resource, or to accept a certain trade). This preference model uses CP-nets (Boutilier et al., 2004), a representation of prefer- ences for which algorithms for computing equilib- rium strategies exist. We adapt those algorithms to predict the trades executed in the game. The algorithm for construcing CP-nets uses only the output of our classifiers, which in turn rely en- tirely on shallow features in the raw text and robust parsers. Together they provide an end to end model, from raw text to a prediction of which trade, if any, …

Content truncated to 500 words