  Coalition formation considers the question of how to partition a set of $n$
agents into disjoint coalitions according to their preferences. We consider a
cardinal utility model with additively separable aggregation of preferences and
study the online variant of coalition formation, where the agents arrive in
sequence and whenever an agent arrives, they have to be assigned to a coalition
immediately. The goal is to maximize social welfare. In a purely deterministic
model, the greedy algorithm, where an agent is assigned to the coalition with
the largest gain, is known to achieve an optimal competitive ratio, which
heavily relies on the range of utilities.
  We complement this result by considering two related models. First, we study
a model where agents arrive in a random order. We find that the competitive
ratio of the greedy algorithm is $\Theta\left(\frac{1}{n^2}\right)$, whereas an
alternative algorithm, which is based on alternating between waiting and greedy
phases, can achieve a competitive ratio of $\Theta\left(\frac{1}{n}\right)$.
Second, we relax the irrevocability of decisions by allowing to dissolve
coalitions into singleton coalitions, presenting a matching-based algorithm
that once again achieves a competitive ratio of
$\Theta\left(\frac{1}{n}\right)$. Hence, compared to the base model, we present
two ways to achieve a competitive ratio that precisely gets rid of utility
dependencies. Our results also give novel insights in weighted online matching.
