This paper gives a new answer to an old question in labor economics, “Who matches with whom?", by introducing a setting where firms and workers are different in many dimensions and we allow workers to be over and under qualified for the jobs they end up occupying. I present a random search model with two side multidimensional heterogeneity in which firms choose and post a wage with commitment i.e. maintaining the posted wage, independent of the productivity of the new worker. Posted wages determine the set of acceptable jobs for each worker and a unique applicants pool for each firm. The composition of these sets varies in size and composition across workers and firms. The optimal posted wage level takes into consideration the requirements of each firm and the characteristics of the applicants pool. In equilibrium, sorting is assortative but mismatches can occur across all skills dimensions. Using French data on workers observed skills and matches, I calculate structural parameters associated with the model for France. I find that the disutility of non cognitive skills is higher when mismatched, while employers value more highly good matches on cognitive skills. I also find that the number of dimensions plays an important role, since it is another source for frictions.