Isidora Jeknic


2025

pdf bib
Collaborative Problem-Solving in an Optimization Game
Isidora Jeknic | Alex Duchnowski | Alexander Koller
Proceedings of the 26th Annual Meeting of the Special Interest Group on Discourse and Dialogue

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.

2024

pdf bib
A Dialogue Game for Eliciting Balanced Collaboration
Isidora Jeknic | David Schlangen | Alexander Koller
Proceedings of the 25th Annual Meeting of the Special Interest Group on Discourse and Dialogue

Collaboration is an integral part of human dialogue. Typical task-oriented dialogue games assign asymmetric roles to the participants, which limits their ability to elicit naturalistic role-taking in collaboration and its negotiation. We present a novel and simple online setup that favors balanced collaboration: a two-player 2D object placement game in which the players must negotiate the goal state themselves. We show empirically that human players exhibit a variety of role distributions, and that balanced collaboration improves task performance. We also present an LLM-based baseline agent which demonstrates that automatic playing of our game is an interesting challenge for artificial systems.