Exercise Sheet 5

Exercise 1

Instruction

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

Let $\mathcal{M}=(E,\mathcal{I})$ be a matroid and let $\mathcal{B}$ be the basis family, i.e. the set of all bases of $\mathcal{M}$,

$$\mathcal{B}=\{B\subseteq E\mid B\text{ is a basis of}\mathcal{M}\}\subseteq 2^E.$$

We have to show the Basis exchange property (B3)

$$\forall B_1,B_2\in \mathcal{B}:\forall x\in B_1\setminus B_2:\exists y\in B_2\setminus B_1:\underset{B_1\text{with}y\text{replacing}x\text{is again a basis}}{\underbrace{(B_1\setminus \{x\})\cup \{y\}\in \mathcal{B}}}$$

Understanding the property

• For every two bases $B_1,B_2\in \mathcal{B}$, i.e., maximal independent sets,
• and all elements $x\in B_1$ that are not in $B_2$,
• there exists an element $y\in B_2$ that is not in $B_1$,
• such that we can replace $x$ in $B_1$ with $y$ from $B_2$, and
• the resulting set is again a base.

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

Solution

Let $B_1,B_2\in \mathcal{B}$ be two bases, and choose

$$x\in B_1\setminus B_2.$$

Set

$$X=B_1\setminus \{x\}.$$

Since $B_1$ is independent, heredity gives $X\in \mathcal{I}$. Also all bases have the same size, so

$$|X|=|B_1|-1<|B_2|.$$

Now apply exchangeability to $X$ and $B_2$. We get some

$$y\in B_2\setminus X$$

with

$$X\cup \{y\}\in \mathcal{I}.$$

Since $X=B_1\setminus \{x\}$ and $x\notin B_2$, removing $x$ from $B_1$ does not matter from the view of $B_2$. Hence

$$B_2\setminus X=B_2\setminus (B_1\setminus \{x\})=B_2\setminus B_1.$$

Thus the element from exchangeability is actually $y\in B_2\setminus B_1$.

Finally,

$$|X\cup \{y\}|=|X|+1=|B_1|.$$

So $X\cup \{y\}$ 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 $X=B_1\setminus \{x\}$,

$$(B_1\setminus \{x\})\cup \{y\}\in \mathcal{B}.$$

This proves (B3).

The exchange is visualised below: pick $x\in B_1\setminus B_2$, drop it to get $X=B_1\setminus \{x\}$, then exchangeability against $B_2$ supplies $y\in B_2\setminus B_1$ so that $(B_1\setminus \{x\})\cup \{y\}$ is again a basis.

Exercise 2

Instruction

Let $G=(V,E)$ be a graph and let $\mathcal{M}=(V,\mathcal{I})$ be the set family over the vertex set $V$ with

$$\mathcal{I}=\{S\subseteq V:\text{some matching of }G\text{ covers every vertex of }S\},$$

i.e., $S\in \mathcal{I}$ if and only if there is a matching $M$ of $G$ with $S\subseteq V(M)$, where $V(M)$ denotes the set of vertices incident to an edge of $M$. (This $\mathcal{M}$ is the matching matroid of $G$ from the lecture)

1. Consider the following graph $G$

   Which of the following subsets belong(s) to $\mathcal{I}$?

   • $S_1=\{v_1,v_5\}$
   • $S_2=\{v_1,v_2,v_5\}$
   • $S_3=\{v_2,v_4,v_6\}$

2. Show that $\mathcal{I}$ satisfies the exchangeability property (I3).

Hint: For part (b): Let $M_X$ and $M_Y$ be matchings covering $X$ and $Y$, respectively, and distinguish two cases.

1. Case 1: Some vertex $y\in Y\setminus X$ is also covered by $M_X$.
2. Case 2: Otherwise every vertex of $Y\setminus X$ is uncovered by $M_X$. In the case, look at the symmetric difference $M_X\Delta M_Y$ and try to modify the matching $M_X$ so that it covers all of $X$ and at least one vertex of $Y\setminus X$.

Here, the ground set of the set family is the vertex set $V$. A set $S\subseteq V$ is in $\mathcal{I}$ if the graph has a matching that touches every vertex in $S$.

Matching

Definition

Matching

A matching of an undirected graph $G=(V,E)$ is a subset $M\subseteq E$ such that no two edges in $M$ share an endpoint.

Example: The highlighted edge sets below show a matching $M_1$, a maximal matching $M_2$, and a maximum matching $M_3$.

Link to original

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

(1)

• $S_1=\{v_1,v_5\}$ belongs to $\mathcal{I}$. For example, the matching

