4.5 Conclusion
After a brief history of stable marriages, I have presented the foundations necessary for working with acyclic preferences: the specific (sometimes colorful) vocabulary, the formalism, the grand theorem of existence, uniqueness, convergence, and a description of the main classes of acyclic preferences, such as global or geometric preferences.
I then detailed the self-stabilization property, and more precisely the time required for complete convergence. I presented techniques that allow bounding or estimating this time for certain specific parameters, and I proposed the use of simulations to highlight the role played by each parameter. One should remember that in the worst case, with asynchronous peers, convergence can be very slow, whereas in practice, it is fairly fast (global preferences), or even very fast (most other preferences).
Finally, I described the distribution of stable partners for a few classes of preferences, by proposing an analysis of this distribution under independence assumptions, then validating and extending these results numerically. For global preferences, I thus highlighted the stratification effect. In figurative terms, in a world where there would be only a single criterion of beauty, the beautiful end up with the beautiful, and the ugly have little choice but to be with the ugly15.
For geometric preferences, it is a small-world effect that occurs, due to the fact that the partner distribution is heavy-tailed, which ensures both locality and long-range links. The image is that of a world governed by homophily (birds of a feather flock together): most of the time, reciprocity allows collaborations between neighbors, but when a peer is rejected by its closest neighbors, it must search further and further, among potential partners who appreciate it less and less the further it must go from its own position.
In the end, I hope to have succeeded in sharing my conception of acyclic preference networks: a possible model for peer-to-peer networks, a varied collection of small mathematical problems, but also a recreational computer science. I am aware that this chapter raises more questions than it provides answers: modeling of random initiative, of agitation, study of new preferences (why not cyclic), arbitrary or even variable graphs and quotas, routing in geometric small-worlds… I will assuredly have neither the time nor the ability to answer all these problems, and consequently, if this chapter gives at least one reader the desire to take an interest in acyclic preference networks, I think it will have perfectly fulfilled its role.
For my part, I plan in the future to try to apply preference networks to practical situations, and to connect them to the work I have done on distribution problems. I believe that acyclic preferences are beginning to have the maturity needed to bring a new perspective to these problems, and I would like to verify this, as I discuss in the next and final chapter.