[FRIAM] 2019 - The end of Trumpism

[Owen Densmore]

This reminded me of a seriously ancient post on Arrow's theorem, see
forward below.

I particularly liked the examples in
    http://www1.udel.edu/johnmack/frec444/444voting.html
showing the surprises that can pop up. The first showed the example where
the majority favorite was the most disliked!

That led me, when I first arrived here in 2002 after the 2000 SFI
Complexity summer school, to work my way through:
    How to Solve It: Modern Heuristics
    Zbigniew Michalewicz & David B. Fogel
"Stochastic Processes" certainly seemed a bit magic.

The NFL paper certainly gave me some doubts but it seemed amazing how
effective GA's, Ant Algorithms, and so on were .. at least in their own
domain. Here are two:

http://backspaces.github.io/as-app3d/models/?ants
http://backspaces.github.io/as-app3d/models/?tsp

(The TSP stops after 500 steps w/o improvement. Open console for info.)

   -- Owen

---------- Forwarded message ---------
From: Owen Densmore <owen at backspaces.net>
Date: Thu, Dec 3, 2009 at 6:06 PM
Subject: Arrow's Impossibility Theorem
To: Roger Critchlow <rec at elf.org>, Nicholas Thompson <
nickthompson at earthlink.net>, Jim Gattiker <j.gattiker at googlemail.com>, Chip
Garner <chip at garnertotalenergy.com>, Frank Wimberly <wimberly3 at gmail.com>
Cc: Owen Densmore <owen at backspaces.net>


Here's a very old post (Dec 03) from the FRIAM list that discusses
Arrow's Impossibility Theorem.  It proves the impossibly of uniquely
resolving social preferences from individual preferences given more
than two things to choose among.

    -- Owen

During the last Friam, we got talking about voting and Arrow's
Impossibility Theorem came up.  It basically discusses anomalies in
voting when there are more than two choices being voted upon.

The result depends strongly on how the votes are tallied.  So for
example, in our last election, due to having three candidates, we
entered the Arrow regime.  But "spoilers" like Ralph are not the only
weirdness.

The html references below have interesting examples, and the pdf
reference is a paper by SFI's John Geanakoplos who gave a public
lecture last year.

"Fair voting" schemes are getting some air-time now a-days.  There are
several forms, but the most popular I think is that you basically rank
your candidates in order of preference, the "top-most" being your
current vote. There are several run-offs which eliminate the poorest
performer and let you vote again, now with the highest of your ranks
still available.  This insures you always have a vote if you want
one.  This would have won the election here for Gore, for example,
presuming the Nader votes would favor Gore.

Various web pages with examples:
  http://www.udel.edu/johnmack/frec444/444voting.html
  http://www.sjsu.edu/faculty/watkins/arrow.htm
  http://www.math.upenn.edu/~kazdan/210/voting/notes_on_arrow.html
Three proofs by John Geanakoplos
  http://cowles.econ.yale.edu/P/cd/d11a/d1123-r.pdf

Owen Densmore          908 Camino Santander       Santa Fe, NM 87505
owen at backspaces.net    Cell: 505-570-0168         Home: 505-988-3787

On Sat, Dec 29, 2018 at 6:31 AM Eric Smith <desmith at santafe.edu> wrote:

> Steve,
>
> I wonder if there is a game theory problem to be worked on here.
>
> Referring to your statement:
>
> >> Arrow's Impossibility is real but no more significant IMO than the
> real-world ambiguities and paradoxes introduced by practical realities such
> as voter suppression and fraud, system hacking and mechanical errors (e.g.
> hanging chads)…
>
> The Impossibility Theorem has the character of a case-existence proof: for
> any algorithm, there is a case of voter preferences for which that
> algorithm produces an unwanted outcome.  In the sense of only counting
> cases, it reminds me of no-free-lunch theorems: for any algorithm that is
> fast to solve one problem of combinatorial search, there is some other
> problem for which it is slow.  However, the NFL _threorem_ — that no
> algorithm is any better than any other — depends on an appropriately
> symmetric search space and a suitable associated uniform measure over
> problems on that space.  If search and optimization are embedded in a
> larger dynamic where correlation between algorithms is allowed, there can
> be global better or worse approaches.  I don’t (as in every other area)
> have details and references ready in memory, but David Wolpert wrote some
> of his later papers on NFL addressing the ways it ceases to apply under
> changed assumptions.
>
> I wonder if anyone has done an analysis of Arrow Impossibility in a
> context of a kind of ecosystem of adversaries.  To game any algorithm,
> crucially with the outcome that not only _some_ voter is handled poorly,
> but that _a sufficiently large pool_ of voters is handled poorly that the
> algorithm is not best, requires arranging the preference case that violates
> the algorithm for suitably many voters.  Is this coordination problem
> harder for some preference-orders than for others?  Is there something akin
> to “canalization” in evolutionary biology, where some algorithms live
> further from the boundary of being collectively tipped into producing the
> wrong outcome than others?  Thus, are there measures of robustness for
> statistical violation of algorithms based on what happens in most cases
> rather than what happens in the worst case, as there are for spin-glass
> phase transition problems?
>
> Another thing it seems unlikely I will ever put time into being serious
> about.  Or maybe there is already a large standing literature that claims
> to have addressed this.
>
> Eric
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://redfish.com/pipermail/friam_redfish.com/attachments/20181229/ed59776b/attachment.html>