$$\{\{v_1,v_3\},\{v_5,v_6\}\}$$

covers $v_1$ and $v_5$.

• $S_2=\{v_1,v_2,v_5\}$ doesn’t belong to $\mathcal{I}$. Both $v_1$ and $v_2$ can only be covered through $v_3$, using the edges $\{v_1,v_3\}$ and $\{v_2,v_3\}$. These two edges share $v_3$, so they cannot both be in a matching.

• $S_3=\{v_2,v_4,v_6\}$ belongs to $\mathcal{I}$. For example, the matching

$$\{\{v_2,v_3\},\{v_4,v_6\}\}$$

covers $v_2,v_4$, and $v_6$.

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

$$\forall X,Y\in \mathcal{I}:|X|<|Y|⟹\exists y\in Y\setminus X:X\cup \{y\}\in \mathcal{I}$$

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

(2)

I can think of $M_X$ as the matching I already have. It covers $X$. The matching $M_Y$ covers the larger set $Y$. Since $|X|<|Y|$, there are more vertices on the $Y$-only side than on the $X$-only side:

$$|X|<|Y|⟺|X\setminus Y|<|Y\setminus X|.$$

The goal is to make $M_X$ cover one extra vertex from $Y\setminus X$ without losing any vertex of $X$.

If some $y\in Y\setminus X$ is already covered by $M_X$, then nothing has to be changed.

Otherwise, every $y\in Y\setminus X$ is free in $M_X$, but matched in $M_Y$. So in the overlay $M_X\Delta M_Y$, each such $y$ starts an alternating path:

$$y\stackrel{M_Y}{\to }\cdot \stackrel{M_X}{\to }\cdot \stackrel{M_Y}{\to }\cdots$$

If I flip this path, the first vertex $y$ becomes covered by the modified $M_X$. 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 $X$. Flipping a safe path keeps all of $X$ covered and adds one new vertex $y\in Y\setminus X$.

Why must a safe path exist? Suppose all paths were unsafe. Here unsafe means that the other endpoint lies in $X$, because then flipping the path might uncover a vertex that still has to stay covered. So every path starting in $Y\setminus X$ would have to end in $X$. Such an endpoint cannot be in $Y$, because vertices of $Y$ are covered by $M_Y$. Hence all unsafe endpoints lie in $X\setminus Y$.

These paths are separate connected components of $M_X\Delta M_Y$. If two of them met, they would be one component, not two. So different starts in $Y\setminus X$ need different endpoints in $X\setminus Y$. That would require

$$|Y\setminus X|\le |X\setminus Y|,$$

contradicting $|X\setminus Y|<|Y\setminus X|$.

Therefore at least one path is safe. Flip it. Then the resulting matching covers $X$ and one additional vertex $y\in Y\setminus X$, so

$$X\cup \{y\}\in \mathcal{I}.$$

This proves (I3).

Exercise 3

Instruction

Show that for each $m>4$, there exists a preference profile on $m$ alternatives and $O(m)$ voters that admits a Condorcet winner such at least $m-2$ 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.

Exercise 4

Instruction

Recall that the Kendall-tau distance between two linear orders $\succ ,{\succ }^{\prime }\in \mathcal{L}(C)$ is

$$KT-dist(\succ ,{\succ }^{\prime })=|\{(x,y)\in C\times C:x\succ y\wedge y{\succ }^{\prime }x\}|,$$

i.e., the number of pairs of alternatives that $\succ$ and ${\succ }^{\prime }$ order differently. Show that the following observation from the chapter “COMSOC” is correct:

For a pair of alternatives $\{x,y\}\subseteq C$, if $R(x,y)=R$, then every K-consensus ${\succ }^{\ast }$ has $x{\succ }^{\ast }y$.

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 $\{x,y\}$ be a pair with $R(x,y)=R$ for which some K-consensus ${\succ }^{\ast }$ has $y{\succ }^{\ast }x$. Show that either moving $x$ up to just above $y$, or moving $y$ down to just below $x$, 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

$$a\succ b\succ c\text{and}c{\succ }^{\prime }a{\succ }^{\prime }b,$$

the pairs $\{a,c\}$ and $\{b,c\}$ are inverted, while $\{a,b\}$ is ordered the same way. Hence the distance is $2$.

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 $x,y\in C$, the notation $R(x,y)$ denotes the set of voters in the profile $R$ who rank $x$ above $y$:

$$R(x,y):=\{i\in \{1,\dots ,n\}:x{\succ }_{i}y\}.$$

