Human Matching Behavior in Social Networks: An Algorithmic Perspective

<div><p>We argue that algorithmic modeling is a powerful approach to understanding the collective dynamics of human behavior. We consider the task of <em>pairing up</em> individuals connected over a network, according to the following model: each individual is able to propose to <em>match</em> with and accept a proposal from a neighbor in the network; if a matched individual proposes to another neighbor or accepts another proposal, the current match will be broken; individuals can only observe whether their neighbors are currently matched but have no knowledge of the network topology or the status of other individuals; and all individuals have the common goal of maximizing the total number of matches. By examining the experimental data, we identify a behavioral principle called <em>prudence</em>, develop an algorithmic model, analyze its properties mathematically and by simulations, and validate the model with human subject experiments for various network sizes and topologies. Our results include i) a -<em>approximate maximum</em> matching is obtained in logarithmic time in the network size for bounded degree networks; ii) for any constant , a -<em>approximate maximum</em> matching is obtained in polynomial time, while obtaining a <em>maximum</em> matching can require an exponential time; and iii) convergence to a maximum matching is slower on preferential attachment networks than on small-world networks. These results allow us to predict that while humans can find a “good quality” matching quickly, they may be unable to find a maximum matching in feasible time. We show that the human subjects largely abide by <em>prudence</em>, and their collective behavior is closely tracked by the above predictions.</p>