[EM] Recursion for the Daring!

[Forest Simmons]

When trying to explain a multistep procedure, sooner or later you reach the
point where the pattern should be evident to your audience ... that's the
point where you say, "... and so forth."

That's fine for informal interactive communication like this EM List, but
when you need to pin down unambiguosly exactly what you mean ... for
example, when giving instructions to a computer (or writing a proposal into
law), ... that's where recursion may be the ideal tool for the job.

The case I'm thinking about now is our Q&D/C approximation to TACC, ... can
we improve the approximation while preserving the succinct concision?

Here's the Q&D version:

Elect the "best" candidate that pairwise defeats the "worst" Smith
candidate.

A concise eleven word description of an amazingly burial resistant
Condorcet method.

I purposely left "best" and "worst" undefined, because we're still
exploring the possibilities. In TACC (Total Approval Chain Climbing)
"worst" refers to least total approval .... the "climbing" is climbing up a
List of candidates previously sorted into approval order ... preferably
explicit approval, but implicit approval is next best ... the best we can
do when restricted to the Universal Domain  rules of RCV, i.e. ordinal
preference information only. [It's an ironically sad oxymoron ... " ..
restricted to Universal ..."]

There is nothing corresponding to "best" in TACC, because TACC just keeps
on going until there is only one candidate left.  In Q&D we have been using
the same score system for "best" and "worst" ... highest "basic score"* and
lowest basic score, respectively. But there is no compelling reason for
adhering slavishly to that custom. In fact, this opening is our big fat
opportunity for incorporating recursion into Q&D!

*["Basic score" is a flexible version of implicit approval.  It means the
number of ballots on which the candidate being scored is ranked above at
least one candidate. The flexibility comes with the option of recalculating
the score when restricting to a subset, like the Smith set, of continuing
(i.e. un-disqualified) candidates.]

So here's a first draft of our recursive version of Q&D:

Elect the "recursively determined best" candidate that pairwise defeats the
"worst" Smith candidate.

The word count goes up from eleven to thirteen ... not too shabby!

Nitty gritty gory details coming soon!

[But now that you know how recursion works, you probably don't need me to
spell it out.]

-Forest

El lun., 10 de ene. de 2022 9:51 p. m., Forest Simmons <
forest.simmons21 at gmail.com> escribió:

> Warning ... recursion is like spicy Thai or Mexican food ... if you are
> not used to it, it can make your head explode!
>
> But when safely in the hands of responsible people it can give valuable
> information about conceptual complexity.
>
> Recursively defined procedures, while maximally succinct and conceptually
> simple (in the minds of people used to them)  are often computationally
> "hard", involving an impractically large number of simple, but highly
> repetitive operatioms.
>
> So we have a dilemma: how do we shield the tender minded from recursive
> descriptions while sharing their beautiful simplicity with the initiated.
>
> In ancient times secretive, exclusive societies like the Pythagoreans or
> the Masons organized according to various levels of what might be called
> "security clearance" in modern parlance.
>
> In modern schools, prerequisites  must be met before admission to an
> advanced course.
>
> On the EM list, inquisitive but sensible people just give up if the going
> gets too tough too soon; "Obviously this post was not intended for the
> general public."
>
> I'm going to try to make this simple enough that someone with no previous
> experience with recursion can see what is going on.
>
> The tricky (and clever) part of recursion is judicious use of what seems
> to be circular definition, but is in reality a kind of convergent inwardly
> spiraling reasoning.
>
> If your first grade teacher asked you to define the number six, you might
> say that it was the number just before seven, which would be true, but not
> as helpful as saying the number just after five.
>
> In the seventh grade a smart alec student might say that six is the
> number  that you get if you subtract it from 18 and divide the result by
> two.
>
> This answer would highly displease your third grade teacher as an example
> of circular definition. But the 7th grade algebra teacher would say, "This
> kid has talent."
>
> If you do a directed graph of the function
>
> x---->f(x), where f(x) =(18-x)/2,
>
> the picture you get is a spiral flow converging to the number 6 on the
> number line.  If you graph y=f(x) on an (x, y) coordinate system and
> connect points (x, y) to (y, f(y)) with arrows, you with get a "web"
> diagram of the same underlying spiral structure converging to the point
> (6,6) on the graph of y=x.
>
> So apparent circularity in definition may lead unambiguously (in some
> cases) to a well-defined number.
>
> In the algebra example, it is sufficient for the slope of the graph of f
> to be strictly less than one, in absolute value.
>
> For recursively defined procedures it is sufficient that any self
> referential part of the procedure be restricted to a set of lesser
> cardinality than the "main" set being dealt with.
>
> If you want to recursively define a procedure on a set of size n,
> temporarily remove a member of the set. Then "recursively"apply the
> procedure to the smaller set of size (n-1), and then re-incorporate the
> member that was removed.
>
> For example, to alphabetize a random list of words, remove any word from
> the list, recursively alphabetize the rest of the list, and then finally
> place the word that was removed into its proper place.
>
> This is not in any way an efficient procedure, but it is amenable to
> logically precise, concise, conceptually simple verbiage.
>
> Even the lexicographical order itself that is needed for placing the
> temporarily removed (last) word into its proper place is easily defined
> recursively:
>
> (For simplicity assume no other alpha numeric characters like hyphens,
> spaces, numerals, etc.)
>
> Find the first place (from the left end) of the two words where they do
> not have the same letter. If that place is at the first letter of the word,
> then precedence goes to the word whose initial letter is closer to the
> front of the alphabet. Otherwise, temporarily remove the common initial
> string of letters and apply the procedure recursively to the remaining
> sub-strings of letters.
>
> To Be Continued....
>
>
>
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20220111/d896855a/attachment-0001.html>