Application domain: Problem solving software for computationally hard problems.

Constructively Egoistic Software: A New Software Development Process for Problem Solving Software

Egoistic software is software that can survive on its own in a "real" virtual world and experientially and constructively show that it is better than other software for the same problem domain. Egoistic software has an ego. The strength of the ego is objectively measured by Specker Challenge Game (SCG) contests with other egoistic software for the same problem domain. The measurement is dynamic and depends heavily on the other contestants and not on a static benchmark.

The constructively egoistic software fights by finding errors in other software and minimizing its own exposure to errors found by other software. The word "constructively" indicates that the errors are cleanly stated by using witnesses that show that claimed beliefs are wrong.

The Constructively Egoistic Software Development Process

We propose a new software development process for problem solving software that is based on artificial markets. Instead of having the software developers develop a problem solver only, they also develop a problem poser and a challenge offer and accept program. The problem poser and challenge offer and accept programs ultimately improve the quality of the problem solver. The software developers create self-sufficient agents that survive on their own in an artificial market. The success of the agent in the artificial market is proportional to the quality of its problem solver. The artificial market is a nested loop: in the outer loop, driven by humans, the software developers improve their agents and in the inner loop, completely automated, the agents play a game to determine the quality of each agent. The history of the game is public so that the software developers have plenty of information to improve their agents. Benefits of this software development process for problem solving software fall into three categories: Software Engineering, Algorithms and Teaching Computer Science.

The outer loop of the development process: 

initialize all agents with babyAgent(ProblemDomain);
gameNr = 0;
repeat
  gameNr++;
  improve all agents based on history[gameNr-1] and other info;
  history[gameNr] = SCG(admin(ProblemDomain), all agents);
until agents are good enough;

The inner loop of the development process is the SCG contest. The agents play a full round-robin tournament.

The SCG process to software development for problem solving software works as follows: n developers are divided into n/2 teams, each producing an agent. The teams have access to a shared infrastructure of reusable tools. The n/2 agents conquer each other and the winning agent will contain the best software for the given domain. That is the way the artificial market has been designed.

NSF Proposal

Summary and Project Description Title: AF: Medium: Artificial Markets for Software Innovation and Algorithmic Evaluation, submitted in August 2009.

In her letter to the community in December 2009, Jeanette Wing writes: CISE seeks ground-breaking, transformative research that will produce fundamentally new ways of thinking about how to develop, sustain, and reason about software, both during its design and deployment. Research projects that span multiple disciplines within CISE, as well as those that import ideas from elsewhere, are especially welcome.

The SCG (Specker Challenge Game) approach to software development is a fundamentally new way to develop software. It touches on measuring and encouraging the development of innovative algorithms and software, a new way to use competition to foster collaboration during software development, a new approach to organize the bidding process for problem solving software (http://www.ccs.neu.edu/home/lieber/courses/cs4500/f09/project/project2/project2.html), etc.