OPTIMAL COTERIES AND VOTING SCHEMES

We consider coteries (i.e. intersecting, Sperner systems) on arbitrary networks with given node reliability, which maximize the network avai lability (i.e. the probability that the set of operating nodes has a c onnected subgraph which contains a set from the coterie). We show that the singleton coterie is always optimal on any network when the node reliability is p less-than-or-equal-to 1/2. For p greater-than-or-equa l-to 1/2, we give optimal coteries for the complete multipartite netwo rks. The resulting optimal coteries when restricted to a special subcl ass of complete bipartite networks are shown to exceed the availabilit y of any voting scheme, for p > 1/2.