求婚大作战

假设有N名单身男子和N名单身女子，每个人对N名异性都有一个单调排序，排序满足传递性并且没有任意两名异性的评价是无差异的。单身男性按照对女性的排序进行求婚，或者求婚成功；如果不成功，或者虽然求婚成功但是之后因另一名男性追求而被甩，则继续向排序中的下一名女性求婚。女性在面临男性求婚时，会接受这些求婚男性中排序最高的一名；并且即使已经接受一名男性的求婚，在之后遇到另一名排序更高的男性追求时，会选择抛弃之前接受求婚的男性。

在这样的规则下，我们可以通过设计对异性的排序，来计算可能的总求婚次数。

很明显，求婚的最少次数乃是N次，也就是说任意两名男性的排序最靠前女性不同，没有两个男性同时追求同一名女性。如此，不论男性的女性排序从第二名开始是怎样的，也不论女性的男性排序如何，所有女性都会接受这唯一一名追求者的求婚，并且不再可能出现分手。因为所有男性都追求到了自己心目中排序第一的女性，且所有女性都不再有别的男性来追求。

求婚的最多次数是N^2-N 1。在这种情况下，有一名女性处在所有男性的排序中的最末位，就是说她在最后才被追求。这就意味着，在第一轮求婚中，必然有两名男性追求同一名女性，从而两名男性中的一名被拒绝。这名男性被拒绝后，去追求排序第二的女性，而他又成功踢走了之前追求这名女性的男性。以此类推，在N名男性每次的追求中，总有两名男性追求同一名女性，从而不断有一名男性被甩，而他又踢走了另一名男性。直到有一名男性将N-1名女性都追求过后失败，不得不去追求排序末位的第N名女性。求婚大作战就此告终，不再有求婚，不再有分手。

还有这样一个典型例子，所有男性心目中的女性排序都完全一致。那么无论女性对男性的排序如何，求婚的次数都是N(N 1)/2。在这种诡异的例子中，所有男性首先都一窝蜂地去追求心目中共同的排名第一的女神，然后这名女神只向其中一名男性发一份offer。这名男性不再会被挖墙脚，因为已经是女性心目中排序最高的。然后剩下的N-1名男性又立刻调转枪头，去追排名第二的女性。以此类推，到最后一名男性去追最后一名女性为止。

对所有的自然数，N^2-N 1>=N(N 1)/2。所以求婚次数的区间是[N,N^2-N 1]。这其中的自然数都可以被取到。因为不难想到，只要将任意两名追求不同女性的男性的女性排序进行调整，改为两人先追求同一名女性，然后被拒绝的一方再去追求另一名女性，就能增加一次求婚次数。

这里举出的三个例子是颇有些意思的。可以看到，第一个例子的求婚次数weakly的最少，第三个例子其次，第二个例子求婚次数最多。不得不想到，人与人之间审美观的不同，欣赏异性的标准的不同，或者说生物学上可能就注定的各自喜欢的异性的不同是有意义的。如果所有人都公认地最喜欢某一个人，另一个人其次等等，那么其结果就是如同长公主在城头点驸马，男性倾城而出去追求，其中某位翩翩少年被点中；然后怏怏的其他男子们又突然呼喊着二公主的名字跑去宫墙的那头去追求二公主。反之，如若不同的人喜欢着不同的人，那在婚配上就少了许多这样的竞争。

当然，即使是所有人的异性排序都相同，也较之错配要好。所谓的错配就是如同例二的样子。我喜欢你，你喜欢他，他又喜欢另一个她。于是往往就会出现如螳螂捕蝉黄雀在后般的，我去松人家的土，结果自己又被别人挖了墙角。

那么既然能够通过每个人对异性的排序来推断出最后的婚配结果。如果这种排序不再是私人信息，是否也就能够少了许多这样的纠结呢。非诚勿扰不再是男嘉宾一个一个地依次上来追求女嘉宾，而是男女嘉宾齐登场站一块儿，然后大家都把自己的心动女生心动男生写出来。

所以是否可以说，有情人确实终成眷属，然而实际上从一定意义上而言，成了眷属的常常不是彼此的最爱，而仅仅是一种妥协的博弈的次优选择的结果。你去追求她，是因为你更喜欢的女生都追求不到了；她接受你，是因为她更喜欢的男生没有去追求她。

仅仅因为无聊赖，从Shapley而来的一道题扯淡这许多。毕竟只是纯粹的数学游戏罢了，于是后面的扯淡也就是数学游戏上的扯淡。