  We study Matching and other related problems in a partial information setting
where the agents' utilities for being matched to other agents are hidden and
the mechanism only has access to ordinal preference information. Our model is
motivated by the fact that in many settings, agents cannot express the
numerical values of their utility for different outcomes, but are still able to
rank the outcomes in their order of preference. Specifically, we study problems
where the ground truth exists in the form of a weighted graph, and look to
design algorithms that approximate the true optimum matching using only the
preference orderings for each agent (induced by the hidden weights) as input.
If no restrictions are placed on the weights, then one cannot hope to do better
than the simple greedy algorithm, which yields a half optimal matching. Perhaps
surprisingly, we show that by imposing a little structure on the weights, we
can improve upon the trivial algorithm significantly: we design a
1.6-approximation algorithm for instances where the hidden weights obey the
metric inequality. Using our algorithms for matching as a black-box, we also
design new approximation algorithms for other closely related problems: these
include a a 3.2-approximation for the problem of clustering agents into equal
sized partitions, a 4-approximation algorithm for Densest k-subgraph, and a
2.14-approximation algorithm for Max TSP. These results are the first
non-trivial ordinal approximation algorithms for such problems, and indicate
that we can design robust algorithms even when we are agnostic to the precise
agent utilities.
