^December January – 2011 ^February

Over the past decades the evolutionary approach has been used in many fields of computer science research. Lately, with the growth of computation power, Genetic Programming (GP) has been showing much promise. Our work is an attempt to apply the tree based GP approach to several zero-sum deterministic full knowledge to board games. We present published results on Lose Checkers as well as yet unpublished improved results, and also results on two other board games: 10X10 Checkers, and Reversi. Our system implements strongly typed GP trees, explicitly defined introns and multi-tree individuals. We use the GP trees to evaluate possible future game states. Used together with traditional search techniques the results show much promise and imply that tree based GP may be useful in finding good players for other similar games.

RNA mutational analysis at the secondary structure level can be useful to a wide range of biological applications. It can be used to predict an optimal site for performing a nucleotide mutation at the single molecular level, as well as to analyze basic phenomena at the systems level. In the past several years, the program RNAmute that is structure-based and relies on RNA secondary structure prediction has been developed for assisting in RNA mutational analysis. It has been extended from single-point mutations to treat multiple-point mutations efficiently by initially calculating all suboptimal solutions, after which only the mutations that stabilize the suboptimal solutions and destabilize the optimal one are considered as candidates for being deleterious.

A key question in cooperative game theory is that of coalitional stability, usually captured by the notion of the core- the set of outcomes such that no subgroup of players has an incentive to deviate. However, some coalitional games have empty cores, and any outcome in such a game is unstable. In this talk, we investigate the possibility of stabilizing a coalitional game by using external payments (subsidies). We consider a scenario where an external party, which is interested in having the players work together, offers a supplemental payment to the grand coalition, thereby extending the core. We define the cost of stability (CoS) as the minimal external payment that stabilizes the game. We provide general bounds on the cost of stability in several classes of games, and explore its algorithmic properties and its relations with other solution concepts. Joint work with Yoram Bachrach, Edith Elkind, Dmitrii Pasechnik, Michael Zuckerman, Joerg Rothe, and Jeffrey S. Rosenschein.