Embedded Files
Project Title: Better Matching Algorithms
Project Title: Better Matching Algorithms
I am particularly interested in computational social choice - finding computationally efficient ways in which a group of self-interested agents can make collective decisions that also satisfy properties such as fairness, incentive to be truthful, and overall social welfare. This is relevant to politics and economics, and also to multiagent systems in AI.
Project Description
This project concerns one-sided matching (also known as house allocation), in which N agents each have preferences over N objects, and each agent must receive a single object. This has applications to college dorm assignment, military postings, etc. A related model is important for school choice programs. We seek algorithms that produce a match with good properties (e.g. fairness, efficiency, incentives to be truthful). I have identified a class of (mostly new) such algorithms to explore in detail. The work will require implementing the algorithms in code, thoroughly analyzing their performance on simulated data, and, where possible, proving that they satisfy or do not satisfy various important properties.
Learning Outcomes
Use statistical software such as R;
Prove basic results about formally specified algorithms;
Recall substantial domain knowledge from social choice/matching.
Prerequisites
Basic programming, basic math classes for CS majors.
Report abuse