[EM] SODA

[fsimmons at pcc.edu]

You're right, the same example dawned on me last night after I used up all of my computer time.

But the Hasse diagram of the partial order does yield a weighted DAG (directed acyclic graph) where the 
weight of each coalition is the sum of the weights of the factions that are included in it.  If we agree that 
edges are directed from coalition to subcoalition, then the only source is the set of all factions. [A 
source is a node that has at least one edge leaving it, but no edge entering it; i.e. indegree=0, 
outdegree>0.]

Here's how to order the factions:

While there remains at least one edge in the graph ..
    remove the heaviest edge leaving the most recently exposed source.
EndWhile

The factions play in the order that they are exposed.

[The weight of an edge is the weight of the node that it enters.  A node is exposed at the stage its 
indegree reaches zero. In the original DAG the only source is considered to be the "most recently 
exposed source."]

This generalizes the order that I gave for trees, i.e.if the DAG is a tree, this order agrees with the order 
that I gave for that case.

It is clear that this algorithm takes O(n) steps where n is the number of edges in the DAG.



----- Original Message -----
From: Jameson Quinn 
> > The Hasse diagram for a partially ordered set is a tree.
> >
> 
> No, it's not. Or at least, not if I understand your terms 
> correctly. If
> there are three candidates [ABC], and all vote types exist, then 
> is [A] a
> leaf on the [AB] branch or on the [AC] branch?
> 
> JQ
>