Exercise Sheet 5

Exercise 1

Instruction

Show that the bases of a matroid satisfy property (B3) from Chapter “Metroids and Greedy Algorithms”.

Let be a matroid and let be the basis family, i.e. the set of all bases of ,

We have to show the Basis exchange property (B3)

Understanding the property

• For every two bases , i.e., maximal independent sets,
• and all elements that are not in ,
• there exists an element that is not in ,
• such that we can replace in with from , and
• the resulting set is again a base.

So we have to show that, after removing any element from one basis , we can replace it by some element from the other basis and again obtain a basis.

Solution

Let be two bases, and choose

Set

Since is independent, heredity gives . Also all bases have the same size, so

Now apply exchangeability to and . We get some

with

Since and , removing from does not matter from the view of . Hence

Thus the element from exchangeability is actually .

Finally,

So is independent and has basis size. It must therefore be a basis; otherwise it could be extended to a larger basis, contradicting that all bases have the same size. Since ,

This proves (B3).

The exchange is visualised below: pick , drop it to get , then exchangeability against supplies so that is again a basis.

Exercise 2

Instruction

Let be a graph and let be the set family over the vertex set with

i.e., if and only if there is a matching of with , where denotes the set of vertices incident to an edge of . (This is the matching matroid of from the lecture)

1. Consider the following graph

   Which of the following subsets belong(s) to ?

2. Show that satisfies the exchangeability property (I3).

Hint: For part (b): Let and be matchings covering and , respectively, and distinguish two cases.

1. Case 1: Some vertex is also covered by .
2. Case 2: Otherwise every vertex of is uncovered by . In the case, look at the symmetric difference and try to modify the matching so that it covers all of and at least one vertex of .

Here, the ground set of the set family is the vertex set . A set is in if the graph has a matching that touches every vertex in .

Matching

Definition

Matching

A matching of an undirected graph is a subset such that no two edges in share an endpoint.

Example: The highlighted edge sets below show a matching , a maximal matching , and a maximum matching .

Link to original

So for (1), I only need to decide whether the listed vertex sets can be covered by pairwise disjoint edges.

(1)

• belongs to . For example, the matching

covers and .

• doesn’t belong to . Both and can only be covered through , using the edges and . These two edges share , so they cannot both be in a matching.

• belongs to . For example, the matching

covers , and .

For the second part, we have to show exchangeability (I3):

This means that if is a larger coverable vertex set than , then at least one vertex from can be added to while still being coverable by some matching.

(2)

I can think of as the matching I already have. It covers . The matching covers the larger set . Since , there are more vertices on the -only side than on the -only side:

The goal is to make cover one extra vertex from without losing any vertex of .

If some is already covered by , then nothing has to be changed.

Otherwise, every is free in , but matched in . So in the overlay , each such starts an alternating path:

If I flip this path, the first vertex becomes covered by the modified . The internal vertices stay covered; they only change which edge covers them. The only possible loss is at the other endpoint of the path.

So a path is safe if its other endpoint is not in . Flipping a safe path keeps all of covered and adds one new vertex . In particular, a path joining two vertices of is safe: both endpoints gain coverage.

Why must a safe path exist? Suppose all paths were unsafe. Then every path starting in ends in , on an edge of (otherwise flipping it would not uncover that endpoint). This endpoint is uncovered by , so it cannot lie in . Hence every unsafe endpoint lies in .

These paths are separate connected components of . If two of them met, they would be one component, not two. So different starts in need different endpoints in . That would require

contradicting .

Therefore at least one path is safe. Flip it. Then the resulting matching covers and one additional vertex , so

This proves (I3).

Exercise 3

Instruction

Show that for each , there exists a preference profile on alternatives and voters that admits a Condorcet winner such at least alternatives have a larger Borda score than the Condorcet winner.

Hint: Use a dedicated alternative to increase the Borda score gap between any other alternative and the Condorcet winner.

A one-vote Condorcet lead

Put , and name the alternatives . We want to be the Condorcet winner and all alternatives to beat it in Borda score. Candidate is the extra alternative used to separate their Borda scores.

