In this assignment, we present a generalized version of the deferred acceptance algorithm that handles indifferences in the agent preferences, and we...

2.2 Analysis of the GDA Algorithm

We begin our analysis of the GDA algorithm by stating some easily proven facts concerning the colors of the left vertices. First, the only possible color transitions are from white to gray and from gray to black. Second, for any man p in I, if we let ui denote the left vertex of G associated with tier(I,p,i) for 0 ≤ i < tiers(I,p), then at any given point in the execution of the GDA algorithm, there are integers s and t such that the following conditions hold: 0≤s≤t≤tiers(I,p); t−s≤1; if0≤i<s, then ui is colored white; if s≤i<t, then  ui is colored gray; if t ≤ i < tiers(I,p), then ui is colored black.

Problem 1. Prove that at any point in the execution of the GDA algorithm, no two gray left vertices have the same priority. Hint: Use the second color-related fact stated above.