In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
--------
Question: We study truthful mechanisms for matching and related problems in a partial information<lb>setting, where the agents’ true utilities are hidden, and the algorithm only has access to ordi-<lb>nal preference information. Our model is motivated by the fact that in many settings, agents<lb>cannot express the numerical values of their utility for different outcomes, but are still able<lb>to rank the outcomes in their order of preference. Specifically, we study problems where the<lb>ground truth exists in the form of a weighted graph of agent utilities, but the algorithm can<lb>only elicit the agents’ private information in the form of a preference ordering for each agent<lb>induced by the underlying weights. Against this backdrop, we design truthful algorithms to<lb>approximate the true optimum solution with respect to the hidden weights. Our techniques<lb>yield universally truthful algorithms for a number of graph problems: a 1.76-approximation<lb>algorithm for Max-Weight Matching, 2-approximation algorithm for Max k-matching, a 6-<lb>approximation algorithm for Densest k-subgraph, and a 2-approximation algorithm for Max<lb>Traveling Salesman as long as the hidden weights constitute a metric. We also provide im-<lb>proved approximation algorithms for such problems when the agents are not able to lie about<lb>their preferences. Our results are the first non-trivial truthful approximation algorithms for<lb>these problems, and indicate that in many situations, we can design robust algorithms even<lb>when the agents may lie and only provide ordinal information instead of precise utilities.

Answer: Truthful Mechanisms for Matching and Clustering in an Ordinal World


Question: Distortion of the underlying speech is a common problem for single-channel speech enhancement algorithms, and hinders such methods from being used more extensively. A dictionary based speech enhancement method that emphasizes preserving the underlying speech is proposed. Spectral patches of clean speech are sampled and clustered to train a dictionary. Given a noisy speech spectral patch, the best matching dictionary entry is selected and used to estimate the noise power at each time-frequency bin. The noise estimation step is formulated as an outlier detection problem, where the noise at each bin is assumed present only if it is an outlier to the corresponding bin of the best matching dictionary entry. This framework assigns higher priority in removing spectral elements that strongly deviate from a typical spoken unit stored in the trained dictionary. Even without the aid of a separate noise model, this method can achieve significant noise reduction for various non-stationary noises, while effectively preserving the underlying speech in more challenging noisy environments.

Answer: SINGLE CHANNEL SPEECH ENHANCEMENT USING OUTLIER DETECTION


Question: The Stable Matching Problem with Couples (SMP-C) is a ubiquitous real-world extension of the stable matching problem (SMP) involving complementarities. Although SMP can be solved in polynomial time, SMP-C is NP-Complete. Hence, it is not clear which, if any, of the theoretical results surrounding the canonical SMP problem apply in this setting. In this paper, we use a recently-developed SAT encoding to solve SMP-C exactly. This allows us to enumerate all stable matchings for any given instance of SMP-C. With this tool, we empirically evaluate some of the properties that have been hypothesized to hold for SMP-C. We take particular interest in investigating if, as the size of the market grows, the percentage of instances with unique stable matchings also grows. While we did not find this trend among the random problem instances we sampled, we did find that the percentage of instances with an resident optimal matching seems to more closely follow the trends predicted by previous conjectures. We also define and investigate resident Pareto optimal stable matchings, finding that, even though this is important desideratum for the deferred acceptance style algorithms previously designed to solve SMP-C, they do not always find one. We also investigate strategy-proofness for SMP-C, showing that even if only one stable matching exists, residents still have incentive to misreport their preferences. However, if a problem has a resident optimal stable matching, we show that residents cannot manipulate via truncation.

Answer:
Exploring Strategy-Proofness, Uniqueness, and Pareto Optimality for the Stable Matching Problem with Couples