Two computer scientists (Yoav Shaham and Kevin Leyton-Brown) have recently produced a book on multi-agent systems, a spinoff from which is a self-contained introduction to game theory aimed at interdisciplinary users. Check it out and give your feedback! It has received excellent reviews so far.
Speaker: Geoff Pritchard
Affiliation: The University of Auckland
Title: Impartial-culture asymptotics: a central limit theorem for manipulation of elections
Date: Monday, 30 Mar 2009
Time: 4:00 pm
Location: Room 401 (small math seminar room)
We consider the problem of manipulation of elections using positional voting rules under Impartial Culture voter behaviour. We consider both the logical possibility of coalitional manipulation, and the number of voters that must be recruited to form a manipulating coalition. It is shown that the manipulation problem may be well approximated by a very simple linear program in two variables. This permits a comparative analysis of the asymptotic (large-population) manipulability of the various rules. It is seen that the manipulation resistance of positional rules with 5 or 6 (or more) candidates is quite different from the more commonly analyzed 3- and 4-candidate cases.
This is joint work with Mark Wilson, to appear in Mathematical Socal Sciences. Slides for the talk are available.
Noam Nisan is one of the authors of the recent book Algorithmic Game Theory and his blog at http://agtb.wordpress.com/ is focused on this topic. It should be of interest to members of this group. He has a recent post on the history of this very active new field, in which he says:
“As the Internet was growing around the mid-to-late 1990’s, several threads of research emerged that somehow connected three key elements: Computer Science, Economics & Game-Theory, and the Internet. Within the networking community, several researchers started worrying about the non-cooperative nature of the Internet, and started considering the issue of incentives. Within the AI community, the coordination between multiple software “agents” became an area of study. Electronic commerce started flourishing, and the underlying basic questions started emerging. A few economists started studying Internet-related economic questions. Around the late 1990’s the different groups of people with these different motivations started talking to each other, and a joint field started emerging. “
Modelling Health Care: Combining real-world data in an “expert system” to test policy scenarios
Peter Davis, Director, COMPASS
There is increasing interest in the application of computational techniques in the social sciences, particularly in the area of modelling social processes. We present preliminary work in building a micro-simulation model of the system of decision-making in health care in the community whereby people experience illness and go to the doctor, who then responds. We combine data from different sources to give this model a solid base in the “real world” and we test it against external data. Policy scenarios are foreshadowed. There are major opportunities for collaborative work across disciplinary boundaries.
Note: COMPASS (www.compass.auckland.ac.nz) is a research group at UoA that uses quantitative, computational techniques in social sciences. The main purpose of this talk is to explore collaborative possibilities between the two groups.
Speaker: Toby Walsh
Affiliation: UNSW and NICTA (Australia)
Title: Where are the really hard manipulation problems?
Date: Wednesday, 18 Mar 2009
Time: 4:00 pm
Location: Building 303, Room 279 (CS seminar room)
Voting is a simple mechanism to aggregate the preferences of agents. Many voting rules have been shown to be NP-hard to manipulate. However, a number of recent theoretical results have suggested that this is only a worst-case complexity, and manipulation may be easy in practice. In this talk, I show that empirical studies are useful in improving our understanding of this issue. I demonstrate that there is a smooth transition in the probability that a coalition can manipulate the result and elect a desired candidate as the size of the manipulating coalition is varied. I argue that for many independent and identically distributed votes, manipulation will be computationally easy even when the coalition of manipulators is critical in size.
Recent Comments