Category Archives: Research

Southern Hemisphere Summer Scholarships

(From University of Auckland science faculty . Anyone seriously interested in working with me should contact me directly. I have several ideas available).

The Faculty has the opportunity to access 100 Summer Scholarships funded by the university (as opposed to Faculty funds) for special categories of students–this includes international students. The Faculty management team has agreed that we should use our recent Northern Hemisphere summer scholarship experience to try to win up to 20 of these scholarships for international students to come over the NZ summer.

The terms of the scholarships will be as for the normal Summer Scholarship: targeting final year undergraduate students; $5000, plus $1000 available for expenses to the host. No costs to the hosting Department or supervising academic are incurred. The student is responsible for all fares, accommodation, etc. Scholarship to be paid as $3500 on arrival, $1500 on presentation of final report. We are preparing an advertising poster for (southern hemisphere) universities now.

Our Northern Hemisphere scholarship experience showed that these scholarships are extremely useful for academics wishing to enhance links with overseas groups, by providing funding for a student from a collaborating group to come to New Zealand for a short period.

AAMAS 2012

It looks as though I will be a (junior) PC member (= referee/reviewer).

Details:

AAMAS will be co-located with EC next year, June 4-8, 2012, Valencia, Spain.  Among other topics the CFP includes

4. Social choice theory
5. Voting protocols

Electronic Abstract Submission: October 7, 2011 (11:59 PM HST)
Full Paper Submission: October 12, 2011 (11:59 PM HST)

more info at
http://aamas2012.webs.upv.es

Call for papers CATS 2012

I am a PC member for the first time.

—

Call for Papers

CATS 2012 — Computing: The Australasian Theory Symposium
Melbourne, Australia, January 30-February 2, 2012
http://cats.it.usyd.edu.au/

The 18th Computing: The Australasian Theory Symposium (CATS) will be
held in Melbourne, Australia, in January/February 2012. CATS is an
annual conference held in the Australia-New Zealand region, dedicated
to theoretical computer science.

Authors are invited to submit papers that present original and
unpublished research on topics related to theoretical aspects of
computer science, including (but not limited to):
– algorithms and data structures
– algorithmic game theory
– combinatorial optimization
– computability
– computational complexity theory
– computational geometry
– graph theory and combinatorics
– parallel and distributed algorithms
– logic and type systems
– program derivation, analysis, and verification
– theory of programming languages

Important dates:
– Paper submission deadline: Monday 15 August, 2011
– Acceptance notification: Monday 10 October, 2011
– Final version due: Monday 7 November, 2011
– Conference dates: Monday 30 January – Thursday 2 February, 2012

