@inproceedings{jeknic-etal-2025-collaborative,
    title = "Collaborative Problem-Solving in an Optimization Game",
    author = "Jeknic, Isidora  and
      Duchnowski, Alex  and
      Koller, Alexander",
    editor = "B{\'e}chet, Fr{\'e}d{\'e}ric  and
      Lef{\`e}vre, Fabrice  and
      Asher, Nicholas  and
      Kim, Seokhwan  and
      Merlin, Teva",
    booktitle = "Proceedings of the 26th Annual Meeting of the Special Interest Group on Discourse and Dialogue",
    month = aug,
    year = "2025",
    address = "Avignon, France",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/corrections-2025-10/2025.sigdial-1.58/",
    pages = "780--799",
    abstract = "Dialogue agents that support human users in solving complex tasks have received much attention recently. Many such tasks are NP-hard optimization problems that require careful collaborative exploration of the solution space. We introduce a novel dialogue game in which the agents collaboratively solve a two-player Traveling Salesman problem, along with an agent that combines LLM prompting with symbolic mechanisms for memory, state tracking and problem-solving. Our best agent solves 45{\%} of games optimally in self-play. It also demonstrates an ability to collaborate successfully with human users and generalize to unfamiliar graphs."
}