This talk is at COMPASS seminar (reciprocal visit after P. Davis talk last year in our seminar)

Speaker: Arkadii Slinko
Title: Proportional Representation and Strategic Voters
Date: Friday 21 May 2010
Time: 12pm
Location: Fale Pacifika Building 273 Rm 104
Abstract: This paper was initially motivated by a desire to explain the behaviour of voters at the New Zealand general election held September 17th, 2005. The New Zealand electoral system is mixed member proportional (MMP). Anecdotal evidence has suggested that some voters voted insincerely even though their doing so could have cost their most preferred party seats. We analyse the election and present two models that account for the behaviour observed in the election. We rigorously investigate opportunities for strategic voting under proportional representation (PR), other than those that emerge due to rounding. This talk is based on the paper “Proportional Representation and Strategic Voters” written jointly with Shaun White which is to appear in Journal of Theoretical Politics.

Slides are available.

Speaker: Tatiana Gvozdeva
Affiliation: The University of Auckland
Title: Roughly weighted games with interval thresholds
Date: Friday, 30 Apr 2010
Time: 3:00 pm
Location: Room 401 (small math seminar room)

It is very well-known that not every simple game has a representation as weighted majority game. The first step in attempt to characterise non-weighted games was the introduction of the class of roughly weighted games. This concept proved to be useful. It realises a very common idea in Social Choice that sometimes the rule needs an additional tie-breaking rule that helps to decide who is the winner if the results of all candidates are on a certain ‘threshold’. We gave a criterion of rough weightedness in the previous talk at this seminar. However not all games are even roughly weighted. Hence we need a more general construction to represent all games.

In this paper we introduce and explore several concepts that generalise roughly weighted games in several directions. One idea is to make the threshold thicker, i.e. use not a number but an interval for it. A good example of this situation would be a faculty vote. If neither side controls a 2/3 majority (calculated in faculty members or their grant dollars), then the Dean would decide the outcome. We can keep weights normalised so that the lower end of the interval is fixed at 1, then the right end of the interval becomes a “resource” parameter. We show that all class of games split into the hierarchy of classes of games define by this parameter. We show that as it increases we get strictly greater descriptive power, i.e., if the resource parameter gets larger, strictly more games can be described.

A situation when the number of players n is fixed also of interest. Then there is an interval [1,s(n)], numbers from which provide us with a resource parameter for every game. There will be finitely many numbers q in this interval such that the interval [1,q] represents more n-player games that any interval [1,q’] with q'<q. We call the set of such numbers the nth spectrum. We calculate the spectrum for n<7. Also we present an upper bound for s(n).

Another hierarchy of games emerges when we restrict the number of possible values that the weight of a coalition might be when this weight is in the threshold interval.

Speaker: Piotr Faliszewski
Affiliation: AGH University of Science and Technology, Krakow
Title: The Complexity of Campaign Management: Swap Bribery
Date: 6 May 2010
Time: 3:00pm
Location: MLT3 (Building 303)

Abstract: In voting theory, bribery is a form of manipulative behavior in which an external actor (the briber) offers to pay the voters to change their votes in order to get her preferred candidate elected. While bribery is typically associated with cheating in elections, its mathematical model can also be interpreted in terms of campaign management. In this work we study a model of bribery which is particularly well-suited for this campaign-management interpretation. Namely, we consider a model where the price of each vote depends on the amount of change that the voter is asked to implement and we focus on situations where the only allowed action is to shift the briber’s (campaign manager’s) preferred candidate forward on voters’ preference lists. We provide hardness results and polynomial time (approximate) algorithms for this type of bribery in many prominent voting rules.

Speaker: Patrick Girard
Affiliation: Department of Philosophy, University of Auckland
Title: Reasoning about social preferences
Date: Thursday, 1 Apr 2010
Time: 3:00 pm
Location: Room 401

A systematic way of aggregating individual preferences is to impose a hierarchy over groups of agents. I proceed in two steps, first by aggregating individual desires constrained by given hierarchies and second by defining preferences based on group desires. All this can be performed precisely in a hybrid modal logic (a basic modal logic augmented with names for states). This procedure avoids (some of) the consequences of Arrow’s impossibility theorem in social choice theory while retaining desirable aggregation properties, but the price to pay is the prioritization of agents. In this talk, I present the basic logic of preference aggregation and discuss the logical approach to the problem of preference aggregation.

Speaker: Arkadii Slinko
Affiliation: The University of Auckland, Mathematics
Title: Dagstuhl and manipulation by cloning candidates
Date: Thursday, 18 Mar 2010
Time: 3:00 pm
Location: Room 401

Firstly I will give my brief impressions of Dagstuhl meeting on Foundations of Computational Social Choice which took place last week. Then I will talk about an article written jointly with Piotr Faliszewski and Edith Elkind which I presented it at the workshop. Here I will give more details.

Abstract of the article

We consider the problem of manipulating elections via cloning candidates. In our model, a manipulator can replicate each candidate c by adding its several clones, i.e., new candidates that are so similar
to c that each voter simply replaces c in his vote with the block consisting of c and its clones. The outcome of the resulting election may then depend on how each voter orders the clones within the block. We formalize what it means for a cloning manipulation to be successful (which turns out to be a surprisingly delicate issue), and, for a number of prominent voting rules, characterise the preference profiles for which a successful cloning manipulation exists. We also consider the model where there is a cost associated with producing each new clone, and study the complexity of finding a minimum-cost cloning manipulation.