Let be the order , let reverse it, and let be its cyclic rotations. For , these are , , and ; each occupies each position exactly once. Construct voters:

Number	Ranking
	, once for each
	and
	, once for each

Candidate is above every opponent in the first votes and below every opponent in the other . Thus beats each opponent by votes to .

Give ranks from top to bottom Borda points. A candidate’s Borda score is the sum of its points over all votes. Candidate gets

Across both sets of rotations, each earns points with first and points with last, totalling . The two reverse orders contribute another points, while the final contributes . Hence

The strict inequality holds for every . Thus at least alternatives beat the Condorcet winner in Borda score, using only voters.

Exercise 4

Instruction

Recall that the Kendall-tau distance between two linear orders is

i.e., the number of pairs of alternatives that and order differently. Show that the following observation from the chapter “COMSOC” is correct:

For a pair of alternatives , if , then every K-consensus has .

Hint: Argue by contradiction, following the setup in the annotated slides, and show that one of two adjusted linear orders has a smaller Kendall-tau distance. Suppose the statement is false, and let be a pair with for which some K-consensus has . Show that either moving up to just above , or moving down to just below , yields a linear order with smaller total Kendall-tau distance.

The Kendall-Tau distance counts inversions between two rankings. An inversion is a pair of alternatives whose relative order is different in the two rankings. For example, between

the pairs and are inverted, while is ordered the same way. Hence the distance is .

For a profile, the total Kendall-Tau distance of a proposed consensus ranking is obtained by adding this inversion count over all voters. Thus each voter contributes one unit for each pair where the consensus disagrees with their ranking.

For two alternatives , the notation denotes the set of voters in the profile who rank above :

Here means that this support set is the whole profile: every voter ranks above . So the profile is unanimous on the ordered pair .

We have to show that this unanimous pair is fixed in every Kemeny consensus. Equivalently, no ranking that minimises the total Kendall-Tau distance may put above .

For a ranking , write

for its total distance to the profile.

What denotes

abbreviates Kendall-Tau. Here counts pairwise disagreements with one voter, while sums these disagreements over the whole profile. A Kemeny consensus minimises this total score.

Why two repairs are enough

Suppose a consensus ranking wrongly contains

even though every voter ranks above .

The wrong pair costs one disagreement for every voter. There are two natural ways to repair it:

• move upward to just above ;
• move downward to just below .

Both repairs fix the pair . They may change how the middle alternatives are ordered relative to or , but a middle alternative cannot make both repairs worse enough to compensate for the unanimous improvement on .

Solution

I start by assuming that the statement fails. The statement says that a unanimous pair must be respected by every Kemeny consensus. So if it fails, there must be a first visible problem:

• every voter ranks some above some ;
• but some Kemeny consensus does not rank above .

Since is a linear order, it must choose one direction for the pair . If it does not have , then it has

So I look at the part of where this mistake occurs. Write the segment from down to as

where is everything before , is everything after , and

is the set of alternatives sitting between and .

At this point, the natural thing to try is to repair only the wrong pair , without disturbing the whole ranking. There are two minimal repairs:

• move upward to just above ;
• move downward to just below .

Denote the resulting rankings by and . Written out, they are

In both trial rankings, I deliberately leave and untouched. I only move one endpoint of the bad interval: either moves up, or moves down. So the alternatives in are not what I am trying to move, but they are exactly the alternatives that get crossed. This is why only comparisons involving or and some can change.

Now I compare the scores. In , the pair is wrong for every voter, because every voter has above but has above . Hence this single pair contributes disagreements to .

Both repairs put above , so this pair contributes after either repair. Thus each repair immediately gains on the pair .

Why this is a gain of

The total Kendall-Tau distance adds one penalty for each voter who disagrees with the proposed consensus on a pair. Before the repair, all voters disagree with on . After the repair, none of them disagree on this pair. The score therefore drops by , which is why the change contributes in the formulas below.

The question is whether the crossed alternatives in can make this gain disappear, i.e., whether the changed comparisons with alternatives between and can add enough new disagreements to cancel the saved disagreements. First look at the repair , where moves upward. For each , the pair is reversed:

