Speaker: Professor Bettina Klaus
Affiliation: University of Lausanne
Date: Friday 3 May 2013
Time: 12pm
Venue: Room 317, Level 3, Owen G Glenn Building

Abstract: In college admissions and student placements at public schools, the admission decision can be thought of as assigning indivisible objects with capacity constraints to a set of students such that each student receives at most one object and monetary compensations are not allowed. In these important market design problems, the agent-proposing deferred-acceptance (DA-)mechanism with responsive strict priorities performs well and economists have successfully implemented DA-mechanisms or slight variants thereof. We show that almost all real-life mechanisms used in such environments – including the large classes of priority mechanisms and linear programming mechanisms – satisfy a set of simple and intuitive properties. Once we add strategy-proofness to these properties, DA-mechanisms are the only ones surviving. In market design problems that are based on weak priorities (like school choice), generally multiple tie-breaking (MTB) procedures are used and then a mechanism is implemented with the obtained strict priorities. By adding stability with respect to the weak priorities, we establish the first normative foundation for MTB-DA-mechanisms that are used in NYC.

This is a joint Department of Economics/CMSS seminar.

Speaker: Arkadii Slinko
Affiliation: The University of Auckland
Title: Secret sharing schemes (an elementary introduction)
Date: Tuesday, 7 May 2013
Time: 4:00 pm
Location: Room 6115, Owen Glenn Building

Certain cryptographic keys, such as missile launch codes, numbered bank accounts and the secret decoding exponent in an RSA public key cryptosystem, are so important that they present a dilemma. If too many copies are distributed, one may be leaked. If too few, they might all be lost or accidentally destroyed. Secret sharing schemes invented by Shamir (1979) and Blakley (1979) address this problem, and allow arbitrarily high levels of confidentiality and reliability to be achieved. A secret sharing scheme `divides’ the secret S into `shares’ – one for every user – in such a way that S can be easily reconstructable by any authorised subset of users, but an unauthorised subset of users can extract absolutely no information about S. A secret sharing scheme, for example, can secure a secret over multiple servers and it remains recoverable despite multiple server failures.

Secret sharing schemes are a sort of cooperative games where the information and not money is being distributed among players. The set of authorised coalitions of a secret sharing scheme is a simple game so there is a rich connection to the theory of games.

In my talk I will give an elementary introduction to secret sharing.

Speaker: Dr Ben Greiner
Affiliation: University of New South Wales
Title: Bargaining, Asymmetric Information, and Communication – An Experiment
Date: Tuesday, 9 Apr 2013
Time: 12:00 pm
Location: Lab 04, Level 0, Owen Glenn Building

(note the unusual time and venue)

This paper explores the effect of communication on negotiation behavior in a stylized bargaining environment with asymmetric information. In particular, we study an Ultimatum Game in which the total amount to be bargained over (the pie) might be unknown to one party. We systematically vary whether both parties are informed about the pie size (baseline), or only the proposer, or only the responder. In addition, we vary whether there is no communication before the bargaining procedure, or whether the informed party can send a message about the pie size before decisions are made. In one communication condition, the message sender is free to choose the correct or the wrong message (cheap talk), while in the second communication condition the sender can only choose whether to reveal or not to reveal the true pie size (“true talk”). We find that contrary to the theoretical prediction cheap talk has a significant positive effect on efficiency, while true talk is less effective than expected.

Speaker: Kathryn E. Lenz
Affiliation: Department of Mathematics and Statistics, University of Minnesota Duluth
Title: Voting Methods for Municipal Elections: Propaganda, Field Experiments and what USA Voters Want from an Election Algorithm
Date: Tuesday, 19 Mar 2013
Time: 4:00 pm
Location: Room 6115, Owen Glenn Building

Within the past two decades various cities across the USA have experimented with instant run-off voting (IRV) for political elections. These experiments demonstrate a public desire for replacing plurality voting with a better method and they give insight into what voters want from an election algorithm. This talk will briefly review several standard election algorithms, properties and public reaction to them. Examples will be given of IRV city election results, pro-IRV propaganda found on websites, misrepresentations in newspaper opinion pieces and discussions with mathematicians and non-mathematicians. Though disheartening, misinformation about IRV propagating in the public arena and suppression of full IRV election results do provide opportunities for the mathematically minded to engage in civic dialogue and to raise awareness concerning election algorithm options.

Slides are available.

Speaker: Matthias Ehrgott
Affiliation: The University of Auckland
Title: Multiobjective Optimization for Supporting Radiation Therapy Treatment Planning
Date: Tuesday, 5 Mar 2013
Time: 4:00 pm
Location: Room 6115, Owen Glenn Building

The choice of a plan for radiotherapy treatment for an individual cancer patient requires the careful trade-off between the goals of delivering a sufficiently high radiation dose to the tumour and avoiding irradiation of critical organs and normal tissue. To support the treatment planner in this task it is necessary to visualize these trade-offs. The treatment planning problem can be formulated as a multi-objective optimization problem. We present a method to compute the optimal trade-offs for this problem and plot them in three dimensions. Furthermore, by computing a finite set of treatment plans that are well distributed across the entire trade-off surface, we support the treatment planner in identifying the best available plan for the patient under consideration.

