Presenter: Karl Lieberherr, Northeastern University, College of Computer and Information Science, Boston, MA.
Abstract:
We present the Specker Challenge Game (SCG) and our experience in using it for innovation in problem solving software and for disseminating CS and mathematical knowledge. We present the Web tools we currently have and the tools we have planned and our experiences with SCG and its limitations.
We turn software for problem solving domains (e.g., optimization and decision problems) into software that can survive on its own in a "real" virtual world of algorithmic scholars with reputations. During a competition, the scholars propose and oppose scientific hypotheses based on experiments conducted by the scholars. The SCG is designed to promote good scientific behavior in the agents. Good scholars propose hypotheses that are difficult to oppose, i.e., hypotheses that are "tight" and that are difficult to discount. Agents are encouraged to express hypotheses they are not sure about but they are encouraged to faithfully express their confidence in their hypotheses. Good scholars must stay active, i.e., they must regularly propose or oppose a hypothesis. SCG is designed so that cheating is impossible: agents can only succeed through good scientific behavior, which includes maximizing their reputation based on good algorithmic knowledge. While the agents compete for reputation (the game is zero sum for reputation), they collaborate on knowledge creation giving each other very specific, constructive feedback.
A discounting protocol, based on delivering a problem instance and solving it, is invoked to either discount or support a hypothesis. As the competition proceeds, the non-discounted hypotheses stand out. The mechanism design for the game guarantees that the winning agent has the best solve algorithm modulo the hypothesis language. SCG is useful as an Innovation Tool for problem solving software, it offers a new way to analyze algorithms, and it is a hypotheses maintenance system.
To use SCG in a particular domain, a suitable challenge language needs to be designed. We will demonstrate two challenge languages for Maximum Boolean Constraint Satisfaction problems (CSP) to illustrate how to design hypotheses languages and how to find strong hypotheses. We use SCG effectively as a web-based teaching tool in our Software Development courses where the students implement software for Maximum Boolean CSP.
More information on SCG is available: http://www.ccs.neu.edu/home/lieber/evergreen/specker/scg-home.html
Joint work with Ahmed Abdelmeged and Bryan Chadwick