Speaker: Matthew Ryan
Affiliation: The University of Auckland
Title: Path Independent Choice and the Ranking of Opportunity Sets
Date: Tuesday, 29 Mar 2011
Time: 4:00 pm
Location: Room 6115, Owen Glenn Building

An opportunity set is a non-empty subset of a given set X. A decision-maker, when confronted with an opportunity set, is allowed to choose one element from it.
We assume that the decision-maker has some reflexive and transitive ordering over opportunity sets. Such an ordering is called an “indirect utility ordering” if there
exists a weak order (preference relation) on X such that opportunity set A is weakly preferred to opportunity set B iff the most preferred element(s) from A∪B includes
at least one element of A. Necessary and sufficient conditions for an opportunity set ranking to be an indirect utility ordering are well-known (Kreps, 1979). We give
necessary and sufficient conditions for an ordering of opportunity sets to be consistent with a path independent choice function, or “Plott consistent”. That is, opportunity set A is weakly
preferred to opportunity set B iff the acceptable choice(s) from A∪B include at least one element of A. The proof employs results from the theory of abstract convex geometries.

Speaker: Arkadii Slinko
Affiliation: The University of Auckland
Title: Hierarchical games
Date: Tuesday, 15 Mar 2011
Time: 4:00 pm
Location: Room 6115, Owen Glenn Building

In many situations, both in human and artificial societies, cooperating agents have different status with respect to the activity and it is not uncommon that certain actions are only allowed to coalitions that satisfy certain criteria, e.g., to sufficiently large coalitions or coalitions which involve players of sufficient seniority. Simmons (1988) formalised this idea in the context of secret sharing schemes by defining the concept of a (disjunctive) hierarchical access structure.

The mathematical concept which describe access structures of secret sharing schemes is that of a simple game. In this paper we aim to start a systematic study of hierarchical games, both disjunctive and conjunctive, and our results show that they deserve such a treatment. We prove the duality between disjunctive and conjunctive hierarchical games. We introduce a canonical representation theorem for both and characterise disjunctive hierarchical games as complete games with a unique shift-maximal losing coalition. We give a short combinatorial proof of the Beimel-Tassa-Weinreb characterisation theorem of weighted disjunctive hierarchical games. By duality we get similar theorems for conjunctive hierarchical games.

This is a joint work with Tatiana Gvozdeva and Ali Hameed.

Speaker: Nadja Betzler
Affiliation: Technical University of Berlin
Title: Parameterized algorithmics for Kemeny’s voting system
Date: Tuesday, 1 Mar 2011
Time: 4:00 pm
Location: Room 6115, Owen Glenn Building

Kemeny’s voting system is concerned with optimally aggregating a multiset of preference lists into a consensus list. We study the parameterized complexity of the underlying decision problem, called Kemeny Score, with respect to several different parameterizations.This includes a discussion about the relevance and motivation of the parameterizations illustrating the usefulness of a multivariate complexity analysis for voting problems.
We further extend this study by introducing the concept of “partial kernelization”. Based on this, we devise an additional result for the parameter measuring the average distance between pairs of input votes. Moreover, the partial kernelization concept naturally leads to additional parameterizations. Finally, we provide experimental results for computing optimal Kemeny rankings based on some of the previously introduced methods.

Speaker: John McCabe Dansted
Affiliation: University of Western Australia
Title: Axioms for obligation and robustness with temporal logic
Date: Tuesday, 15 Feb 2011
Time: 4:00 pm
Location: Room 6115, Owen Glenn Building

Deontic logics are used to reason about norms. These norms may include
policies, relating to operation of an automated system, that are
subject to violation. We present a Temporal Logic of Robustness
(RoCTL*) that is intended to verify that a system is Robust to
some number of norm violations. We present sound and complete
axiomatisations of fragments of this logic and briefly discuss the
philosophical background to these axioms, including which axioms may
be relevant in fields other than robust systems. Although every
property that can be expressed in RoCTL* can be expressed in an
existing logic (CTL*), RoCTL* can express some properties much more
succinctly than CTL*.

Everyone welcome!

