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.

Speaker:     Arkadii Slinko
Affiliation: The University of Auckland
Title:       Axioms for ex-post rationality
Date:        Monday, 9 Mar 2009
Time:        3:00 pm
Location:    Room 401 (small math seminar room)

A Decision Maker (DM) must choose at discrete moments from a finite set of actions that result in random rewards.  The environment is complex in that she finds it impossible to describe the states of the world and is thus prevented from application of standard Bayesian methods of expected utility maximisation. The DM can however be ex-post rational. If she knows the utilities of the prizes she may, at each step, maximise the “expected utility” of each action using empirical frequencies of the rewards. We give axioms for such ex-post rational behaviour.

Mathematical apparatus used is that of multisets and multiset rankings developed by the presenter in a paper with Murat Sertel (2002).

We also consider the topic of utility elicitation which requires the apparatus of random walks on a non-standard grid. An interesting open question will be formulated that may be a topic for a research project or an Honours dissertation.

The paper is written jointly with Murali Agastya (UNSW, Australia and NUS, Singapore).

Everyone welcome!