Monday, October 27, 2014
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 01
Lecture - 14:15
Abstract:
The program of numerical characterisation and classification of simple games was initiated in the classical monograph of von Neumann and Morgenstern (1944). One of the most fundamental questions of this program is what makes a simple game a weighted majority game. The necessary and sufficient conditions that guarantee weightedness, obtained so far, are combinatorial and surprisingly complex. If a simple game does not have weights, then rough weights may serve as a reasonable substitute. In this lecture I will give necessary and sufficient conditions for a simple game to have rough weights. I will define two functions f(n) and g(n) that measure the maximal deviation of a simple game with n players from a weighted majority game and from roughly weighted majority game, respectively. We formulate known results in terms of lower and upper bounds and discuss how those bounds can be improved.
Colloquium - 16:00
Abstract:
Voter control problems model situations where an external agent is trying to affect the result of an election by adding some voters to the election. Traditionally, in this setting, we can add voters one-by-one, with the goal of making a distinguished alternative win by adding a minimum number of voters.
In this talk, I will present an initial study of combinatorial variants of control by adding voters. In our setting, when the agent chooses to add some voter $v$, she also have to add a whole bundle $\kappa(v)$ of voters associated with $v$. I will present a computational complexity analysis of this problem on two of the most basic voting rules, namely the Plurality rule and the Condorcet rule.