Generalization of the smith set?
Note: The generalization in this post seems fairly obvious and I assume has already been studied. I don’t remember seeing it described before, but I would guess it has been.
(skip to heading “the generalization part” if you are already familiar with the concept of a smith set and a dominating set in the context of voting mechanisms, and don’t want a refresher on the background)
Background:
The smith set is “the smallest non-empty set of candidates in a particular election such that each member defeats every candidate outside the set in a pairwise election”. Let w(x,y) be the proportion of the vote that x gets in a pairwise election against y. (w(x,y) isn’t a standard notation, I just picked a random letter. I don’t know what the standard letter to use for this is, if there is a standard letter to use.) For all x,y, w(y,x) = 1 - w(x,y) , i.e. w(y,x)+w(x,y)=1. Let C be the set of candidates. A subset X of C is called a dominating set if each element of X defeats each element of C\X in a pairwise election. i.e. a subset X of C is a dominating set if for all x in X, for all y in C\X , w(x,y) > 1/2 .
Let X and Y be dominating sets. Consider the intersection of X and Y, i.e. X \cap Y. Let x be an element of X \cap Y. Let t be an element of the complement of the intersection, i.e. of C\(X \cap Y). The complement of the intersection of X and Y is the union of the complements of X and Y, i.e. of (C \ X) \cup (C \ Y). Therefore, either t is in C\X, and therefore as x in X, w(x,t) > 1/2 , or t is in C\Y , and therefore as x in Y, w(x,t) > 1/2 . So, in any case, w(x,t) > 1/2 . So, for any x in X \cap Y and any t in C\(X \cap Y), w(x,t) > 1/2 . That is, when X and Y are dominating sets, the intersection of X and Y is also a dominating set. Therefore, the intersection of a finite set of dominating sets is also a dominating set. Suppose X and Y are both dominating sets, and are both non-empty. If the intersection of X and Y were empty, then each would be a subset of the complement of the other. But then, for x in X and y in Y, because x in X and X is a dominating set, and y in the complement of X, we would have w(x,y) > 1/2 , while at the same time, because Y is a dominating set, and y in Y, and x in the complement of Y, would have w(y,x) > 1/2 , and therefore w(x,y) + w(y,x) > (1/2) + (1/2) = 1, so w(x,y) + w(y,x) > 1 , which contradicts the fact that we always have w(x,y)+w(y,x)=1. So, for X and Y two non-empty dominating sets, their intersection is also non-empty, as well as being a dominating set.
Therefore, the intersection of a finite set of non-empty dominating sets is also a non-empty dominating set.
If C is finite, the set of subsets of C is also finite, and therefore the set of dominating sets is finite. C itself is always a dominating set, because its complement is empty, and therefore, vacuously, all elements of its complement lose a pairwise race against all elements of it. So, if C is finite and non-empty, the set of non-empty dominating sets is both finite and non-empty. If we take the intersection of all non-empty dominating sets, the result will be a non-empty dominating set which is a subset of all other non-empty dominating sets. i.e. it will be the smallest non-empty set of candidates such that each member defeats every candidate outside the set in a pairwise election, i.e. it will be the smith set. So, the smith set is the intersection of all non-empty dominating sets.
the generalization part:
For any p ≥ (1/2) , define a “p-dominating set” as: for a subset X of C, X is a p-dominating set if, for all x in X, and for all y in C\X , w(x,y) > p.
Note that a (1/2)-dominating set is the same thing as a dominating set. Note also that for any p > (1/2) , the condition that X is a p-dominating set is a stricter condition than that X is a dominating set. In general, for any p2 ≥ p1 ≥ (1/2) , (X is a p2-dominating set) implies (X is a p1-dominating set).
Note that the same argument as the one above (one of the ones under the “background” heading) that shows that the intersection of two dominating sets is also a dominating set, applies just as much to this case. Similarly, because for any p ≥ (1/2) , have that the sum of any two numbers which are both strictly greater than p is strictly greater than 1, and so the argument that the intersection of two non-empty dominating sets is non-empty and a dominating set, easily extends to show that the intersection of any two non-empty p-dominating sets is a non-empty p-dominating set. Also, the argument that C is always a dominating set extends to show that C is always a p-dominating set.
So, for any p ≥ (1/2) , if C is non-empty and finite, then the set of non-empty p-dominating sets is non-empty and finite, and so the intersection of all non-empty p-dominating sets is itself a non-empty p-dominating set, which is a subset of all non-empty p-dominating sets. Call this intersection the p-smith set.
A property of the p-smith set: For any p2 ≥ p1 ≥ (1/2) , the p1-smith set is a subset of the p2-smith set. (This is because the set of non-empty p2-dominating sets is a subset of the set of non-empty p1-dominating sets , and so the intersection of all non-empty p1-dominating sets is the intersection of all p2-dominating sets and also possibly some more sets, and is therefore a subset of the intersection of all p2-dominating sets.)
We can therefore generalize the smith-criterion for voting systems to get the weaker p-smith-criterion. Instead of requiring that the winner always be in the smith-set, as the smith-criterion requires, the p-smith-criterion instead requires that the winner always be in the p-smith set.
Some voting systems do not satisfy the smith criterion. For example, any system which satisfies the participation criterion (casting a ballot for one’s preference cannot increase the chance of one’s preference losing to a candidate one ranks strictly lower) , and has more than 3 candidates and more than 11 voters, can simultaneously satisfy the smith criterion.
So, I think a natural question to ask, could be, “For each p > (1/2), can a system be designed which satisfies the participation criterion, and also satisfies the p-smith-criterion?” . (For p=1 , the p-smith set, (i.e. the 1-smith set) is the smallest set of candidates that is unanimously preferred to all candidates outside the set. I’m fairly confident that the 1-smith-criterion is compatible with the participation criterion, and with basically any reasonable criterion, though that’s mostly based on intuition, not any real argument.)
Question: What is the smallest p such that the p-smith-criterion is consistent with the participation criterion (with any number of voters and any number of candidates)? Edit: Turns out “half-way monotonicity”, i.e. “completely reversing the order preference you express on your ballot compared to your true preferences cannot improve the outcome from your perspective, compared to if you voted your true preferences”, which is a weaker condition than the participation criterion, is also incompatible with the Condorcet criterion, and therefore incompatible with the smith-criterion. Therefore, Question: What is the smallest p such that the p-smith-criterion is consistent with the “half-way monotonicity” condition?