Monthly Archives: September 2023

Clustering

I feel a little silly I didn’t come up with this one myself.

The problem: Clustering.  This is problem MS9 in the appendix.

The description: Given a complete weighted graph G=(V,E), with a positive weight d(i,j) for each edge eij, and two positive integers K and B.  Can we partition V into K (or less) disjoint sets V1..Vk such that within each Vi, all edges that stay within the partition cost B or less?

Example: Here is a graph:

If K=2, and B=2, we could have the sets {A,C} and {B,D} as a legal cluster.  But if  K=2 and B=1, we will not be able to solve the problem.  For example, we might want to have the edges (A,B) and (A,D) in the same cluster, but that would require us also to consider the edge (B,D), which is larger than 1.

Reduction: Brucker’s paper introduces the problem using a graph, like I did above. (G&J talk about points and distances), His reduction is from Graph Coloring.

Suppose we have a coloring graph G.  We build a new graph G’ such that the weight of an edge in G’ is 1 if it did not appear in G, and its weight is 2 if it did appear in G.  Then we set out K = the K of the coloring problem (3 for 3-coloring), and B = 2.  A partition of the vertices into 3 sets where each set has no weight-2 edges is exactly a legal coloring.

Difficulty: 3.  I do think the graph terminology helps to make the problem more understandable.

Shapley-Shubik Voting Power

Setting up this definition will take a bit, bear with me.

The problem: Shapley-Shubik Voting Power.  This is problem MS8 in the appendix.

The description: Suppose we have a set of n voters, each voter i has a “weight” wi, corresponding to their number of votes.  If we are doing a simple majority vote, a coalition of voters then needs votes of (strictly) more than half the sum of the weights to win.  For a specific voter i, we can look at all permutations of voters, and say that all voters before voter i in the permutation voted “yes”, and all voters after voter i in the permutation voted “no”.  We are interested in the number of these permutations where voter i’s vote “matters”- where adding voter i to the “yes” votes makes “yes” the majority, but adding them to the “no” votes makes “no” the majority.  We call voter i a pivot player if this is the case.

Is voter 1 (in the G&J definition, it’s voter N in the paper) ever a pivot?

Some clarifications:  The number of times a voter is a pivot is the “Shapley-Shubik voting power”, and the proportion of permutations the voter is a pivot (by dividing the count by N!) is the “Shapley-Shubik power index”, but all we care about here is whether the power is non-zero.

Also, the definition of the voting game (in G&J, and also in the paper) allows for a more general definition of winning, besides a simple majority- you can supply a “quota” q, and any amount of votes ≥ q is a winning coalition.  For us, q is set in the reduction to be 1/2 the sum of the weights, +1, rounded up.

Example: Suppose we had 4 voters, with weights: 5.4,3,1.  There is 13 total weight, and 7 weight is enough to win. Voter 4 has 0 coalitions in which they are the pivot (we would need 6 votes without them), so has “zero Shapley-Shubik voting power”.

If, however, we split up the same number of votes among 5 voters: 4,3,3,2,1, then the 1-vote voter can be a pivot with (among others) the 4 and the 2.  The coalition loses without our pivot voter but wins with them.

Reduction: G&J have this as an “unpublished results” problem, but luckily I found a paper by Matsui and Matsui who solved it.  So we start with Partition.  We’re given a set A of n integers.  We will create a set of weights with one weight equal to each element of A, and add one extra voter with weight 1 at the end.  This is the voter that may or may not be a pivot.

If this last voter is a pivot, then there is a coalition that needs an additional weight of 1 to become a majority.  This means the coalition had exactly half of the votes without this voter (and so the sum of the elements is a partition of A)

In the other direction, if the set has a partition, then the partition set’s votes is equal to exactly half of the votes, one short of a majority.  Adding our 1-weight voter will make it a majority, and thus that voter is a pivot.

Difficulty: 4.  This problem looks scary because the definitions of Shapley-Shubik voting power include a lot more than what you actually need to do this reduction.  Once you get past all of that, it’s actually a pretty nice problem that students can handle.