| Project: | Assignment mechanism |
|---|---|
| Mentor: | Ron Holzman |
| Coworker: | David Ryzak |
Together with David Ryzak we will be working on a project from game theory. Let us consider a situation in which N players (agents), N indivisible items (called houses in this context) and a list of preferences for each agent are given. An assignment is a 1-to-1 pairing of agents to houses. Assignment mechanism will, given the agent's preferences, construct the assignment. We require that the assignment satisfies ex-post-efficiency, equil treatment of equils and strategy proofness.
Efficient assignment is such that no subgroup of agents may exchange houses in a way that will make everyone happier. An ex-post-efficient mechanism will randomize over efficient assignments.
Equil tratment of equils means that players witht the asme preferences will have the same odds of receiving a given house.
Strategy proofness is a very strong requirement that sais that no agent may gain by lying about his preferences.
All of these requirements restrict the assignment mechanism to a considerable extend. In fact, only one mechanism is known to satisfy all of them and that is the Random serial dictatorship (RSD). Under this mechanism, agents are selected randomly unifomally. A selected player will take his top house which is still available and leave with it. This continues until every agent is assigned a house.
As mentioned above RSD satisfies all three axioms we require. The conjecture is that RSD is the only such mechanism. It has been shown to be the case for N<4. During this summer we want to study this conjecture deeper.
Before REU even started we got in touch with the supervisor and talked about the project. This better understanding will be essential in our reasearch. We discussed in particular the case N=3 where the situation is already non trivial and made efford to understand why RSD is the only mechanism satisfying all axioms. We also spent a considerable amout of time woring on our openning presentation.
We continued our discussion for N=3. We also tried to develop simple rules by which one can change the preference profile and only using the simple axioms deduce many elements of the bi-stochastic matrix that describes the assignment.
We were further developing our algorithmic approach to the problem and discussed if and how a computer can help us solve it. The simple swapping rules may be used directly by a computer program to manualy go through all possible preference profiles and solve them one by one.
We formalized the rules that the neighbours (given by swaps) should satisfy. We also focused on what the program can in theory acomplish and that it should therefore include.
We wrote a program that tries to accomplish what is desribed in research log of week 3. At this point, the program works with N=3 and we are carefully examining its outputs.
We made some changes that allow the program to run even for N=4. This required non-trivial changes, since for N=4 the number of profiles is large enough not to allow us to use reccursion in Python. We ran the program, but it didn't find a unique solution.
We investigated further how we can enhance the program. Finally, we added more intially known profiles and implemented ex-post efficiency into the code. Now some elements are marked as known since they are inefficient and thus their probability is zero. In this setting, the program found a unique solution for N=4.
We were further discussing the implications of the program being able to find a solution. This means among other things that the inequalities given by strategy proofness are redundant for N=4. Also, if we wanted to use the same approach for N=5, we would run into difficulities as the number of profiles grows very fast. We estimated that the computation would take about 13 years with the hardware we have.
We finalized work on the closing paper and presentation. We also talked about future work and ideas for a more convetional proof for general number of agents.
[1] Abdulkadiroglu, A. and Sonmez, T., Random serial dictatorship and the core from random endowments in house allocation problems, Econometrica 66 (1998) 689-701.
[2] Bogomolnaia, A. and Moulin, H., A new solution to the random assignment problem, Journal of Economic Theory 100 (2001) 295-328.
[3] Nesterov, A., Fairness and efficiency in strategy-proof object allocation mechanisms, Journal of Economic Theory 170 (2017) 145-168.
This work is supported by CoSP, a project funded by European Union's Horizon 2020 research and innovation programme, grant agreement No. 823748.