Algorithmic Approach of Majority Voting With Agents’ Inclusiveness for Facility Resource Matching

In a two-sided matching with preferences, an agent has preferences over the agents from the other side. In a head-to-head election between any two matching, the agent votes for the matching with a better allocation in pairing based on its preference. A matching <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</i> is popular when the number of votes for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</i> is not less than the number of votes for any other matching <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</i>′ in such an election. A <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i>-popular matching is introduced recently with a two-sided matching model where U and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">W</i> are the two sets of agents, but only the preferences of the agents from <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i> are emphasized, and the preferences of the agents from <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">W</i> are ignored. The matching which is popular among the votes of the agents from <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i> is defined as <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i>-popular. We consider such a model for a one-to-one matching where the agents from <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i> have an inclusive mindset and want to integrate the voting decision of the agents from <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">W</i> into their voting process. In parallel, the agents from <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">W</i> rely more on their ranking on the preference list of the agents from <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i> than their own preferences due to the uncertainty involved in the construction of their preferences.We define an inclusive voting model with such a predominant-subordinate agent scenario (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i> as predominant, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">W</i> as subordinate) and prove that the Boston mechanism matching is <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i>-popular under the model. However, it is possible that the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i>-popular matching is not the choice of the majority of agents. The choice to be neutral is added in the voting process, and the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i>-neutral matching type is introduced when the majority of agents vote for neutral. We characterize the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i>-neutral and max-size <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i>-neutral matching under the inclusive voting model and propose a polynomial-time algorithm to determine a max-size <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i>-neutral matching. The experiments we performed with synthetic instances endorse the algorithm based on the theoretical foundations established.