Skip to main content
Open Access Publications from the University of California

How Optimal is Too Optimal? Expectations About Performance in the Traveling Salesman Problem


How effective do observers expect other problem solvers to be? What makes a decision seem "human"?" We addressed this question in the context of the Traveling Salesman Problem (TSP), a decision problem in which a perfectly optimal solution is intractable, but for which various kinds of approximate solutions are available. We conducted a series of experiments involving both "production tasks" in which we asked subjects to solve the TSP, and "perception tasks", in which we asked subjects to judge others' solutions to the TSP, rating them for intelligence or humanness. Results suggest that observers expect human solutions to be less optimal than algorithmic solutions: observers expect human problem solvers to exhibit a combination of local and global solution criteria, and to use a short look-ahead window when choosing a solution. These results shed light on human models of other humans' minds, a fundamental problem in social interaction and robotics.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View