The efficiency of educational choices is studied in a search-matching model where individuals face a tradeoff: acquiring formal education or learning while on the job. When their education effort is successful, newcomers directly obtain a high-skill job; otherwise, they begin with a low-skill job, learn-by-doing and then search while on-the-job for a high-skill job. Low-skill firms suffer from hold-up behavior by high-skill firms. The low-skill sector is insufficiently attractive and individuals devote too much effort to formal education. A self-financing tax and subsidy policy restores market efficiency.