Richard Marmorstein '14 Robot Socrates: Contradiction Identification With Minimum Questioning

Abstract: I develop a concept of computer-assisted Socratic dialogue, aimed at enabling productive and efficient argumentation. The goal is a framework for argumentation that is as rigorous as a formal debate,
yet as convenient as an online quiz. A human specifies questions and answer choices and designates certain sets of answer choices as contradictory. The computer's task is to end the dialogue asking as few questions as  possible, by eliciting a set of answers from a questionee that either includes a contradiction or eliminates the possibility of any contradiction.

I formalize this minimum questioning problem and prove it is NP-hard. I then analyze the problem in terms of a trade-off between (1) asking questions that are most likely to achieve immediate progress towards
termination and (2) asking questions that are most likely to yield  knowledge that will lead towards greater progress towards termination  in the future. I develop a greedy algorithm that maximizes a multi-objective utility function embodying this trade-off, and evaluate its performance on a set of randomly generated dialogues and questionees. Preliminary results suggest that, except in contrived cases, heavily favoring immediate progress is a better strategy. In cases where a contradiction is present, a greedy algorithm that maximizes immediate progress requires asking less than half the number of questions as random question selection. The case where no
contradiction is present proves to be more difficult, and the algorithms I investigate offer only a slight improvement over a random strategy.

Faculty Advisors: Sara Sprenkle and Serge Salan