|
%I #27 Sep 24 2019 10:52:32
%S 1,1,1,48,72,24,746496,1347840,756864,134784
%N Table read by rows: T(n,k) is the number of stable marriage instances with n men and n+1 women in which some "rejecting" woman receives exactly k proposals.
%C The n-th row (which has n+1 items) concerns stable marriage instances with n men and n+1 women. Over all such instances in which the preference list of one woman is empty (i.e., that woman deems all the men as unacceptable matches) consider running men-proposing differed acceptance (the Gale-Shapley algorithm). The k-th item in the row (k=0,...,n) gives the number of those instances in which the rejecting woman receives exactly k proposals over the course of the algorithm.
%C Terms computed by brute force enumeration.
%C Motivation for studying this sequence comes from studying the opportunities for strategic manipulation in bipartite matching markets with more agents on one side than another.
%C The first element of each row is exactly a 1/(n+1) fraction of the row sum. Proof: the probability that the rejecting woman receives zero proposals is exactly the probability that this woman is unmatched when preferences are uniformly random (i.e., if that woman did not reject). But if preferences are uniform, then each woman is equally likely to be unmatched.
%C The distribution of each row is statistically dominated by the following type of "coupon collector" random variable: at each time step, and integer between 1 and n+1 is drawn uniformly. The process stops when each integer between 1 and n has been drawn, and the output is the number of times n+1 was drawn. (Proof sketch: the coupon collector random process exactly corresponds to man-proposing differed acceptance where men always select the next woman to propose to uniformly at random (with repetition).)
%C Using the coupon collector distribution, you can show that the first O(log n) terms of each row comprise at least a (1 - 1/poly(n)) fraction of the row (using a Chernoff bound).
%F Sum_{k=0..n} T(n,k) = ((n+1)!*n!)^n.
%e The first row corresponds to n=0, where there is a unique instance with 0 men and 1 woman (and the woman gets no proposals).
%e The second row concerns stable marriage instances with 1 man and 2 women. There are two such instances (the man chooses either of the women as his top choice). In one of them, the rejecting woman gets a proposal (T(1,1) = 1) and in the other she does not (T(1,0) = 1).
%e The third row has 2 men and 3 women. The men's and the first two women's preference lists are uniform over all permutations of the other side. The final woman has no list and rejects all proposals. Thus there are 6^2*2^2 = 144 total instances. In 48 of these instances, the rejecting woman receives no proposals. In 72, she receives one, and in 24, she receives two (one from each man).
%e The table begins:
%e n | k = 0 1 2 3
%e --+---------------------------------
%e 0 | 1;
%e 1 | 1, 1;
%e 2 | 48, 72, 24;
%e 3 | 746496, 1347840, 756864, 134784;
%e ...
%K nonn,tabl,more
%O 0,4
%A _Clayton Thomas_, Aug 23 2019
| 