Assignment games represent a tractable yet versatile model of two-sided markets with transfers. We study the likely properties of the core of randomly generated assignment games. If the joint productivities of every firm and worker are i.i.d bounded random variables, then with high probability all workers are paid roughly equal wages, and all firms make similar profits. This implies that core allocations vary significantly in balanced markets, but that there is core convergence in even slightly unbalanced markets. For the benchmark case of uniform distribution, we provide a tight bound for the workers' share of the surplus under the firm-optimal core allocation. We present simulation results suggesting that the phenomena analyzed appear even in medium-sized markets. Finally, we briefly discuss the effects of unbounded distributions and the ways in which they may affect wage dispersion.
@cite_22: 
@cite_24: Given an n by n matrix X, the assignment problem asks for a set of n entries, one from each column and row, with the minimum sum. It is shown that the expected value of this minimum sum is less than 3, independent of n, if X consists of independent random variables uniformly distributed from 0 to 1.
@cite_0: Analysis of random instances of optimization problems provides valuable insights into the behavior and properties of problem's solutions, feasible region, and optimal values, especially in large-scale cases. A class of problems that have been studied extensively in the literature using the methods of probabilistic analysis is represented by the assignment problems, and many important problems in operations research and computer science can be formulated as assignment problems. This paper presents an overview of the recent results and developments in the area of probabilistic assignment problems, including the linear and multidimensional assignment problems, quadratic assignment problem, etc.
@cite_13: Author(s): Aldous, DJ | Abstract: The random assignment (or bipartite matching) problem asks about An = minπ ∑ni=1 c(i, π(i)) where (c(i, j)) is a n × n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations π. Mezard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EAn → ζ(2) = π2 6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ζ(2) limit and of the conjectured limit distribution of edge-costs and their rank-orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost-optimal matching coincides with the optimal matching except on a small proportion of edges. © 2001 John Wiley a Sons, Inc. Random Struct. Alg., 18, 381-418, 2001.
@cite_25: The random assignment problem is to choose a minimum-cost perfect matching in a complete n µ n bipartite graph, whose edge weights are chosen randomly from some distribution such as the exponential distribution with mean 1. In this case it is known that the expectation does not grow unboundedly with n, but approaches a limiting value c* between 1.51 and 2. The limit is conjectured to be c* = π 2 6, while a recent conjecture has it that for finite n, the expected cost is EA* = ⌆n i=11 I2.
Analysis of random instances of the linear sum assignment problem was first carried by @cite_24 , and was subsequently improved by @cite_13 @cite_25 @cite_22 . For a survey on the topic and other related literature see @cite_0 .