Before the repair, this pair disagreed with exactly the voters in . After the repair, it disagrees with exactly the voters in . Therefore this pair changes the score by . Including the gain from fixing gives

The same reasoning for gives the other possible change. Moving downward reverses every pair with :

Hence

At this stage I do not need to know which repair is better. It is enough to show that the two changes together are negative, because then at least one of them must be negative.

Fix one middle alternative and one voter. Since the pair is unanimous, this voter ranks above . So can only sit in one of three places relative to and :

voter order	contribution to the two sums

This table records the voter’s contribution to

For example, in the middle case , the voter supports , so the first bracket contributes . The same voter supports , so the second bracket also contributes . The total is .

In the other two cases the contributions cancel to . Thus no voter contributes positively to the two side-effect sums. Summing over all voters and all gives

Therefore the two total changes satisfy

If the sum of two numbers is negative, then at least one of them is negative. So either

or

In either case, the supposed Kemeny consensus was not actually optimal: one of the two simple repairs has smaller total Kendall-Tau distance. This contradicts the definition of a Kemeny consensus.

Hence every Kemeny consensus must rank above whenever all voters rank above .

Exercise 5

Instruction

Recall the justified representation (JR) axiom for approval-based multi-winner voting: Given approval sets for the voters , with , a size- committee satisfies JR if for every voter subset with and (a cohesive group) it holds that

Show that for every approval profile and every , a size- committee satisfying JR can be found in polynomial time.

Hint: You cannot use the CC voting rule, since it is NP-hard to compute. Instead, adapt the AV rule by greedily adding an alternative that is approved by the largest number of not-yet-represented voters.

Greedily represent new voters

Let be the voters not yet represented by the committee . Initially and . For each of the seats, choose an unelected candidate maximising

add to , and remove from every voter who approves . Ties are arbitrary. Assume ; candidates with no new approvals can fill any remaining seats.

Suppose the resulting violates JR. Then some group of at least voters shares a candidate , yet none of its voters approves anyone in . Thus throughout the algorithm, and remains unelected. At every selection, would represent at least new voters. The greedy candidate represents at least as many. Since represented voters are removed from , the selections represent disjoint groups, giving

This would leave , contradicting . Hence satisfies JR.

For each seat, scan all candidates and voters to count new approvals. This takes time, which is polynomial.

Exercise 6

Instruction

Consider the Dynamic Programming (DP) algorithm for the CC rule on single-peaked approval preferences from Chapter “COMSOC”, where the alternatives are ordered such that every voter approves an interval of this order.

1. What does the DP table look like for the following instance with ? Justify your answer, and state which committee achieves the maximum CC-score.

   Hint: Recall that stores the maximum CC-score over size- committees chosen from that include . Compute for each , then for via the recurrence.

2. Show that the DP algorithm for single-peaked approval preferences is correct for the CC rule, i.e., for every and , equals the maximum CC-score over size- committees from that include . The overall optimum is then .

   Hint: Induct on . What do you know about a voter’s approval set if it approves but not ?

Write for the voters approving . Because each is an interval in the candidate order, if and a voter approves but not , that voter approves no . This is the reason the DP only needs to remember the last selected candidate.

For , let be the best number of represented voters among size- committees from containing . Entries with are infeasible. The recurrence is

(1) Fill the table

The approval sets of the candidates are

For instance, the three ways to finish a two-member committee at give

The full table (a dash means that the committee is too large for the prefix) is

	—

In particular, . The maximum is , attained by : represents and represents .

(2) Why the recurrence is correct

Induct on . At , the only committee counted by is , representing exactly voters.

For , take any committee counted by , and let be its second-last candidate, where . Its first members are among and include . When is added, the newly represented voters are precisely : a voter approving both and was already represented, while a voter approving but not cannot approve any earlier candidate because their approval set is an interval. Thus

Conversely, adding to a committee attaining gives exactly that score. Maximising over all possible proves the recurrence. Every size- committee has some last candidate , so its overall best score is .

There are states, each testing at most predecessors. With the sets stored as bit vectors or Boolean arrays, each gain can be computed in time, giving time overall.