## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, July 08, 2008, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Karl Lieberherr (Northeastern University, Boston, USA)

## Using Artificial Markets to Teach Computer Science Through Trading Robots

Motivated by a collaboration with the Algorithmic Trading Group of GMO, we have invented an artificial market game, called SDG(Max), inhabited by trading robots that are empowered by the students. The students teach the robots to precisely follow the rules of the artificial markets. And the most interesting challenge for the students is to equip their robots with enough artificial intelligence so that they will win in the market (game competitions). Although the artificial markets are sufficiently simple so that they can be formally analyzed, they have interesting analogies to real markets.

Each trading robot gets 5 million start capital which it uses to buy derivatives. A derivative in SDG(Max), where Max is a maximization problem with objective function range [0,1], is a triple (predicate, price, robot), where predicate selects a subset of the instances of Max, price is a number in [0,1], and robot is the robot which put the derivative on the market. After a derivative is bought, the buyer has two rights: to receive raw material R satisfying the predicate and to receive q million, where q in [0,1] is the quality of the finished product, the solution found by the buyer for R.

The robots offer and buy derivatives. The robot which follows the market rules, and makes the most money, wins. A robot consists of an offering agent, a buying agent, a raw material agent and a finished product agent which is finding (approximate) solutions for the maximization problem.

The artificial markets create a rich learning experience for the students along several dimensions: abstraction skills (how to model those markets to determine the break-even price for a derivative), software reading skills (why is this robot beating mine; how can I improve mine), software architecture skills (which software product line technologies are most suitable - I promote a functional implicit invocation architecture called DemeterF, but the students are free to choose others), software design skills (what are the concerns and how can I keep them separate down to the implementation level; what are the data structures and how do we traverse and process them), algorithm analysis skills (how fast and how well can I solve the maximization problem). Underneath is a basic dimension of mathematics including: how to count combinatorial objects; how to minimize and maximize continuous functions and how to solve min-max problems.

The talk will present our successful experience in teaching Computer Science using trading robots both for an undergraduate capstone course as well as a graduate master level course. We used the market instance SDG(MAXSAT) for the undergraduates and SDG(MAXCSP) for the graduate students. The talk is intended for educators in Computer and Information Science and educational game designers.

SDG stands for Specker Derivative Game, named after ETH Professor Ernst Specker.

Information for students and suggested topics for student talks