Marriages

Maximum weighted bipartite matching is a well-known optimization problem. Inspired (loosely) by its emergence in sponsored search, researchers have studied their exploration + exploitation versions where nodes or edges may arrive in some order and some weights are observed before committing to the matching (eg., as in graph secretary problems).

I would like to see similar formulations for the well-known stable marriages problem. This formulation should consider the gradual revealing of preferences. What FOCS/STOC/SODA style formulation will lead to pretty math and powerful technical results, motivations entirely aside?