#### Introduction to the Special Issue on EC?16

Yiling Chen; Dirk BergemannMotivated by an application in kidney exchange, we study the following stochastic matching problem: we are given a graph G(V,E) (not necessarily bipartite), where each edge in E is realized with some constant probability p > 0 and the goal is to find a maximum matching in the realized graph. An algorithm in this setting is allowed to make queries to edges in E in order to determine whether or not they are realized.

We design an adaptive algorithm for this problem that, for any graph G, computes a (1-eps)-approximate maximum matching in the realized graph G_p with high probability, while making O(log(1/eps p)/(eps p)) queries per vertex, where the edges to query are chosen adaptively in O(log(1/eps p)/(eps p)) rounds. We further present a non-adaptive algorithm that makes O(log(1/eps p)/(eps p)) queries per vertex and computes a (1/2 - eps)-approximate maximum matching in G_p with high probability.

Both our adaptive and non-adaptive algorithms achieve the same approximation factor as the previous best algorithms of Blum et al. (EC 2015) for this problem, while requiring exponentially smaller number of per-vertex queries (and rounds of adaptive queries for the adaptive algorithm). Our results settle an open problem raised by Blum et al. by achieving only a polynomial dependency on both eps and p. Moreover, the approximation guarantee of our algorithms is instance-wise as opposed to only being competitive in expectation as is the case for Blum et al. This is of particular relevance to the key application of stochastic matching in kidney exchange. We obtain our results via two main techniques, namely matching-covers and vertex sparsification that may be of independent interest.

#### Minimizing Regret with Multiple Reserves

Tim Roughgarden; Joshua WangExclusive social groups are ones in which the group members decide whether or not to admit a candidate to the group. Examples of exclusive social groups include academic departments and fraternal organizations. In the present paper we introduce an analytic framework for studying the dynamics of exclusive social groups. In our model, every group member is characterized by his opinion, which is represented as a point on the real line. The group evolves in discrete time steps through a voting process carried out by the group's members. Due to homophily, each member votes for the candidate who is more similar to him (i.e., closer to him on the line). An admission rule is then applied to determine which candidate, if any, is admitted. We consider several natural admission rules including majority and consensus.

We ask: how do different admission rules affect the composition of the group in the long run?

We study both growing groups (where new members join old ones) and fixed-size groups (where new members replace those who quit). Our analysis reveals intriguing phenomena and phase transitions, some of which are quite counterintuitive.

The maximum Nash welfare (MNW) solution -- which selects an allocation that maximizes the product of utilities -- is known to provide outstanding fairness guarantees when allocating divisible goods. And while it seems to lose its luster when applied to indivisible goods, we show that, in fact, the MNW solution is unexpectedly, strikingly fair even in that setting. In particular, we prove that it selects allocations that are envy free up to one good -- a compelling notion that is quite elusive when coupled with economic efficiency. We also establish that the MNW solution provides a good approximation to another popular (yet possibly infeasible) fairness property, the maximin share guarantee, in theory and -- even more so -- in practice. While finding the MNW solution is computationally hard, we develop a nontrivial implementation, and demonstrate that it scales well on real data. These results lead us to believe that MNW is the ultimate solution for allocating indivisible goods, and underlie its deployment on a popular fair division website.

We consider the efficiency of taxation in congestion games with polynomial latency functions along the line of research initiated by [Caragiannis et al., {\em ACM Transactions on Algorithms}, 2010] who focused on both pure and mixed Nash equilibria in games with affine latencies only. By exploiting the primal-dual method [Bil\`o, {\em Proceedings of the 10th Workshop on Approximation and Online Algorithms}, 2012], we obtain interesting upper bounds with respect to a variety of different solution concepts ranging from approximate pure Nash equilibria up to approximate coarse correlated equilibria, and including also approximate one-round walks starting from the empty state. Our findings show a high beneficial effect of taxation which increases more than linearly with the degree of the latency functions. In some cases, a tight relationship with some well-studied polynomials in Combinatorics and Number Theory, such as the Touchard and the Geometric polynomials, arises. In these cases, we can also show matching lower bounds, albeit under mild assumptions; interestingly, our upper bounds are derived by exploiting the combinatorial definition of these polynomials, while our lower bounds are constructed by relying on their analytical characterization.

The human willingness to pay costs to benefit anonymous others is often explained by social preferences: rather than only valuing their own material payoff, people also include the payoffs of others in their utility function. But how successful is this concept of outcome-based social preferences for actually predicting out-of-sample behavior? We investigate this question by having 1067 participants each make 20 cooperation decisions with randomized parameters (eg. outcomes for the self, for the other, benefit/cost ratio of cooperation). We then use machine learning to try to predict cooperative behavior by each participant in each cooperation decision. A representative agent model (a small, shared, set of parameters) predicts better than random but still quite poorly (AUC=.69). Allowing for full heterogeneity across individuals in the mapping from decision-parameters to outcome yields good predictive performance (AUC=0.89). However, this heterogeneous model is complicated and unwieldy, thus we also investigate whether a simpler model can yield similar performance. We find that the vast majority of the predictive power (AUC=0.88) is achieved by a model that allows for three behavioral types. Finally, we show that cannot be well proxied for by other measures in psychology. This final analysis adds further evidence to the literature that human ``cooperative phenotypes'' are indeed meaningful, relatively orthogonal person-level traits.