  We introduce a new random input model for bipartite matching which we call
the Random Type Poisson Arrival Model. Just like in the known i.i.d. model
(introduced by Feldman et al. 2009), online nodes have types in our model. In
contrast to the adversarial types studied in the known i.i.d. model, following
the random graphs studied in Mastin and Jaillet 2016, in our model each type
graph is generated randomly by including each offline node in the neighborhood
of an online node with probability $c/n$ independently. In our model, nodes of
the same type appear consecutively in the input and the number of times each
type node appears is distributed according to the Poisson distribution with
parameter 1. We analyze the performance of the simple greedy algorithm under
this input model. The performance is controlled by the parameter $c$ and we are
able to exactly characterize the competitive ratio for the regimes $c = o(1)$
and $c = \omega(1)$. We also provide a precise bound on the expected size of
the matching in the remaining regime of constant $c$. We compare our results to
the previous work of Mastin and Jaillet who analyzed the simple greedy
algorithm in the $G_{n,n,p}$ model where each online node type occurs exactly
once. We essentially show that the approach of Mastin and Jaillet can be
extended to work for the Random Type Poisson Arrival Model, although several
nontrivial technical challenges need to be overcome. Intuitively, one can view
the Random Type Poisson Arrival Model as the $G_{n,n,p}$ model with less
randomness; that is, instead of each online node having a new type, each online
node has a chance of repeating the previous type.
