Dialog participants in a non-mixed initiative dialogs, in which one participant asks questions exclusively and the other participant responds to those questions exclusively, can select actions that minimize the expected length of the dialog. The choice of question that minimizes the expected number of questions to be asked can be computed in polynomial time in some cases. The polynomial-time solutions to special cases of the problem suggest a number of strategies for selecting dialog actions in the intractable general case. .
