Charity auctions on social networks

Charitable giving is influenced by many social, psycho-logical, and economic factors. One common way to en-courage individuals to donate to charities is by offering to match their contribution (often by their employer or by the government). Conitzer and Sandholm introduced the idea of using auctions to allow individuals to offer to match the contribution of others. We explore this idea in a social network setting, where individuals care about the contribution of their neighbors, and are al-lowed to specify contributions that are conditional on the contribution of their neighbors. We give a mechanism for this setting that raises the largest individually rational contributions given the conditional bids, and analyze the equilibria of this mech-anism in the case of linear utilities. We show that if the social network is strongly connected, the mechanism al-ways has an equilibrium that raises the maximum total contribution (which is the contribution computed ac-cording to the true utilities); in other words, the price of stability of the game defined by this mechanism is one. Interestingly, although the mechanism is not dominant strategy truthful (and in fact, truthful reporting need not even be a Nash equilibrium of this game), this result shows that the mechanism always has a full-information equilibrium which achieves the same outcome as in the truthful scenario. Of course, there exist cases where the maximum total contribution even with true utilities is zero: we show that the existence of non-zero equilib-ria can be characterized exactly in terms of the largest eigenvalue of the utility matrix associated with the so-cial network.