This may be of interest to CMSS members.

Special session on **Logics for Games and Social Choice**
CLIMA XII 12th International Workshop on Computational Logic in Multi-Agent Systems
http://centria.di.fct.unl.pt/events/climaXII/sessions.html
Barcelona, Spain, July 17-18, 2011.
Affiliated with IJCAI’11. Submission deadline: April 8.

The 2010 summer workshop archive now contains almost all the slides for the talks.
The 2011 workshop is tentatively planned for December, and will have logic as a theme. More details will follow throughout the year.
Mark Wilson is now the Director of CMSS and the seminar organizer is Arkadii Slinko. Please contact us if you want to give a talk in the seminar, or otherwise visit us.
We expect some visitors in 2011, including Nadja Betzler from Germany.

We are planning a workshop in December. The first announcement from Arkadii Slinko:

The Centre for Mathematical Social Science at The University of Auckland (New Zealand) is planning a series of lectures and seminars  given by visitors
and members of the Centre in the period of 13–22 of December 2010.  At the moment the following visitors have expressed their intention to participate and give lectures:

– Clemens Puppe (KIT, Karlsruhe)
– Bill Zwicker (Union College, New York)
– Toby Walsh (University of NSW and NICTA)
– Igor Shparlinski (Macquarie University, Sydney)

This will be accompanied by discussions of future research directions and research collaborations in small groups with participation of visitors and local researchers including PhD and graduate students. The talks will take place in mornings and in the afternoon we will have sessions for discussions on topics relevant to the lectures.

======================

TOPICS AND DATES:

13 Dec (Monday) – Registration. Welcoming drink at Old Government House.
14 Dec (Tuesday) – Simple games and Secret Sharing.
15 Dec (Wednesday) – Cryptography.
17 Dec (Friday) – Comparative probabilities and simple games.
20 Dec (Monday) – Voting theory.
21 Dec (Tuesday) – Uncertainty, Ambiguity and Choice.

The exact schedule for each day will be announced later. During the weekend 18-19 of December we are planning an excursion.

======================

APPROXIMATE SCHEDULE:

Simple Games and Secret Sharing (organiser Arkadii Slinko)

1. Arkadii Slinko – Complete simple games and hierarchical secret sharing schemes.
2. Bill Zwicker – Hereditary rough weigtedness in simple games.
3. Ali Hameed – Weighted and roughly weighted ideal secret sharing schemes.

Topics for discussions in the afternoon session: simple games and secret sharing schemes, hereditary rough weightedness and its
characterisations, hierarchical simple games (access structures) and their properties.

Cryptography (organiser Steven Galbraith)

1. Igor Shparlinski – Group structures of elliptic curves over finite fields
2. Steven Galbraith – Introduction to “Learning With Errors” and lattice-based cryptography
3. Edoardo Persichetti – Compact McEliece keys using quasi-dyadic Srivastava codes

Topics for discussions in the afternoon session:  Cryptography from codes, Homomorphic encryption, Lattices in cryptography.

Comparative probabilities and simple games (organiser Arkadii Slinko)

1. Arkadii Slinko – Abstract simplicial complexes which are initial segments of comparative probability orders
2. Tatyana Gvozdeva – On Edelman’s conjecture about simple games obtained from comparative probability orders
3. Ilya Chevyrev – On the number of facets of the convex polytope of a comparative probability order.

Topics for discussions in the afternoon session: Edelman’s conjecture, characterisations of weighted simple
games by polytopes

Uncertainty, Ambiguity and Choice (Organiser Matthew Ryan)

1. Clemens Puppe – “Majoritarian Indeterminacy and Path-Dependence: The Condorcet Efficient Set”
(based on joint work with Klaus Nehring and Markus Pivato)
2. Matthew Ryan – Abstract Convex Geometries and Decision Theory
3. Patrick Girard, Jeremy Seligman – Logic of Social Choice

Topics for discussions in the afternoon session: Abstract convexity in decision theory; abstract convexity in social choice; modal logic for ambiguous semantics.

Voting Theory (organiser Mark Wilson)

