In Colombia, physicians must work during a year to fulfill a compulsory social service known as año rural. This service constitutes an entry-level labor market which can be modeled as a many-to-one matching market. To match physicians with hospitals, a centralized and equiprobable random drawing is employed in the market. This random mechanism is evaluated here by using axioms of ex-post stability, ex-post efficiency and strategy-proofness. It is underlined in this paper that agents in the market have identified these axioms as a matter of interest. A formal proof shows that the random mechanism violates these axioms.

Three random mechanisms which produce desirable outcomes are presented: Employment by Lotto (Aldershof, Carducci, and Lorenc, 1999; Klaus and Klijn, 2006), Random Order Mechanism (Roth and Vande Vate, 1990; Ma, 1996; Klaus and Klijn, 2006) and Doctor Serial Dictator (Roth, 1982). The first two are both ex-post stable and ex-post efficient, and the latter is ex-post efficient and strategy-proof. It is shown that there is no ex-post stable and strategy-proof random mechanism, extending the result by Roth (1982, 1985) from deterministic to random mechanisms. Considering the concept of doctor-strategy-proofness, it is shown that the deterministic mechanism which leads to the doctor-optimal matching is the unique ex-post stable and doctor strategy-proof mechanism, strengthening the result by Roth (1985).