Title: Artificial Scientific Communities for Combinatorial Optimization: Can Data Mining and Machine Learning Help?

Presenters: Karl Lieberherr and Ahmed Abdelmeged

http://www.ccs.neu.edu/home/mirek/classes/2009-F-DBIRseminar/index.htm

Abstract: We turn software for Combinatorial Optimization into software that can survive on its own in a "real" virtual world of algorithmic scientists with reputations. During a competition, called Specker Challenge Game (SCG), the scientists offer and oppose scientific hypotheses. The SCG is designed to promote good scientific behavior in the agents. Good scientists 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 scientists must stay active, i.e., they must regularly propose a hypothesis or oppose a hypothesis. SCG is designed so that cheating is impossible: agents can only succeed through good scientific behavior which is based on good algorithms.

A discounting protocol, based on delivering a problem instance and solving it, is invoked to either discount or support the 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 Combinatorial Optimization, it offers a new way to analyze algorithms for Combinatorial Optimization, and it is a hypothesis maintenance system for Combinatorial Optimization. We use SCG effectively as a web-based learning and grading tool in our Software Development course (CS 4500).

The agents produce a lot of data during a full round-robin game. Loss of reputation means that there is a programming fault or conceptual fault in the agent. These faults should be repaired for the next competition. Can data mining and machine learning techniques help to produce a better agent for the next competition? Or can it help to compose a new agent based on the performance of the agents in earlier competitions?

Joint work with Bryan Chadwick