Ex1.5

Translated Problem:

正如课本中讨论的,稳定匹配问题假定所有的学生和医院由全部排序的优先表.在这个问题中我们将考虑与他相关的另一个问题,其中学生和医院在某些选择中是中立的.如前所述,我们有$n$个学生的集合$S$和$n$个医院的学生$H$.假定每个学生和每个医院对对方类型进行排名,但是现在我们允许在排名中出现并列.例如$(n=4)$,一个医院能够说排在第一位的是$s_1$;$s_2$和$s_3$并列第二位(两者之间没有优先权);$s_4$是后一位.如果在医院的优先表上,$s$排得比$s’$更高(他们不是并列).我们说$h$更爱$s$而不爱$s’$.由于排名中的不可区分,关于稳定性可能存在如下两种自然的看法,并且对每种看法我们可以问稳定匹配的存在性问题.

1. 在一个完美匹配$M$中的强不稳定因素由一个学生$s$和一个医院$h$组成,使得每个$s$和每个$h$都宁愿要其他人而不要他们目前在$M$中的配对.总是存在一个不具有强不稳定因素的完美匹配吗?给出一个具有优先表的学生和医院集合的例子,对它的每个完美匹配都有一个强不稳定因素;或者给出一个算法保证找到不具有强不稳定因素的完美匹配.
2. 在一个完美匹配$M$中的弱不稳定因素由一个学生$s$和一个医院$h$组成,使得他们在$M$中的配对分别是$h’$和$s’$且下述之中的一条保持:
   • $s$更加偏爱$h$而不是$h’$,且$h$要么更加偏爱$s$而不是$s’$​,要么这两个选择之间的优先权是中立的(理解为$s$和$s’$在$h$的优先级考虑中相同).
   • $h$更加偏爱$s$而不是$s’$,且$s$要么更加偏爱$h$而不是$h’$,要么这两个选择之间的优先权是中立的(理解为$h$和$h’$在$s$的优先级考虑中相同).
   换句话说,在$s$和$h$​之间要么双方都很愿意,或者一方更愿意而另一方却认为中立.总是存在一个不具有弱不稳定因素的完美匹配吗?给出一个具有优先表的学生和医院集合的例子,对它的每个完美匹配都有一个弱不稳定因素;或者给出一个算法保证找到不具有弱不稳定因素的完美匹配.

Answer:

避免强不稳定因素采用以Gale-Shapley算法为基础的修改版算法.改进点在于考虑到中立造成的相等优先性,于是在每个循环中将$s$的最高优先级项统一作为一个列表输出;随后对于列表中的$h$依次再进行迭代,$h$根据自己的优先级决定是否接受$s$:倘若$s$的优先级更高,则考虑接受$s$,否则将保持原状.实现的伪代码如下:

