Computational Aspects of Conflict Resolution and Game Theory

Summer 2007 (8 weeks)

**Class times:** MTWRF 3:45-4:50 pm, COMP 321

**Instructors:**

Vladik Kreinovich, office COMP 215, email vladik@utep.edu,
phone 747-6951

Francois Modave, office COMP 222A, email fmodave@utep.edu,
phone 747-5564

**Faculty office hours:** Vladik Kreinovich MTWR 1:15-2:25 pm, or by
appointment

**Prerequisite:** we will use some probabilities and a little bit of
matrices.

**Motivations:**
In 1944, when the Second World War was still going
on, John von Neumann (of von Neumann computer architecture fame)
wrote a book (co-authored with an economist) describing a new
science of "game theory", a science of how to resolve conflicts by
logic and reason. At times, this noble dream seems as impossible as
it may have sounded back in 1944, but at least now we now that there
is a rational way to resolve conflicts.

This course will overview the main concepts of game theory and decision making, with a strong emphasis on computational aspects.

**Contents.**
Along the way, we will learn:

- how to divide a disputed territory
- how to organize fair elections
- what to do if arrested (the famous "prisoners dilemma")
- how to design an array of radiotelescopes
- is it reasonable to sacrifice your life for your brother
- why great love can lead to great tragedies (Romeo and Juliet revisited)
- why viruses and bacteria probably will not kill us all, no matter what science fiction writers make you believe
- why computers, on the other hand, are very vulnerable to viruses

We will also learn about applications to biology (especially to bioinformatics) and to computer security.

These are topics on which we are currently working, we will mention our open problems and hopefully, the best student projects will eventually turn into publishable research papers.

**Textbook:** Peter Morris, Introduction to Game Theory,
Springer-Verlag, 1994.

**Handouts:** The textbook will be heavily supplemented by
handouts, including the following papers:

Hung T. Nguyen, Olga Kosheleva, and Vladik Kreinovich, "Decision Making Beyond Arrow's `Impossibility Theorem', With the Analysis of Effects of Collusion and Mutual Attraction", Proceedings of the Sixth International Conference on Intelligent Technologies InTech'05, Phuket Island, Thailand, December 14-16, 2005, pp. 43-52. file in pdf Hung T. Nguyen and Vladik Kreinovich, "How to Divide a Territory? A New Simple Differential Formalism for Optimization of Set Functions", International Journal of Intelligent Systems, 1999, Vol. 14, No. 3, pp. 223-251. file in pdf Martine Ceberio, Gang Xiang, Luc Longpre, Vladik Kreinovich, Hung T. Nguyen, Daniel Berleant, "Two Etudes on Combining Probabilistic and Interval Uncertainty: Processing Correlations and Measuring Loss of Privacy", Proceedings of the 7th International Conference on Intelligent Technologies InTech'06, Taipei, Taiwan, December 13-15, 2006, pp. 8-17. file in pdf

**Tests and grades:** There will be two tests and one final exam.
Each topic means home assignments.
Maximum number of points:

- first test: 10
- second test: 25
- home assignments: 10
- final exam: 35
- project: 20

A good project can help but it cannot completely cover possible deficiencies of knowledge as shown on the test and on the homeworks. In general, up to 80 points come from tests and home assignments. So:

- to get an A, you must gain, on all the tests and home assignments, at least 90% of the possible amount of points (i.e., at least 72), and also at least 90 points overall;
- to get a B, you must gain, on all the tests and home assignments, at least 80% of the possible amount of points (i.e., at least 64), and also at least 80 points overall;
- to get a C, you must gain, on all the tests and home assignments, at least 70% of the possible amount of points (i.e., at least 56), and also at least 70 points overall.

**Standards of Conduct:**
Students are expected to conduct themselves in a
professional and courteous manner, as prescribed by the
Standards of Conduct.
Students may discuss programming
exercises in a general way with other students, but the solutions must be
done independently. Similarly, groups may discuss project assignments with
other groups, but the solutions must be done by the group itself. Graded
work should be unmistakably your own. You may not transcribe or copy a
solution taken from another person, book, or other source, e.g., a web
page). Professors are required to - and will -
report academic dishonesty and
any other violation of the Standards of Conduct to the Dean of Students.

**Disabilities:**
If you feel you may have a disability that requires
accommodation, contact the Disabled Student Services Office at 747-5148, go
to Room 106 E. Union, or e-mail to
dss@utep.edu.