Here $R(x,y)=R$ means that this support set is the whole profile: every voter ranks $x$ above $y$. So the profile is unanimous on the ordered pair $x\succ y$.

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 $y$ above $x$.

For a ranking $\rho$, write

$$\mathrm{KT}(\rho ,R):=\sum _{i=1}^{n}KT-dist(\rho ,{\succ }_i)$$

for its total distance to the profile.

What $\mathrm{KT}$ denotes

$\mathrm{KT}$ abbreviates Kendall-Tau. Here $KT-dist(\rho ,{\succ }_i)$ counts pairwise disagreements with one voter, while $\mathrm{KT}(\rho ,R)$ 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

$$y{\succ }^{\ast }{z}_1{\succ }^{\ast }\cdots {\succ }^{\ast }{z}_t{\succ }^{\ast }x,$$

even though every voter ranks $x$ above $y$.

The wrong pair $y{\succ }^{\ast }x$ costs one disagreement for every voter. There are two natural ways to repair it:

• move $x$ upward to just above $y$;
• move $y$ downward to just below $x$.

Both repairs fix the pair $\{x,y\}$. They may change how the middle alternatives $z_1,\dots ,z_t$ are ordered relative to $x$ or $y$, but a middle alternative cannot make both repairs worse enough to compensate for the unanimous improvement on $\{x,y\}$.

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 $x$ above some $y$;
• but some Kemeny consensus ${\succ }^{\ast }$ does not rank $x$ above $y$.

Since ${\succ }^{\ast }$ is a linear order, it must choose one direction for the pair $\{x,y\}$. If it does not have $x{\succ }^{\ast }y$, then it has

$$y{\succ }^{\ast }x.$$

So I look at the part of ${\succ }^{\ast }$ where this mistake occurs. Write the segment from $y$ down to $x$ as

$${\succ }^{\ast }:L{\succ }^{\ast }y{\succ }^{\ast }{z}_1{\succ }^{\ast }\cdots {\succ }^{\ast }{z}_t{\succ }^{\ast }x{\succ }^{\ast }H,$$

where $L$ is everything before $y$, $H$ is everything after $x$, and

$$Z:=\{z_1,\dots ,z_t\}$$

is the set of alternatives sitting between $y$ and $x$.

At this point, the natural thing to try is to repair only the wrong pair $y{\succ }^{\ast }x$, without disturbing the whole ranking. There are two minimal repairs:

• move $x$ upward to just above $y$;
• move $y$ downward to just below $x$.

Denote the resulting rankings by ${\succ }_x$ and ${\succ }_y$. Written out, they are

$$\begin{array}{rl}{\succ }_x& :L{\succ }_{x}x{\succ }_{x}y{\succ }_x{z}_1{\succ }_x\cdots {\succ }_x{z}_t{\succ }_{x}H,\\ {\succ }_y& :L{\succ }_y{z}_1{\succ }_y\cdots {\succ }_y{z}_t{\succ }_{y}x{\succ }_{y}y{\succ }_{y}H.\end{array}$$

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

Now I compare the scores. In ${\succ }^{\ast }$, the pair $\{x,y\}$ is wrong for every voter, because every voter has $x$ above $y$ but ${\succ }^{\ast }$ has $y$ above $x$. Hence this single pair contributes $n$ disagreements to $\mathrm{KT}({\succ }^{\ast },R)$.

Both repairs put $x$ above $y$, so this pair contributes $0$ after either repair. Thus each repair immediately gains $n$ on the pair $\{x,y\}$.

Why this is a gain of $n$ The total Kendall-Tau distance adds one penalty for each voter who disagrees with the proposed consensus on a pair. Before the repair, all $n$ voters disagree with ${\succ }^{\ast }$ on $\{x,y\}$. After the repair, none of them disagree on this pair. The score therefore drops by $n$, which is why the change contributes $-n$ in the formulas below.

The question is whether the crossed alternatives in $Z$ can make this gain disappear, i.e., whether the changed comparisons with alternatives between $y$ and $x$ can add enough new disagreements to cancel the $n$ saved disagreements. First look at the repair ${\succ }_x$, where $x$ moves upward. For each $z\in Z$, the pair $\{x,z\}$ is reversed:

$$z{\succ }^{\ast }x\text{becomes}x{\succ }_{x}z.$$

Before the repair, this pair disagreed with exactly the voters in $R(x,z)$. After the repair, it disagrees with exactly the voters in $R(z,x)$. Therefore this pair changes the score by $|R(z,x)|-|R(x,z)|$. Including the gain $-n$ from fixing $\{x,y\}$ gives