func FindPerfectMatchingWithNoStrongInstability(S,H)
{
    initially let s,h free for s in S,for h in H
    var Result={}

    while(exist free s in S && s hasn't proposed to every h in H)
    {
        let h_list=[h for h which h is the highest-ranked for s to whom s has not yet proposed]

        for(h in h_list)
        {
            if(h is free)
            {
                Engage(s,h) to Result
                break
            }
            else
            {
                let s'=the student currently engaged to h
                if(h prefers s to s')
                {
                    Engage(s,h) to result
                    let s' free
                }
                else continue
            }
        }
    }

    return Result
}

避免弱不稳定因素时的大体算法和避免强不稳定因素时相同,区别在于$h$在根据优先级决定是否接受$s$时,如果$s$的优先级与$s’$是对等的,那么也是可以被接受的.

func FindPerfectMatchingWithNoWeakInstability(S,H)
{
    initially let s,h free for s in S,for h in H
    var Result={}

    while(exist free s in S && s hasn't proposed to every h in H)
    {
        let h_list=[h for h which h is the highest-ranked for s to whom s has not yet proposed]

        for(h in h_list)
        {
            if(h is free)
            {
                Engage(s,h) to Result
                break
            }
            else
            {
                let s'=the student currently engaged to h
                if(h prefers s to s' || h is indifferent between s and s')
                {
                    Engage(s,h) to result
                    let s' free
                }
                else continue
            }
        }
    }

    return Result
}

Ex1.6

Translated Problem:

逍遥运输线(PSL)公司是一家拥有$n$条船并且为$n$个港口提供服务的航运公司.每条船有一张时间表.对这个月的每一天,这个时间表要么标明它正停泊在哪个港口,要么标明它正在出海.(假定一个月有$m$天,并且$m>n$)在这个月里每条船停泊每个港口的时间恰好为1天.为了安全起见,PSL公司规定:

同一天不能有两条船停在同一个港口.

公司想在这个月通过以下方案对旗下的所有船只进行维护:他们打算截断每条船的时间表.对每条船$S_i$,将会在某一天当它到达它时间表上的港口后,它需要停港至月底进行持续维护,这意味着这个月里$S_i$将不能再访问它时间表上的剩余港口,这是允许出现的情况.因此$S_i$时间表的截断方案只不过由它开始的时间表直到它到达港口P的指定的一天组成.截断时间表的后半部分它将一直驻港P进行维护.

现在公司提出了如下问题:给定每条船的时间表,找出每条船的截断方案并且还需要使得公司的安全条件继续保持:同一天始终没有两条船停在同一个港口.证明总可以找到这样一组截断方案,并且给出找到他们的算法.

例如:假设有2条船和2个港口,而这个月一共有4天.他们的时间表如下

在这个场景中,唯一的截断方式是第三天起$S_1$泊$P_2$,第二天起$S_2$泊$P_1$.

Answer:

针对这个问题,可以选择从第$m$天开始倒序遍历,如果遍历到的当天有船只$S_i$入港$P_j$,并且$S_i$还没有被分配到驻港的港口,则将港口$P_j$分配给$S_i$(倘若$P_j$已经有此前分配的船只,将该船只重新设置为未分配的状态).直到所有船只都分配到驻港港口后,遍历结束.实现的伪代码如下:

func FindTruncatedSchedule(schedule)
{
    get m,n,Ports,Ships from schedule
    initially let ship,port free for ship in Ships,for port in Ports

    while(exist free s in S)
    {
        for(day from m-1 to 0)
        {
            if(schedule[day] has ship visiting port)
            {
                get dict{ports,ships}
                for(port,ship in dict)
                {
                    if(port has ship' stay)
                    {
                        let ship' free
                    }
                    let ship stay in port
                }
            }
        }
    }

    return Ports,Ships
}

通过反证法可以证明这种算法总可以找到这样至少一组截断方案:假设不存在一种方式使得所有船只都能在满足条件的情况下找到截断方案.这意味着至少存在一艘船$S_x$,在其任何可能的截断点,都会与另一艘船在同一港口冲突.但根据我们的算法,每次$S_x$到达一个港口且该港口已被其他船只$S_y$选中时,$S_y$将会被重新置为未分配状态,为$S_x$让出空间.这保证了即使存在冲突，也会通过重新分配来解决,从而为$S_x$找到一个不冲突的截断点.

Ex1.8

Translated Problem:

关于这个问题,我们将会探索在稳定匹配问题尤其是G-S算法中的真实性问题.基本的问题是:一个学生或者一个医院能够通过谎称他们的优先表以便得到更好的结果吗?更具体地说,我们假设每一个参与者有一个真实的优先顺序.现在考虑一个医院$h$.假设$h$更加偏向学生$s$而不是$s’$,但是$s$和$s’$在它的优先表上都是低位.通过交换$s$和$s’$在它的优先表上的次序(即通过$h$更加偏向学生$s’$而不是$s$的假声明)并且用这个假优先表运行算法,在结束时$h$将拥有比$s$和$s’$真的更偏向的学生$s”$.这种情况可能发生吗?(我们可以对学生问同样的问题,但是对于这个问题,我们将集中考虑医院的情况)

通过做下面两件事中的一件重新求解这个问题:

1. 证明对任何一组优先表,交换表中一对学生的顺序不可能改善G-S算法中一个医院的选择;
2. 给出一组优先表的例子.对于他存在一个交换,且它将能够改善交换了优先表的医院的选择;

Answer:

通过反证法来进行证明对任何一组优先表,交换表中一对学生的顺序不可能改善G-S算法中一个医院的选择:假设存在一种情况,在这种情况下,某个医院$h$通过在其优先列表中交换两个学生$s$和$s’$的顺序,能够获得一个它更偏好的学生$s”$作为最终匹配.如果这样的话,意味着在$h$的优先表交换前,$s”$的优先表将$h$放在更低的位置;或者$h$之前选择了一个比$s”$优先级更高的学生.事实上这种前后的变化是不能通过交换$s$和$s’$​的顺序所能完成的.这里出现了矛盾,因而可以得出假设不成立的结论.

所以对任何一组优先表,交换表中一对学生的顺序不可能改善G-S算法中一个医院的选择.