Monday, October 3rd, 2016 | 4pm-5pm | Burnside 1205 |

Rensselaer Polytechnic Institute

Blind, Greedy, and Random: Ordinal Approximation Algorithms for Matching
and Clustering

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 the problem of clustering agents into equal sized partitions, Densest k-subgraph, and Max TSP. These results indicate that it is possible to design robust algorithms even when we are agnostic to the precise agent utilities.