$$\mathrm{KT}({\succ }_x,R)-\mathrm{KT}({\succ }^{\ast },R)=-n+\sum _{z\in Z}(|R(z,x)|-|R(x,z)|).$$

The same reasoning for ${\succ }_y$ gives the other possible change. Moving $y$ downward reverses every pair $\{y,z\}$ with $z\in Z$:

$$y{\succ }^{\ast }z\text{becomes}z{\succ }_{y}y.$$

Hence

$$\mathrm{KT}({\succ }_y,R)-\mathrm{KT}({\succ }^{\ast },R)=-n+\sum _{z\in Z}(|R(y,z)|-|R(z,y)|).$$

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 $z\in Z$ and one voter. Since the pair is unanimous, this voter ranks $x$ above $y$. So $z$ can only sit in one of three places relative to $x$ and $y$:

voter order	contribution to the two sums
$x{\succ }_{i}y{\succ }_{i}z$	$0$
$x{\succ }_{i}z{\succ }_{i}y$	$-2$
$z{\succ }_{i}x{\succ }_{i}y$	$0$

This table records the voter’s contribution to

$$(|R(z,x)|-|R(x,z)|)+(|R(y,z)|-|R(z,y)|).$$

For example, in the middle case $x{\succ }_{i}z{\succ }_{i}y$, the voter supports $x\succ z$, so the first bracket contributes $-1$. The same voter supports $z\succ y$, so the second bracket also contributes $-1$. The total is $-2$.

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

$$\sum _{z\in Z}(|R(z,x)|-|R(x,z)|+|R(y,z)|-|R(z,y)|)\le 0.$$

Therefore the two total changes satisfy

$$\begin{array}{rl}& (\mathrm{KT}({\succ }_x,R)-\mathrm{KT}({\succ }^{\ast },R))+(\mathrm{KT}({\succ }_y,R)-\mathrm{KT}({\succ }^{\ast },R))\\ & =-2n+\sum _{z\in Z}(|R(z,x)|-|R(x,z)|+|R(y,z)|-|R(z,y)|)\\ & <0.\end{array}$$

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

$$\mathrm{KT}({\succ }_x,R)<\mathrm{KT}({\succ }^{\ast },R)$$

or

$$\mathrm{KT}({\succ }_y,R)<\mathrm{KT}({\succ }^{\ast },R).$$

In either case, the supposed Kemeny consensus ${\succ }^{\ast }$ 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 $x$ above $y$ whenever all voters rank $x$ above $y$.

Exercise 5

Instruction

Recall the justified representation (JR) axiom for approval-based multi-winner voting: Given approval sets $A_i\subseteq C$ for the voters $v_i\in V$, with $n=|V|$, a size-$k$ committee $C^{\ast }\subseteq C$ satisfies JR if for every voter subset $V^{\prime }\subseteq V$ with $|V^{\prime }|\ge n/k$ and ${\bigcap }_{v_i\in V^{\prime }}{A}_i\ne \varnothing$ (a cohesive group) it holds that

$$C^{\ast }\cap \left(\bigcup _{v_i\in V^{\prime }}{A}_i\right)\ne \varnothing .$$

Show that for every approval profile and every $k$, a size-$k$ 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.

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 $c_1⊳c_2⊳\cdots ⊳c_m$ such that every voter approves an interval of this order.

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

   	$c_1$	$c_2$	$c_3$	$c_4$
   $v_1$	$1$	$1$	$0$	$0$
   $v_2$	$0$	$1$	$1$	$0$
   $v_3$	$0$	$0$	$1$	$1$
   $v_4$	$0$	$0$	$0$	$1$
   $v_5$	$1$	$1$	$1$	$0$

   Hint: Recall that $T[j,k^{\prime }]$ stores the maximum CC-score over size-$k^{\prime }$ committees chosen from $\{c_1,\dots ,c_j\}$ that include $c_j$. Compute $T[j,1]$ for each $j$, then $T[j,2]$ for $j\in \{2,\dots ,m\}$ via the recurrence.

2. Show that the DP algorithm for single-peaked approval preferences is correct for the CC rule, i.e., for every $j\in \{1,\dots ,m\}$ and $k^{\prime }\in \{1,\dots ,k\}$, $T[j,k^{\prime }]$ equals the maximum CC-score over size-$k^{\prime }$ committees from $\{c_1,\dots ,c_j\}$ that include $c_j$. The overall optimum is then ${\max }_{j\in \{k,\dots ,m\}}T[j,k]$.

   Hint: Induct on $k^{\prime }$. What do you know about a voter’s approval set if it approves $c_j$ but not $c_{j^{\prime }}$?