The proceedings of this event will be published by the Australian
Computer Society (ACS) in the CRPIT Series (http://crpit.com/), and
will also appear in the ACM digital library. CATS 2012 is part of the
Australasian Computer Science Week (ACSW), an international annual
conference event, supported by the Computing Research and Education
Association (CORE) in Australia. ACSW 2012 is hosted by RMIT
University in Melbourne, Australia.

For more information please visit http://cats.it.usyd.edu.au/
Contact: Julian Mestre <cats2012@easychair.org>

The Complexity of Safe Manipulation under Scoring Rules

This paper will appear in Proceedings of IJCAI ’11 and be presented at the conference in Barcelona in July.

Abstract: Slinko and White have recently introduced a new model of coalitional
manipulation of voting rules under limited communication, which they
call {em safe strategic voting}. The computational aspects of this
model were first studied by Hazon and Elkind, who provide
polynomial-time algorithms for finding a safe strategic vote under
$k$-approval and the Bucklin rule. In this paper, we answer an open
question of Hazon and Elkind by presenting a polynomial-time algorithm
for finding a safe strategic vote under the Borda rule. Our results for
Borda generalize to several interesting classes of scoring rules.

Asymptotics of coefficients of multivariate generating functions: improvements for multiple points

This has been uploaded to arXiv and submitted to Online Journal of Combinatorics. Interestingly, it was rejected by Electronic Journal of Combinatorics without refereeing, as being out of scope. It improves on previous work mainly by giving explicit formulae. The main work associated with this paper is the SAGE implementation by Alex Raichev. Computation of higher order asymptotic expansions by hand is essentially impossible, hence the paucity of numerical or explicit results  in published papers.

Download author copy

COMSOC Days 0, 1

NOTE: The entire conference report is available as a guest post on Noam Nisan’s blog.

I am in Dusseldorf for COMSOC 2010. The LOGICC tutorial day was yesterday and the first full day today. It is a good way to meet many people in a short time. The organizers are doing a good job overall. All talks today had a good or very good standard of presentation. The most interesting talks in my opinion:

Nicholas Tideman: after long experience, claims that spatial models are the best for modelling real voter behaviour. Discussed difficulties of obtaining real data and had plenty of computational problems to offer the audience, often involving Gaussian quadrature. Challenged us to generate fake elections that he could not distinguish from real ones.

Gabrielle Demange: has a new ranking method which she has characterized axiomatically. Ranking methods focus attention of the rankers, and there is a dynamic process which converges in some cases.

Tyler Lu: interpolate between social choice and full personalized recommendations. Isomorphic to theory of fully proportional representation. Hardness results, greedy algorithms, approximation algorithms.

Matthew Jackson: in experiments, if you offer people $100 now or $200 in 2 years, most take the $100. But if you offer $100 in 6 years or $200 in 8 years, they take the $200. This is inconsistent with standard rational models. Main idea is that perhaps each person has several “personalities”, some with more patience than others. He showed that in that case, this kind of inconsistency is basically inevitable (impossibility result like Arrow, but easier to prove).

Toby Walsh is giving a ridiculously large number of talks. One good idea he had is a standard library of benchmark election data for testing algorithms.

Plenty of complexity and especially parametrized complexity results.

The probability of safe manipulation

This paper (joint with Reyhaneh Reyhani) will be presented at COMSOC 2010. It deals with the concept of “safe manipulation”, whereby an agent can attempt to manipulate the result of an election without risk, provided that voters of other preferences vote sincerely but irrespective of the number of like-minded voters that also try to vote strategically. It was introduced by Slinko and White in COMSOC 2008.

Abstract: The concept of safe manipulation has recently been introduced by Slinko and White. We show how to compute the asymptotic probability that a safe manipulation exists for a given scoring rule under the uniform distribution on voting situations (the so- called Impartial Anonymous Culture). The technique used is computation of volumes of convex polytopes. We present explicit numerical results in the 3-candidate case.

Download author copy

An interesting new Mahonian permutation statistic

While studying the standard method for random permutation generation I discovered a function whose distribution on a uniformly random permutation of fixed length is the same as that of the number of inversions. Such things are called Mahonian permutation statistics.

This statistic appears to be new, but this is not as easy to show as I would like. After several attempts to find out by reading papers, asking experts and doing database searches, I concluded that it probably was and submitted the paper to the arXiv and for publication. Almost immediately I got email from Dennis White at University of Minnesota pointing out a connection with a paper by him and Galovich in 1996. This raises some questions: how much responsibility do we have in the modern research environment to check novelty? why is there no standard database of numerical values of all important functions, and how do we achieve one?

Abstract: The standard algorithm for generating a random permutation gives rise to an obvious permutation statistic $stat$ that is readily seen to be Mahonian. We give evidence showing that it is not equal to any previously published statistic. Nor does its joint distribution with the standard Eulerian statistics $des$ and $exc$ appear to coincide with any known Euler-Mahonian pair.
A general construction of Skandera yields an Eulerian partner $ska$ such that $(ska, stat)$ is equidistributed with $(des, maj)$. However $ska$ itself appears not to be a known Eulerian statistic.
Several ideas for further research on this topic are listed.

Download author copy

Recommending research articles

Challenge for AGT researchers: come up with a good mechanism to help the most noteworthy papers get the most notice!

As a start, Noam Nisan is trying an experiment to get people to recommend interesting papers in Algorithmic Game Theory/Economics. Journals no longer serve well in disseminating results quickly – is it possible to dispense with them altogether by using another way to give a signal of quality and noteworthiness?

I have doubts that this particular proposal will succeed, because of incentive compatibility problems. When we cite a paper when writing our own, it is usually taken as a recommendation (negative citations do occur, but relatively infrequently I guess). If we don’t cite it, a referee or the author may notice and our reputation will suffer. If we do cite it, our paper is probably more likely to get published. So there are some incentives to participate in that form of “recommendation”. However, recommending papers via Noam’s proposed scheme doesn’t seem to me to have as strong an incentive to participate. Who has the time to do it, if the recognition obtained for good recommendations is so low? Still, it’s good to have a first step, and I am sure with enough time and money a nice system could be devised that cuts out the for-profit journal publishers.

Turing Centenary

2012 is the centenary of the birth of Alan Turing. Every time I read about him I find some new and amazing thing he has done, for example running a marathon in well under 3 hours. For someone who died at about the age I am now, he achieved an enormous amount.

Many activities to commemorate him and his contributions are being planned and a website giving a good overview is available.