<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
</head>
<body dir="ltr">
<div id="divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Helvetica,sans-serif;" dir="ltr">
<p style="margin-top:0;margin-bottom:0"><span>Owen writes:</span></p>
<p style="margin-top:0;margin-bottom:0"><span><br>
</span></p>
<p style="margin-top:0;margin-bottom:0"><span>"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."</span></p>
<p style="margin-top:0;margin-bottom:0"><span><br>
</span></p>
<p style="margin-top:0;margin-bottom:0"><span>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. <br>
</span></p>
<p style="margin-top:0;margin-bottom:0"><span><br>
</span></p>
<p style="margin-top:0;margin-bottom:0"><span>Marcus </span><br>
</p>
</div>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> Friam <friam-bounces@redfish.com> on behalf of Owen Densmore <owen@backspaces.net><br>
<b>Sent:</b> Saturday, December 29, 2018 11:05:58 AM<br>
<b>To:</b> The Friday Morning Applied Complexity Coffee Group<br>
<b>Subject:</b> Re: [FRIAM] 2019 - The end of Trumpism</font>
<div> </div>
</div>
<div>
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">
This reminded me of a seriously ancient post on Arrow's theorem, see forward below.</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">
<br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">
I particularly liked the examples in </div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">
<a href="http://www1.udel.edu/johnmack/frec444/444voting.html">http://www1.udel.edu/johnmack/frec444/444voting.html</a> </div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">
showing the surprises that can pop up. The first showed the example where the majority favorite was the most disliked!</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">
<br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">
That led me, when I first arrived here in 2002 after the 2000 SFI Complexity summer school, to work my way through:</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">
How to Solve It: Modern Heuristics</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">
Zbigniew Michalewicz & David B. Fogel</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">
"Stochastic Processes" certainly seemed a bit magic.</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">
<br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">
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:</div>
</div>
</div>
</div>
</div>
<blockquote style="margin:0 0 0 40px; border:none; padding:0px">
<div>
<div>
<div>
<div>
<div class="x_gmail_default"><font color="#000000" face="arial, helvetica, sans-serif"><a href="http://backspaces.github.io/as-app3d/models/?ants">http://backspaces.github.io/as-app3d/models/?ants</a></font></div>
</div>
</div>
</div>
</div>
<div>
<div>
<div>
<div>
<div class="x_gmail_default"><font color="#000000" face="arial, helvetica, sans-serif"><a href="http://backspaces.github.io/as-app3d/models/?tsp">http://backspaces.github.io/as-app3d/models/?tsp</a></font></div>
</div>
</div>
</div>
</div>
</blockquote>
<font color="#000000" face="arial, helvetica, sans-serif"><span class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; color:rgb(0,0,0)">(The TSP stops after 500 steps w/o improvement. Open console for info.)</span><br>
</font>
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div dir="ltr">
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; font-size:small; color:rgb(0,0,0)">
<br>
</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; font-size:small; color:rgb(0,0,0)">
-- Owen</div>
<div class="x_gmail_default" style="font-family:arial,helvetica,sans-serif; font-size:small; color:rgb(0,0,0)">
<div dir="ltr" style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<br class="x_gmail-Apple-interchange-newline">
---------- Forwarded message ---------<br>
From: <strong class="x_gmail_sendername" dir="auto">Owen Densmore</strong> <span dir="ltr"><<a href="mailto:owen@backspaces.net">owen@backspaces.net</a>></span><br>
Date: Thu, Dec 3, 2009 at 6:06 PM<br>
Subject: Arrow's Impossibility Theorem<br>
To: Roger Critchlow <<a href="mailto:rec@elf.org">rec@elf.org</a>>, Nicholas Thompson <<a href="mailto:nickthompson@earthlink.net">nickthompson@earthlink.net</a>>, Jim Gattiker <<a href="mailto:j.gattiker@googlemail.com">j.gattiker@googlemail.com</a>>, Chip
Garner <<a href="mailto:chip@garnertotalenergy.com">chip@garnertotalenergy.com</a>>, Frank Wimberly <<a href="mailto:wimberly3@gmail.com">wimberly3@gmail.com</a>><br>
Cc: Owen Densmore <<a href="mailto:owen@backspaces.net">owen@backspaces.net</a>><br>
</div>
<br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">Here's a very old post (Dec 03) from the FRIAM list that discusses </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">Arrow's Impossibility Theorem. It proves the impossibly of uniquely </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">resolving social preferences from individual preferences given more </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">than two things to choose among.</span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif"> -- Owen</span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">During the last Friam, we got talking about voting and Arrow's </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">Impossibility Theorem came up. It basically discusses anomalies in </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">voting when there are more than two choices being voted upon.</span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">The result depends strongly on how the votes are tallied. So for </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">example, in our last election, due to having three candidates, we </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">entered the Arrow regime. But "spoilers" like Ralph are not the only </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">weirdness.</span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">The html references below have interesting examples, and the pdf </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">reference is a paper by SFI's John Geanakoplos who gave a public </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">lecture last year.</span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">"Fair voting" schemes are getting some air-time now a-days. There are </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">several forms, but the most popular I think is that you basically rank </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">your candidates in order of preference, the "top-most" being your </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">current vote. There are several run-offs which eliminate the poorest </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">performer and let you vote again, now with the highest of your ranks </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">still available. This insures you always have a vote if you want </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">one. This would have won the election here for Gore, for example, </span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">presuming the Nader votes would favor Gore.</span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">Various web pages with examples:</span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif"> </span><a href="http://www.udel.edu/johnmack/frec444/444voting.html" rel="noreferrer" target="_blank" style="font-family:Arial,Helvetica,sans-serif">http://www.udel.edu/johnmack/frec444/444voting.html</a><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif"> </span><a href="http://www.sjsu.edu/faculty/watkins/arrow.htm" rel="noreferrer" target="_blank" style="font-family:Arial,Helvetica,sans-serif">http://www.sjsu.edu/faculty/watkins/arrow.htm</a><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif"> </span><a href="http://www.math.upenn.edu/~kazdan/210/voting/notes_on_arrow.html" rel="noreferrer" target="_blank" style="font-family:Arial,Helvetica,sans-serif">http://www.math.upenn.edu/~kazdan/210/voting/notes_on_arrow.html</a><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">Three proofs by John Geanakoplos</span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif"> </span><a href="http://cowles.econ.yale.edu/P/cd/d11a/d1123-r.pdf" rel="noreferrer" target="_blank" style="font-family:Arial,Helvetica,sans-serif">http://cowles.econ.yale.edu/P/cd/d11a/d1123-r.pdf</a><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">Owen Densmore 908 Camino Santander Santa Fe, NM 87505</span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
<a href="mailto:owen@backspaces.net" target="_blank" style="font-family:Arial,Helvetica,sans-serif">owen@backspaces.net</a><span style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif"> Cell: 505-570-0168 Home: 505-988-3787</span><br style="color:rgb(34,34,34); font-family:Arial,Helvetica,sans-serif">
</div>
</div>
<br>
<div class="x_gmail_quote">
<div dir="ltr">On Sat, Dec 29, 2018 at 6:31 AM Eric Smith <<a href="mailto:desmith@santafe.edu">desmith@santafe.edu</a>> wrote:<br>
</div>
<blockquote class="x_gmail_quote" style="margin:0px 0px 0px 0.8ex; border-left:1px solid rgb(204,204,204); padding-left:1ex">
Steve, <br>
<br>
I wonder if there is a game theory problem to be worked on here.<br>
<br>
Referring to your statement: <br>
<br>
>> 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)… <br>
<br>
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.<br>
<br>
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?<br>
<br>
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.<br>
<br>
Eric<br>
</blockquote>
</div>
</div>
</div>
</div>
</div>
</div>
</body>
</html>