The newly formed Centre for Mathematical Social Sciences at the University of Auckland (of which I am a founding member) recently held its first event, a workshop on Algorithmic Aspects of Game Theory and Social Choice. There were some interesting talks and some good colleagues from overseas attended. I enjoyed it very much. Thanks to all the participants especially those coming from afar.
Category Archives: Research
Recent talks I have given
“Higher order asymptotics from multivariate generating functions” was presented at University of Pennsylvania, Rutgers University, University of California Berkeley and University of California Davis.
“Measuring manipulability of voting rules” was presented at University of Rochester and Union College.
These and others can be found on my archive of talks.
Science and NZ prosperity
The NZ Institute’s discussion paper Standing on the Shoulders of Science and slides from a talk by Philip McCann (which I saw on Hard News) have come my way today. It seems that more urgency is being felt by decision-makers in NZ about the poor productivity growth of recent decades, and science R&D is being promoted more. I hope something actually happens, because these problems have been known for a long long time.
DIMACS 20th birthday
Today I attended the 20th birthday celebrations for DIMACS at Rutgers University. There were some nice talks: Ron Graham on addressing in graphs; Peter Winkler on combinatorics in statistical physics, Joan Feigenbaum on approximate privacy, Michael Trick on the DIMACS Challenges, Richard Karp on implicit set algorithms, Eva Tardos on games in networks, etc. There was also an interesting panel discussion on education (de facto national standards coming in the US are strongly opposed by some here, because of the de-emphasizing of discrete math topics) and industry (the environment is much meaner now, and managers are loath to fund projects without clearly stated benefits to the company). This was my first visit and I can see now why DIMACS has been so successful. Thanks to all the organizers and speakers for a very enjoyable day.
Note: another report by Muthu
The other blog
I have started a WordPress installation for the recently formalized Mathematical Social Sciences group here at UoA. It contains our seminar information among other things. Subscribe today!
Asymptotic expansions of oscillatory integrals with complex phase
Robin Pemantle and I have just submitted this paper, which fills in some gaps from our previous work. There is still more to be done along these lines – asymptotics of integrals whose stationary points are not isolated or are at a vertex of a simplex, for example, requires more work.
Abstract: We consider saddle point integrals in d variables whose phase function is
neither real nor purely imaginary. Results analogous to those for Laplace (real
phase) and Fourier (imaginary phase) integrals hold whenever the phase function
is analytic and nondegenerate. These results generalize what is well known for
integrals of Laplace and Fourier type. The method is via contour shifting in
complex d-space. This work is motivated by applications to asymptotic
enumeration.
New measures of the difficulty of manipulation of voting rules
Reyhaneh Reyhani, Geoffrey Pritchard and I have just submitted this to a special issue of Journal of Autonomous Agents and Multi-Agent Systems concerning computational social choice.
Abstract: We introduce new measures of manipulability of anonymous voting rules
and argue for their superiority over some commonly used measures. We give a sim-
ple common framework that describes these measures and connects them to recent
literature. We discuss their computation and present numerical results that allow for
comparison of various common voting rules.
The joys of conference organization
I have been the main organizer for 4ICC currently being held in Auckland. This is my first job of organizing a meeting of this type. I started 14 months ago and the last few months have been extremely busy. Before doing this I had an idea of the main tasks: finding invited speakers, booking rooms, budgeting, etc. All these are quite onerous, but predictably so, and I did get help with some of them. What surprised me was this kind of stuff (which will no longer surprise me if I ever forget myself enough to do it again): at the first coffee break on Monday morning, participants used the souvenir coffee mugs in their conference bags, instead of the cups supplied, so the coffee ran out halfway through; the travel agent I was forced to use made 4 errors with booking invited speaker accommodation, so that speakers emailed me late on Sunday night worried about where they were going to spend Friday night; having to give the same information over and over again to people who could have read it on the conference website; worrying about losing people on the excursion; catching a cold and having no time to rest; in other words, being ultimately responsible for everything! Overall, the last two weeks had more stress than the preceding 12 months, and I am filled with admiration for people who do this for a living.
The conference itself seemed to go well overall. Thanks to all who helped with the organization – I could not have done it without you. And no thanks to that travel agent.
Manipulation can be a good thing
I have studied strategic manipulation of voting rules in some detail, and it never occurred to me to question the basic assumption that manipulation (misrepresentation of a group of voters of their sincere preferences, thereby achieving a better outcome than if they had voted sincerely) is bad. It is unavoidable by Gibbard-Satterthwaite. A large number of papers have been devoted to trying to minimize its occurrence.
However, some people are now arguing that it might be a good thing, for example papers by Aki Lehtinen and by Keith Dowding and Martin van Hees. The reasons include maximization of total social welfare (utilitarian argument) and improvements to the democratic process through upskilling of voters. It is not that often that I find such a basic assumption questioned, and it is very refreshing. Most of the mathematical techniques that I know can be used to analyse this new framework, and I will definitely be looking at doing so.
Permutation Patterns 2008
I went to this conference in Dunedin just for the first two days – it ends on 20 June.
A lot of good generating functions arise from the enumeration of permutations avoiding certain patterns. The plenary talk by Mireille Bousquet-Melou (whose talks are always a model of clarity) discussed the systematic solution of various functional equations arising from fairly straightforward recursive decompositions of these combinatorial classes. As well as the by now traditional kernel method, she discussed the “algebraic kernel method” which uses symmetries of the kernel function to derive a system of equations that is amenable to simplification.
I have been thinking for a long time about the need for a better presentation of the kernel method in these contexts. Perhaps this will finally inspire me to write something.