Impact of Ties in Stable Matching Problems
Restricted (Penn State Only)
- Author:
- Sharma, Kanika
- Area of Honors:
- Information Sciences and Technology
- Degree:
- Bachelor of Science
- Document Type:
- Thesis
- Thesis Supervisors:
- Hadi Hosseini, Thesis Supervisor
Edward J Glantz, Thesis Honors Advisor - Keywords:
- Artificial Intelligence
Economics
Computer Science
Information Science Technology - Abstract:
- In Artificial Intelligence, agents refer to intelligent entities that are capable of preference- based decision making. Agents may interact with one another in multi-agent settings, where the decisions of one agent impacts the decisions of another. One real world application of a multi- agent system is online bidding, where agents interact with one another by placing bids to buy and sell resources. One type of multi-agent setting is when agents interact with each other and are ultimately arranged in pairs. Students and colleges represents agents paired in college admissions, Uber clients and drivers are agents paired in ride sharing, or applicants and job openings are agents paired in employment. From these examples comes the focus of this research on two-sided match- ing, where an agent can only be matched with another agent from the partner set. Preferences of agents may contain ties. A matching is considered stable if there does not exist a pair such that both sides of the pair prefer the other to their current matching. The Deferred Acceptance (DA) Algorithm was pro- posed to always guarantee a stable matching. Given a preference profile, the Deferred Acceptance algorithm finds a matching for two sided matching markets by proceeding in rounds in which one side, the proposing side, “proposes” to the other side, the proposed-to side, who chooses to accept or reject based on their own preferences. When weak preferences are present, a tie-breaking rule, a priority ordering of agents, is used to make preferences strict with respect to the tie-breaking rule. The Deferred Acceptance algorithm is not strategy-proof for the “proposed-to side”, meaning agents can strategically misreport their preferences to get matched with an agent that they strictly prefer more to their match under true preferences. This concept is known as strategic manipula- tion. Traditional research on two-sided strategic manipulation has focused on strict preferences. This thesis looks at how a manipulator may misreport preferences to become strictly better off in the context of weak preferences. A tie-breaking rule is shown to make: (1) a fixed woman, and all women, better off when partner man preferences are weak, and (2) a fixed man, and all men, better off when partner woman preferences are weak. Using the tie-breaking rule with weak pref- erences showed that the manipulator is strictly better off when the proposing side tie-breaking rule is known to the manipulator. When ties are used with strategic manipulation, the manipulator is more frequently strictly better off, but at the expense of a lower expected improvement, and mak- ing some women strictly worse off. This thesis looks at variations of the DA algorithm that were proposed for dealing with ties in preference lists and studies their strategic manipulation and new notions of stability that arise with these new algorithms.