Slides are available

Speaker: Dov Samet
Affiliation: Tel Aviv University
Title: Interim agreements: In the footsteps of Zeno, Parkinson, and Nash
Date: Thursday, 14 Feb 2013
Time: 10:30 am
Location: Room 317, Owen Glenn Building

Zeno’s paradoxes of motion, which claim that moving from one point to another cannot be accomplished in finite time, seem to be of serious concern when moving towards an agreement in utility space is concerned. Parkinson’s Law of Triviality implies that such an agreement cannot be reached in finite time. By explicitly modeling dynamic processes of reaching interim agreements, we show that if utilities are von Neumann-Morgenstern, then no such process can bring about an agreement in finite time in linear bargaining problems. To extend this result for all bargaining problems, we characterize a particular path illustrated by Raiffa, and show that no agreement is reached along this path in finite time. When deadlines are set, then agreements are reached exactly at the deadline, proving Parkinson’s Law that work expands so as to fill the time available for its completion.

Speaker: Matthew Ryan
Affiliation: University of Auckland
Title: Freedom of Opportunity: Axiomatic Approaches
Date: Tuesday, 4 Dec 2012
Time: 4:00 pm
Location: Room 6115, Owen Glenn Building

This talk will give a brief and selective overview of the literature on axiomatic characterisations of freedom. Since this literature spans (at least) economics, mathematics, philosophy, politics and statistics, I hope it might be a fruitful area of potential research for the CMSS group. I’ll discuss the main strands of this research and some key results. I’ll also present recent work connecting this literature to that on abstract convexity, including some (hopefully interesting!) open questions.

Link to slides
Survey article by Dowding and van Hees

Speaker:     Marinus Ferreira
Affiliation: The University of Auckland
Title:       Conventional authority
Date:        Tuesday, 9 Oct 2012
Time:        4:00 pm
Location:    Room 5115, Owen Glenn Building

It is a truism that many instances of authority are conventional – that the standing of the authority is granted by some convention in society. There exists no standard account of how to understand this truism. I propose that we extend David Lewis’s game-theoretic analysis of conventions to give a comprehensive analysis of what the conventional basis of authority is. This paper doesn’t develop a new game-theoretic result, but offers an interpretation of Lewis’s original result to cover a new range of cases. He analysed conventions as ways for people to co-ordinate by furnishing each other with the necessary expectations of how people will act in specified circumstances in order to make their behaviour predictable. Making use of an extension of his analysis to the ethical domain – which I call ‘limited conventionalism’ – I intend to show how authority is conventional in the same way. I introduce the notion of a ‘benign arbiter’ – somebody whose commands everybody will follow and expect everybody else to follow, and who, when asked to adjudicate on a problem case, always selects one of the best candidate options. I argue that we can endorse the commands of an authority or not based on whether they are a benign arbiter – if they are, we should follow the commands, and if they aren’t, we needn’t. To illustrate my case, I give a limited conventionalist analysis of three instances of authority which many people don’t expect to be conventional: parental authority, divine authority, and trial by ordeal.

Speaker:     Michael Fowlie and Mark C. Wilson
Affiliation: The University of Auckland
Title:       Electoral engineering through simulation
Date:        Tuesday, 25 Sep 2012
Time:        4:00 pm
Location:    Room 5115, Owen Glenn Building

We report on recent and ongoing work to optimize electoral system parameters (e.g., party vote threshold for MMP) with respect to the competing criteria of decisiveness/governability and proportionality/fairness of parliament. This uses both real data (hard to obtain) and extensive simulation with artificially generated societies. Models for the latter are also hard to find, and we solicit audience help. Some interesting computational issues arise.

This forms the mandatory public talk for Michael’s CS380 project.

Everyone welcome!

Speaker:     Shaun White
Affiliation: The University of Auckland
Title:       Strategic voting: overshooting and undershooting, and safe and unsafe strategic votes
Date:        Tuesday, 11 Sep 2012
Time:        4:00 pm
Location:    Room 5115, Owen Glenn Building

There are many situations in which mis-coordinated strategic voting can leave strategic voters worse off than they would have been had they not tried to manipulate.  We develop a framework for analysing the simplest of such scenarios, in which a set of strategic voters all have the same sincere preferences and all cast the same strategic vote, while all other voters vote sincerely.  We say a voter has `an incentive to vote strategically’ when they can manipulate the choice mechanism by voting strategically in unison with certain other voters who share their sincere preferences.  We classify mis-coordinations as instances of strategic overshooting (when the choice mechanism is anonymous, overshooting occurs when too many vote strategically) or strategic undershooting (too few vote strategically). If casting a strategic vote cannot inadvertently lead to overshooting or undershooting, we call it safe. We extend the Gibbard-Satterthwaite Theorem by proving that every onto and non-dictatorial social choice rule can be individually manipulated by a voter casting a safe strategic vote. All this is joint work with Arkadii Slinko.