Re: Atlantic Coast Regionals

On Apr 17, 12:13 am, Flo <Flo.Pfen...@xxxxxxxxxxxxxx> wrote:
It's simple and easy to replicate, which I like.   The part of the
algorithm that troubles me is that the seedings it provides are not
locally stable which is a property I think any good seedings should
have.  I call a set of seedings locally stable if there is no pair of
teams A and B such that A is seeded immediately below B and A would be
seeded ahead of B if the two teams were considered in isolation.  For
example, if the algorithm seeded Georgia 3 and Virginia 4 then the
seeds would be unstable because the algorithm would reverse the order
if they were the only two teams under consideration.

Question:  are the notions of locally stable seeds (no pair of
adjacent seeds should be swapped) and a globally stable seeding
algorithm (top down or bottom up yields the same results) mutually
exclusive?

well, yes.

Take this very hypothetical example with 13 teams (any odd number
greater than 1 will do, for even numbers just add one team that lost
everything and is consensus last seed):
Every team has played every other team exactly once, and the score was
15-10 in every game. No games outside this group of teams, no
historical strength record...
12 teams have consistent scores, i.e. you can order these teams
(linearly and uniquely) according to their results, and the 66 head-to-
heads are all according to this order.
Now odd team number 13 comes along, and it has wins against the 6 top
teams and losses against the 6 bottom teams.
Any locally stable algorithm will put team 13 either as the first seed
or as the last. And if you use this algorithm backwards (switching top
and bottom), you will get the opposite result. This example also
magnifies the problem in demanding local stability. Most people would
seed team 13 somewhere in the middle as good wins and bad losses
somewhat cancel.

This example is the 3-way-tie blown up to a ridiculous size. In
reality, a variant of it often happens with 3 teams and sometimes with
5, but probably never with 7 or more teams.

But it demonstrates that in a 3-way-tie where A>B is forced due to
sectional finish, and B>C and C>A in head-to-heads, maybe ACB is the
best choice as average of the possible three orders ABC, CAB, ACB,
even though ACB has two local instabilities.
At least in ACB, misseeding is limited to one seed per team, and the
other two seeding sets have the potential of getting C's seed wrong by
2 (if we agree that one of the three sets is correct, but you don't
know which one).

I would agree that one of ABC or CAB is correct. At this point I have
a difficult time accepting ACB as correct, though by the argument you
provide above it is a good approximation of the correct seeding.

I believe that seedings are valuable more for the order that they
apply to the teams than for the specific placement that is given --
i.e. D > E > F is more important than D = 2, E = 3, F = 4. Given this
perspective, I prefer measuring the misseeding by the number of ">"
relationships that are violated.
As an example, consider the 13 team example from above. Draw an arrow
from the winner to loser of each game. Now seed the teams and sort
them left to right. The score associated with the seeding is the
number of arrows that go right to left, and a low score indicates a
better/more accurate set of seeds. Under this metric either of the
locally stable options that seed the 13th team first or last will have
a score of 6 (the 13th team is ahead of 6 teams it should be below or
below 6 teams it should be ahead of). Any other option will have a
higher score, and seeding the 13th team perfectly in the middle as
argued above will have a score of 12.




Btw, the algorithm I proposed above would also get a different result
here...

Your proposed algorithm, if i understand it correctly, would seed the
top 5 teams and the bottom 5 teams before running into a 3 way tie
where 6 beat 7 beat the 13th team beat 6. Presumably those 3 teams
would be seeded according to their RRIs, though without knowing
exactly how that function is defined I am not sure what that order
would be.


As a related aside, several times it has come up that "if you run the
algorithm top to bottom -v- bottom to top the results change." I think
this is a misleading statement because, for the most part, any
algorithm for which this statement is true specifies a direction that
the seeding should be done in. By specifying the direction, the
algorithm is explicitly stating that it will systematically punish (or
reward) upsets. An algorithm that does not specify direction should
be independent of the direction that it is executed, but as soon as an
algorithm specifies direction it is unfair to say that a variation
that goes in the opposite direction is expected to arrive at the same
results because the variation is in fact a different algorithm.

allen
.

Relevant Pages

  • Re: Atlantic Coast Regionals
    ... and this should not matter in any good algorithm). ... them a 1-seed at sectionals, and if they end up winning sectionals ... provide more accurate seeds. ... enough objective information to justify seeding them lower and they ...
    (rec.sport.disc)
  • Re: Hash functions (was: Maximum String size in Java?)
    ... > "Even though a hash table is a fairly wonderful data structure, ... correctness are, which implies simplicity and consistency of the ... It doesn't take long for an Oalgorithm to become unusable, ... the broken "Reply" link at the bottom of the article. ...
    (comp.programming)
  • Re: famous literature
    ... Before I describe the algorithm, ... there is an important mathematical function - xor - that has an ... will generate random seeds. ... the run length random number generator. ...
    (sci.crypt)
  • Re: Online poker and RNG...
    ... Second, as soon as the hole cards are dealt, ... of those five cards, what seeds are possible. ... site publishes its algorithm, in which case the missing ingredient is ... it is difficult to keep these algorithms totally secret -- ...
    (sci.crypt)
  • Re: Atlantic Coast Regionals
    ... algorithm that troubles me is that the seedings it provides are not ... seeds would be unstable because the algorithm would reverse the order ... even though ACB has two local instabilities. ...
    (rec.sport.disc)
Loading