1. 1. Bill Zwicker – “The Geometry of Influence: Weighted Voting and Hyper-ellipsoids,” joint work with Nicolas Houy.
2. Toby Walsh – Manipulation of Borda and related voting rules
3. Reyhaneh Reyhani – Dynamics in voting games
4. Egor Ianovski – Safe manipulation of Borda

Topics for discussions in the afternoon session: Manipulation of Borda and related voting rules,
Manipulation with partial information, Lotteries and voting rules. Interplay between manipulability and decisiveness

Speaker: John Hillas
Affiliation: Department of Economics, UoA
Title: Backward Induction in Games with Imperfect Recall (with D. Kvasov)
Date: Wednesday, 13 October 2010
Time: 4:00 pm
Location: 301-242 [Science Centre, Symonds Street]

ABSTRACT

The standard solution concepts motivated by the idea of backward induction, subgame perfect equilibrium, extensive form perfect equilibrium, sequential equilibrium, and quasi-perfect equilibrium were explicitly defined only for games with perfect recall.  In games with imperfect recall a literal application of the same definitions is clearly inappropriate.  We give definitions that coincide with the standard definitions in games with perfect recall and define sensible solutions in games without perfect recall.

The basic idea is to look, at subsets of each player’s information sets, at the pure strategies that make that those subsets reachable and to define a system of beliefs as associating to that strategy and that subset a distribution over the other players’ strategies.  We define the relevant solution concepts and show (conjecture) that the inclusions and the relation to proper equilibrium of the associated normal that were true for games with perfect recall remain true.

Very much work in progress.

Speaker: Mark C. Wilson
Affiliation: University of Auckland, Computer Science
Title: The probability of safe manipulation
Date: Wednesday, 25 August 2010
Time: 4:00 pm
Location: 301.242

Manipulation by a coalition in voting games is a well-studied occurrence, yet the underlying model is rather unconvincing. Slinko and White recently introduced the more restricted concept of safe manipulation and studied some basic properties. They posed the question of the probability that safe manipulation can occur. We present some results for positional scoring rules. The numerical results for 3 candidates show that the susceptibility of such rules to safe manipulation differs substantially from that for coalitional manipulation.

Joint work with Reyhaneh Reyhani, to be presented at COMSOC 2010 in Dusseldorf.

Speaker: Suren Basov
Affiliation: La Trobe University
Title: The Inclusiveness of Exclusion
Date: Tuesday, 22 Jun 2010
Time: 3:00 pm
Location: Room 401

Consider a monopolist who produces a good of quality x to sell to consumers.
A consumer’s utility from consuming the good is given by u(a, x) – t, where a is
a parameter, which is privately known to the consumer, x is the quality of the
good purchased, and t is the price paid. The monopolist does not observe a,
but knows the distribution of a in the population of the consumers and chooses
tariff t(x) to maximize her profits. Early models assumed that a belongs either
to a finite set or a one-dimensional continuum. Under these assumptions it was
shown that the monopolist may sometimes choose not to serve some fraction of
consumers in equilibrium, even when there is positive surplus associated with
those consumers. This phenomenon is known as exclusion. However, whether the
exclusion occurs in early models depended on the distribution of types and both
cases exclusion and full coverage were robust with respect to small perturbations of
the model. In a multidimensional screening models a is assumed to be distributed
over a set of dimension greater than one. One of the most celebrated results in the
theory of multidimensional screening comes from Armstrong (1996) where he shows
that under some technical assumptions exclusion always occur in such models.
Though important, Armstrong’s result relies on strong technical assumptions on
both preferences and market structure, which made it hard to apply to many
interesting practical questions. We extend Armstrong’s result on exclusion
in multi-dimensional screening models in two key ways, providing support for the
view that this result is quite generic and applicable to many different markets.
First, we relax the strong technical assumptions he imposed on preferences and
consumer types. Second, we extend the result beyond the monopolistic market
structure to generalized oligopoly settings with entry. We also analyze applications
to several quite different settings: credit markets, automobile industry, research
grants, the regulation of a monopolist with unknown demand and cost functions,
and involuntary unemployment in the labor market.