Bounded unpopularity matching in a (3, 3)-hypergraph with one-sided preferences

We solve the following problem: given two sets of different items and a set of people with combined preferences over pairs of items, one from each set, what is the best way to match the pair of items to the people? To solve this problem, we consider the popular matching problem in a 3-uniform 3-partite hypergraph, where the first set comprises agents, while the second and third sets contain distinct items respectively. Agents have preferences over the hyperedges, whereas the members of the other sets lack such preferences. An agent votes for a matching in which he/she obtains a better assignment. A matching M is called popular if there is no matching M' such that the number of agents that prefer M' is more than the number of agents that prefer M. Finding a popular matching, if it exists, is a hard problem. Therefore, one approach is to find a matching that is approximately popular. The usual metric in this case is called the unpopularity factor of a matching M, denoted by u(M). In this paper, we provide an approximation algorithm that produces a matching M in a 3-uniform 3-partite hypergraph such that $u(M) \leq 1.5 \times {3^{\frac{k}{2}}}$ where k is the maximum degree of an agent. The approximation algorithm takes O(k(n<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1.5</sup> + m)) time to produce the matching M where n is the total number of agents and m is the total number of hyperedges. In a 3-uniform 3-partite hypergraph where k is a constant, our algorithm performs well and produces a matching M with u(M) = O(1). Importantly, our approach stands as the inaugural algorithm to achieve a bounded unpopularity matching in a hypergraph.