From time to time EM contributers have described simple ways to construct
the Smith set.
Here's another one that just occurred to me:
- Make a list L1 of the candidates in any order ... the order they appear
on the ballot will do.
- Reverse L1 to get L2.
- Bubble Sort each of these two lists pairwise (separately) to get sorted
lists SL1 and SL2, respectively.
- The Smith Set is the smallest solid coalition contained in both sorted
lists.
- This set is easily found by placing the sorted lists side- by-side and
slowly lowering a line until the same set of candidates is above the line
in both lists.
- More systematically ... find the tops t1 and t2 of each list in the
other list ... then form a beatpath that starts at t1 completes a cycle
through the Smith set by continuing down to t2 ... then connecting to t2 at
the top of the second list ... and continuing down that list to t1 ...
thereby completing a beattcycle through the Smith Set.
- Check that this set is the Smith Set by starting at any point of the
beatcycle we just constructed .... making one complete circuit through it
... and then continuing down either list SL1 or SL2 to extend the beatpath
to the rest of the candidates.
In summary... starting at any candidate in our "top cycle" we get a
beatpath through all of the other candidates ... therefore our top cycle
contains the Smith set, defined as the smallest set of candidates all of
whom have beatpaths to the remaining candidates.
It is clear that no smaller solid coalition would include both t1 and t2
... which must be included in Smith or they could not bubble sort to the
top.
It sounds complicated ... but it's easy to do... just list the candidates
in the same order they appear on the ballot ... then reverse the list to
get a second list ... then bubble sort both lists.
If both lists have the same top candidate t1=t2, then that candidate is the
CW. If not find t1 in the second list and t2 in the first list ... the
beatpath from t1 to t2 in the first list concatenated with the beatpath
from t2 to t1 in the second list is the "top cycle" we're looking for.
-Forest
>From time to time EM contributers have described simple ways to construct
the Smith set.
Here's another one that just occurred to me:
1. Make a list L1 of the candidates in any order ... the order they appear
on the ballot will do.
2. Reverse L1 to get L2.
3. Bubble Sort each of these two lists pairwise (separately) to get sorted
lists SL1 and SL2, respectively.
4. The Smith Set is the smallest solid coalition contained in both sorted
lists.
5. This set is easily found by placing the sorted lists side- by-side and
slowly lowering a line until the same set of candidates is above the line
in both lists.
5. More systematically ... find the tops t1 and t2 of each list in the
other list ... then form a beatpath that starts at t1 completes a cycle
through the Smith set by continuing down to t2 ... then connecting to t2 at
the top of the second list ... and continuing down that list to t1 ...
thereby completing a beattcycle through the Smith Set.
6. Check that this set is the Smith Set by starting at any point of the
beatcycle we just constructed .... making one complete circuit through it
... and then continuing down either list SL1 or SL2 to extend the beatpath
to the rest of the candidates.
In summary... starting at any candidate in our "top cycle" we get a
beatpath through all of the other candidates ... therefore our top cycle
contains the Smith set, defined as the smallest set of candidates all of
whom have beatpaths to the remaining candidates.
It is clear that no smaller solid coalition would include both t1 and t2
... which must be included in Smith or they could not bubble sort to the
top.
It sounds complicated ... but it's easy to do... just list the candidates
in the same order they appear on the ballot ... then reverse the list to
get a second list ... then bubble sort both lists.
If both lists have the same top candidate t1=t2, then that candidate is the
CW. If not find t1 in the second list and t2 in the first list ... the
beatpath from t1 to t2 in the first list concatenated with the beatpath
from t2 to t1 in the second list is the "top cycle" we're looking for.
-Forest
