An Algorithm for Matching in a (3,3)‐Hypergraph With One‐Sided Preferences Having Quadratic Unpopularity Factor

ABSTRACT Given two distinct sets of items and a set of agents, each with combined preferences for selecting one item from each set, the question arises: How can we optimally assign pairs of items to agents? To address this, we investigate the popular matching problem in a 3‐uniform 3‐partite hypergraph. In this setting, the first partition represents agents, while the second and third partitions represent two different types of items. Agents express preferences over the hyperedges incident to them, whereas the items have no preferences. A matching is called popular if there exists no matching that a majority of agents prefer over . Since determining the existence of a popular matching is NP‐hard in a 3‐uniform 3‐partite hypergraph, we focus on approximating such matchings using the concept of unpopularity factor . The unpopularity factor is defined as the maximum ratio over all other matchings , where and are the sets of agents preferring the matching and , respectively. We first present an exact algorithm that computes a popular matching in exponential time if it exists, or it notifies the nonexistence of such a matching. To address efficiency, we design an approximation algorithm that constructs a matching in a 3‐uniform 3‐partite hypergraph with unpopularity factor , where is the maximum degree of any agent. Additionally, we show that , where is the number of agents, implying . The approximation algorithm runs in time, where is the number of hyperedges.