Suppose we relax the rules for the men, so that each unpaired man proposes to the next woman on his list at a time of his choice (some men might procrastinate for several days, while others might propose and get rejected several times in a single day). Can the order of the proposals change the resulting pairing? Give an example of such a change or prove that the pairing that results is the same as with the standard algorithm.
To my thought this won't change the pairing of result as the preference list remains the same hence there will be only one solution that we will get.
But i am not really sure about this. Please correct me if i am wrong.
If we set all bachelors to set A = {a,b,c} and all females as set B = {x,y,z} for a simplified example, Aa may prefer Bx but given that time of choice for pairing is essentially a random event with respect to all elements in set A, the mapping of A to B as you've asked would change for each decision by members of A given that the preference associated with Aa, Ab, and Ac may overlap but this shift in pairing would occur irrespective to time.
Proof:
Ab prefers, in order, By, Bx and Bz. this creates matrix [AbBy, AbBx, AbBz].
Aa chooses next, and prefers Bx, Bz, By. Matrix becomes [AaBx, AaBz, AaBy]
Ac chooses last, and prefers By, Bz, Bx creating the matrix [AcBy, AcBz, AcBx].
your condition states that rejection is possible, so with Ab choosing first, assume rejection, Aa is accepted by first choice regardless of time of proposal. Ac ignores Bx saving Bx for last, and instantiates AcBy, which accepts. Ab proposes to second preference, but AaBx is instantiated (Bx accepts Aa), therefore the order of preference shifts for Ab to Bz, which Bz must accept if the system is closed to the defined matrices and pairings are definite (meaning all in A end with a pair from B).
If Ab prefers, in order, Bx, Bz, By then Ab = Aa, yet time becomes a factor given the equality in preference. If Ab chooses first, and is accepted in the first round, Aa must change preference to Bz, By (in that order).
To formalize this:
{a,b,c} are elements of A, {x, y, z} are elements of B. for all in A, there is some B such that Aa...Ac maps to one and only one element of B, and for all elements of B, there is some A such that {Bx...Bz} maps onto one and only one element of A. A relationship exists between A and B such that the pairing between all elements of A and B is ordered and determined based upon values of elements in A. For each successive pairing from A to B there is an element of B which has been paired and now becomes a null value. If a pairing is attempted from an element of A to an element of B and B returns a null value, the successor function pairs the same element of A to a new element of B until a pair is successful.