Speaker: Mark Wilson
Affiliation: Computer Science Department
Title: Average-case analysis of random assignment algorithms
Date: Monday, 2 May 2016
Time: 4:00 pm
Location: Clock Tower 032

I present joint work with summer scholarship student Jacky Lo. The problem of one-sided matching without money (also known as house allocation), namely computing a bijection from a finite set of items to a finite set of agents each of whom has a strict preference order over the items, has been much studied. Symmetry considerations require the use of randomization, yielding the more general notion of random assignment. The two most commonly studied algorithms (Random Serial Dictatorship (RP) and Probabilistic Serial Rule (PS)) dominate the literature on random assignments. One feature of our work is the inclusion of several new algorithms for the problem. We adopt an average-case viewpoint: although these algorithms do not have the axiomatic properties of PS and RP, they are computationally efficient and perform well on random data, at least in the case of sincere preferences. We perform a thorough comparison of the algorithms, using several standard probability distributions on ordinal preferences and measures of fairness, efficiency and social welfare. We find that there are important differences in performance between the known algorithms. In particular, our lesser-known algorithms yield better overall welfare than PS and RP and better efficiency than RP, with small negative consequences for envy, and are computationally efficient. Thus provided that worst-case and strategic concerns are relatively unimportant, the new algorithms should be seriously considered for use in applications.

Everyone welcome!

Speaker:     Jiamou Liu
Affiliation: Computer Science Department
Title:       Hierarchies, Ties and Power in Organizational Networks
Date:        Monday, 11 Apr 2016
Time:        4:00 pm
Location:    Clock Tower 032
An organizational structure consists of a network where employees are connected by work and social ties. Analyzing this network, one can discover valuable insights into information flow within the organization. Moreover, properly defined centrality measures reveal the distribution of power and, therefore, important individuals in the network. We develop this idea and propose a simple network model that is consistent with management theory, and that captures main traits of large corporations. The carcass of the model is an organizational hierarchy. We extend it by allowing additional types of connections such as collaboration, consultation, and friendship. Having both reporting and non-reporting interpersonal ties, our model supports a multilevel approach to social networks.  We then formally define power and power consistency in organizations. These notions enable us to analyze a range of organizational phenomena such as limited hierarchy height, restructuring through flattening, and impact of non-reporting ties. This is a joint work with Anastasia Moskvina.
Everyone welcome!

Speaker:     Rachel Liu
Affiliation: The University of Auckland
Title:       Generalised Second-Price Auctions
Date:        Monday, 4 Apr 2016
Time:        4:00 pm
Location:    Clock Tower 032
We model the Generalized Second-Price Auction for internet advertising as a strategic form game with complete information. We begin with the simplest game in which two advertisers bid against each other over two advertising positions. We show that each advertiser has a unique weakly dominant strategy and there are multiple Nash equilibria. We then study the game with three advertisers and three positions and show that no player has a dominant strategy.  Each of the six possible allocations may arise as Nash equilibrium. It is not clear which allocation results in the largest welfare loss compared to the socially optimal outcome.  In the general case no player has a dominant strategy as well.
Everyone welcome!

Speaker:     Arkadii Slinko
Affiliation: Department of Mathematics
Title:       Approximation Algorithms for Fully Proportional Representation by Clustering Voters
Date:        Wednesday, 9 Dec 2015
Time:        12:00 pm
Location:    303-561
Charles Dodgson (Lewis Carroll) asserted that “a representation system should find the coalitions in the election that would have formed if the voters had the necessary time and information … and allow each of the coalitions to elect their representative using some single-winner voting method.”
Both the Chamberlin-Courant and Monroe voting rules do exactly that. Given the preferences of voters, they select committees whose members represent the voters so that voters’ satisfaction with their assigned representatives is maximised. These rules suffer from a common disadvantage, being computationally intractable to compute the winning committee exactly when the numbers get large. As both of these rules, explicitly or implicitly, partition voters, they can be seen as clustering of voters so that the voters in each group share the same representative.This suggest studying approximation algorithms for these voting rules by means of cluster analysis, which is the subject of this paper. We develop several such algorithms and experimentally analyse their performance.
Joint work with Piotr Faliszewski and Nimrod Talmon.
Everyone welcome!

Speaker: Mark Wilson
Affiliation: Computer Science Department
Title: Predicting FPP elections
Date: Tuesday, 6 Oct 2015
Time: 5:00 pm
Location: CAG15/114-G15 (Commerce A)

In this informal talk I will discuss some basic issues involved predicting elections in countries using the First Past The Post (single-winner plurality in districts) electoral system. A variety of methods have been tried with varying success. Part of the reason for this talk is to clarify for myself what “success” means. The talk will focus on standard methods involving models of “swing”, which often underlie more complicated models. I will make some predictions for the Canada 2015 election.

