How does social welfare change when the two entities do not have the same number of individuals in them, so that not everyone can be matched?
The algorithm works fine in this case. The important assumption is still that the underlying graph is bipartite (and that preferences are transitive). If we allow for members of a given type to propose to each other, then we lose convergence. Suppose we have three players: $A, B, C$. We have $A$'s preferences as $(B, C, A)$; $B$'s preferences as $(C, A, B)$; and $C$'s preferences as $(A, B, C)$. So $A$ proposes to $B$, which accepts. Then $B$ proposes to $C$, which accepts. This unmatches $A$. Next, $C$ proposes to $A$, which accepts. This unmatches $B$. We then repeat.
Are there faster ways to match individuals with each other (lower runtime?)
Gale-Shapley has a runtime complexity of $\Theta(n^{2})$. In graph theory, most bipartite matching algorithms take $\Omega(|E| \sqrt{|V|})$ time. In the worst case, $|E| = |V|^{2}/4$. So I wouldn't bank on much better.
Additionally, this isn't a problem that lends itself well to a divide and conquer approach. It's really a greedy problem. You might be able to get the expected runtime down by selecting a random ordering for proposing. The analysis would be involved though.
It seems like a very weird game theoretic model just because when I read the proof for the validity of the algorithm, it doesn't seem like the problem is "discrete"; that is, optimizing who gets matched with who and finding a Pareto efficient result can't be solved through maximizing a continuous function.
Actually, it's a discrete model. In more traditional fields of economics, we have continuous variables. So linear programming makes sense. We could actually formulate an integer-linear program for the stable-marriage problem if we look at it from a graph theoretic perspective. Matching problems can be formulated in the language of flows. And we can write flow problems as LPs. The flow constraints form a convex polytope. If the graph is bipartite, the vertices of the polytope are the matchings. The trick here is that we have to add additional constraints to ensure we end up with the correct matching (since the matching from the Gale-Shapley algorithm is unique, regardless of the order in which the men propose).
Even if we go to the trouble of formulating the linear program, solving an LP for this problem by hand or by a computer is less efficient than using the algorithm.
(As a side question, is the Gale-Shapley allocation Pareto efficient?)
The matching generated by the Gale-Shapely algorithm is in the core. An imputation belonging to the core satisfies the property that no coalition can collude their initial endowments and improve its members' outcomes. An imputation is Pareto optimal if no set of agents can improve their outcomes without another player's outcome being less favorable. So core allocations are Pareto optimal.
For more on Gale-Shapley, check out my blog: https://michaellevet.wordpress.com/2015/05/22/algorithmic-game-theory-stable-marriage-problem/
