probability 1 3 , 1 6 , 1 6 , 1 3 , respectively, is maxmin-fair. The satisfaction probabilities of a0, a1, a2 and a3 are then 1, 2 3 , 2 3 , 2 3 . Any attempt to match, say, a1 with probability > 2 3 will n [...] bility, and so on. Example 4. In Examples 1 and 2 we have F1 ↑ = F2 ↑ = (1, 2 3 , 2 3 , 2 3 ) ≻ D ↑ = ( 23 , 2 3 , 2 3 , 2 3 ). As D ↑ is not lexicographically maximal, it cannot be maxmin- fair; whereas [...] and S3 = B1 ∪B2 ∪B3 as the fairly isolated sets. This motivates the following definitions. a0 a1 a2 a3 a4 a5 b0 b1 b2 b3 Fig. 2 A bipartite graph with blocks B1 = {a5, a4}, B2 = {a3, a2, a1} and B3 = {a0} …

probability 1 3 , 1 6 , 1 6 , 1 3 , respectively, is maxmin-fair. The satisfaction probabilities of a0, a1, a2 and a3 are then 1, 2 3 , 2 3 , 2 3 . Any attempt to match, say, a1 with probability > 2 3 will n [...] bility, and so on. Example 4. In Examples 1 and 2 we have F1 ↑ = F2 ↑ = (1, 2 3 , 2 3 , 2 3 ) ≻ D ↑ = ( 23 , 2 3 , 2 3 , 2 3 ). As D ↑ is not lexicographically maximal, it cannot be maxmin- fair; whereas [...] and S3 = B1 ∪B2 ∪B3 as the fairly isolated sets. This motivates the following definitions. a0 a1 a2 a3 a4 a5 b0 b1 b2 b3 Fig. 2 A bipartite graph with blocks B1 = {a5, a4}, B2 = {a3, a2, a1} and B3 = {a0} …