Everyone welcome!

Speaker: Samin Aref
Affiliation: Department of Computer Science
Title: Measuring Partial Balance in Signed Networks
Date: Tuesday, 29 Sep 2015
Time: 5:00 pm
Location: CAG15/114-G15 (Commerce A)

Is the enemy of an enemy necessarily a friend, or is a friend of a friend a friend? If not, to what extent does this tend to hold? Such questions were formulated in terms of signed (social) networks and necessary and sufficient conditions for a network to be “balanced” were obtained around 1960. Since then the idea that signed networks tend over time to become more balanced has been widely used in several application areas, such as international relations. However investigation of this hypothesis has been complicated by the lack of a standard measure of partial balance, since complete balance is almost never achieved in practice.

We formalise the concept of a measure of partial balance, compare several known measures on real-world and synthetic datasets, as well as investigating their axiomatic properties. We use both well-known datasets from the sociology literature, such as Read’s New Guinean tribes, and much more recent ones involving senate bill co-sponsorship. The synthetic data involves both Erdős-Rényi and Barabási-Albert graphs.

We find that under all our measures, real-world networks are more balanced than random networks. We also show that some measures behave better than others in terms of axioms. We make some recommendations for measures to be used in future work.

Everyone welcome!

Speaker:     José A. Rodrigues-Neto
Affiliation: Australian National University
Title:       Self-Consistency and Common Prior in Non-Partitional Knowledge Models
Date:        Tuesday, 22 Sep 2015
Time:        5:00 pm
Location:    CAG15/114-G15 (Commerce A)
In non-partitional models of knowledge with objective and subjective state spaces, the issue of self-consistency arises. The present paper defines a multigraph G_j for each player j, and also a global multigraph G. The posteriors of player j are self-consistent if and only if all cycle equations associated with cycles in G_j are satisfied. Similarly, the posteriors of all players are consistent with a common prior when all cycle equations corresponding to the cycles in G are satisfied. In particular, the self-consistency of player j is automatic when G_j is acyclic. Consistency always holds when G is acyclic, regardless of any probabilistic information. There is a simple formula to check for the acyclicity of G_j , and another formula to check for the acyclicity of G.
This is a joint paper with Luciana C. Fiorini.
Everyone welcome!

Speaker: Nina Anchugina & Arkadii Slinko
Affiliation: The University of Auckland
Title: Two talks see titles below
Date: Thursday, 7 May 2015
Time: 5:00 pm
Location: Room 260-325, Owen Glenn Building

1. Speaker: Nina Anchugina.
Title: A simple framework for the axiomatization of exponential and quasi-hyperbolic discounting
Time: 30 min.

Abstract: The main goal of this talk is to investigate which normative requirements, or axioms, lead to exponential and quasi-hyperbolic forms of discounting in inter-temporal decision-making. Exponential discounting has a well-established axiomatic foundation originally developed by Koopmans (1960) with subsequent contributions by several other authors. Hayashi (2003) and Olea and Strzalecki (2014) axiomatize quasi-hyperbolic discounting. In this talk we provide an alternative foundation for exponential and quasi-hyperbolic discounting, with simple, transparent axioms and relatively straightforward proofs. Using techniques by Fishburn (1982) and Harvey (1986), we show that Anscombe and Aumann’s (1963) version of Subjective Expected Utility (SEU) theory can be readily adapted to axiomatize the aforementioned types of discounting, in both finite and infinite horizon settings.

This is a joint work with Matthew Ryan.

2. Speaker: Arkadii Slinko
Title: Condorcet Domains and Median Graphs
Time 30 min

Abstract: A set of linear orders D is called a Condorcet domain if every profile composed from preferences from D has acyclic majority relation. Maximal Condorcet domains have been a subject of intense investigation, especially by Fishburn and Monjardet. Demange (2012) generalized the classical single-crossing property to the intermediate property on median graphs and proved that for every intermediate profile R with an odd number of voters on a median graph G there is a representative voter whose preference order coincides with the majority relation. We complement her result with proving that the linear orders of any profile which is intermediate on a median graph form a Condorcet domain. We prove that for any median graph there exists a profile that is intermediate with respect to that graph and that one may need at least as many alternatives as vertices to construct such a profile. We provide a polynomial-time algorithm to recognise whether or not a given profile is intermediate with respect to some median graph.

This is a joint work with Adam Clearwater (The University of Auckland) and Clemens Puppe (Karlsruhe Institute of Technology, Germany).

Everyone welcome!