[FRIAM] 2019 - The end of Trumpism

[Marcus Daniels]

Owen writes:


"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."


GA's are not an effective way to solve NP-hard, high-dimensional constrained optimization problems (> 1000 variables).  Problems like distribution of shared resources.  For that you need algorithms designed to do it and a lot of brute force (see SCIP, CPLEX, etc).   In public and private organizations we see dimensional reduction by introduction of hierarchy.  Individualists (sic) pretend the shared resources aren't finite or think by taking as much ground as they can they can better control the shared resource -- that their hierarchy is the best one.


Marcus

________________________________
From: Friam <friam-bounces at redfish.com> on behalf of Owen Densmore <owen at backspaces.net>
Sent: Saturday, December 29, 2018 11:05:58 AM
To: The Friday Morning Applied Complexity Coffee Group
Subject: Re: [FRIAM] 2019 - The end of Trumpism

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<mailto: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<mailto:rec at elf.org>>, Nicholas Thompson <nickthompson at earthlink.net<mailto:nickthompson at earthlink.net>>, Jim Gattiker <j.gattiker at googlemail.com<mailto:j.gattiker at googlemail.com>>, Chip Garner <chip at garnertotalenergy.com<mailto:chip at garnertotalenergy.com>>, Frank Wimberly <wimberly3 at gmail.com<mailto:wimberly3 at gmail.com>>
Cc: Owen Densmore <owen at backspaces.net<mailto: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<mailto: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<mailto: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/dfaa97f4/attachment.html>