[EM] Hylland's theorem

[Kevin Venzke]

Hi Rob,

Rob Lanphier <roblan at gmail.com> a écrit :
> 
> Hi folks,
> 
> I've seen many references to "Hylland's theorem" in recent papers and other places, and
> yet, this theorem seems to be a partial mystery to the Internet, and no one has
> bothered to write a Wikipedia article about it:
> https://en.wikipedia.org/wiki/Hylland%27s_theorem
> 
> Way back in 2005, I found a discussion of "Hylland's theorem" (and "May's theorem") on
> the EM-list:
> http://lists.electorama.com/pipermail/election-methods-electorama.com//2005-January/thread.html#79759
> 
> That led me to this paper:
> "Strategy Proofness of Voting Procedures with Lotteries as Outcomes and Infinite Sets
> of Strategies" -- Aanund Hyllund -- January 1980
> 
> ...which seems to be archived here (among other places, I hope):
> 
> https://www.sv.uio.no/econ/personer/vit/aanundh/upubliserte-artikler-og-notater/Strategy%20Proofness%5B1%5D.pdf
> 
> Am I following the breadcrumbs properly?  Is there a different "Hylland" that deserves
> to have a theorem named after them?

All references seem to point to the 1980 paper, yes.

Markus' description in 2005 seems to refer specifically to a two-candidate situation,
and when he says "Hylland's theorem" it's possible to read it as only referring to the
finding he mentions:

>> However, Hylland proved that when there are only two candidates and
>> the used single-winner election method is strategyproof then the
>> result depends only on whether the individual voter strictly prefers
>> candidate A to candidate B, strictly prefers candidate B to candidate A
>> or is indifferent between candidate A and candidate B (Aanund Hylland,
>> "Strategy Proofness of Voting Procedures with Lotteries as Outcomes
>> and Infinite Sets of Strategies," University of Oslo, 1980).
>> 
>> Therefore, I interpret May's theorem in connection with Hylland's
>> theorem as follows [...]

The paper "Strategy-proof Cardinal Decision Schemes" (by Dutta, Peters, and Sen, 2007)
has this in the abstract:

>> We provide a new proof of Hylland's theorem which shows that the only strategy-proof
>> cardinal decision scheme satisfying a weak unanimity property is the random
>> dictatorship.

and inside one version of it:
(https://warwick.ac.uk/fac/soc/economics/staff/bdutta/publications/cardinalrev7.pdf)

>> [...] Hylland [9], in an important and regrettably unpublished paper, showed that
>> the random dictatorship result holds even if the decision scheme is allowed to use
>> cardinal information. In this paper, we have two main objectives. First, we provide
>> an alternative and considerably simpler proof of Hylland’s theorem.

The reference is still to the 1980 paper.

Wikipedia's discussion of it suggests another view of the significance:

>> Gibbard's theorem is itself generalized by Gibbard's 1978 theorem and Hylland's
>> theorem, which extend these results to non-deterministic processes, i.e. where the
>> outcome may not only depend on the agents' actions but may also involve an element
>> of chance.

> I would like to either flesh out the following wiki page, or delete it:
> https://electowiki.org/wiki/Hylland%27s_theorem

I'm not sure what we would say it is. It seems like when people use this term they
also clarify (at least somewhat) what they mean by it.

> I'm not sure what to do with the "Hylland free riding" section in the "Free riding"
> article, but that needs better citations:
> https://electowiki.org/wiki/Free_riding#Hylland_free_riding

The citations go to Markus' paper, in which the relevant reference is:

>> Aanund Hylland, Proportional Representation without Party Lists, pp. 126-153,
>> RATIONALITY AND INSTITUTIONS, eds. Raino Malnes and Arild Underdal, Scandinavian
>> University Press, Oslo, 1992

Hylland free riding seems unrelated to the 1980 paper or the theorem.

Kevin
votingmethods.net