David Ryzak's REU 2021 Web Page

About Me

Name: David Ryzak
Email: david.ryzak99@gmail.com
Home Institution: Charles University, Prague
Project: Assignment mechanism
Mentor: Ron Holzman
Coworker: David Sychrovsky

Project description

I deal with game theory in project of mine in DIMACS REU 2021. To be more specific it is about mechanism design. In mechanism design we usually want to design a mechanism which satisfies a given properties i.e. the mechanism behaves in a desirable way. In this project we know how a mechanism look like for a given model and we want to know if it is unique. Consider the following model. Let $N$ be a number of players and number of indivisible objects (e.g. houses). Each player have a list of strict preferences of houses. We seek a mechanism which provides, as a function of the individual rankings, a one-to-one (possibly randomized) assignment of the objects to the players. Widely used such a mechanism is Random serial dictatorship (RSD). RSD is a mechanism with the following description: the players are randomly ordered, and each one in his turn chooses the best object for him among those still available. Let us consider the following properties of an assignment mechanism: Strategy proofness (no one can gain by lying about his preferences), Ex-post efficiency (assignment mechanism randomize over efficient assignments) and Equal treatment of equals (players with same preferences have the same chances to get each house). RSD is a mechanism which satisfies these three properties. The question we study in this project is the following: Is RSD the only assignment mechanism satisfying these three properties? For $N\geq$4 it is an open question which we study.

Research Log

Week 1

I was already in a contact with my mentor Ron Holzman and coworker David before REU officialy started. That enable us to well understand what is the problem we deal with. I managed to understand better how to work with properties of a mechanism. For this purpose I thought about the problem for 3 players and at least partially solved this known part of the problem. We also made a presentation shortly explaining proposed properties of a mechanism and the problem itself.

Week 2

During the presentation day on Tuesday it was nice to see what interesting projects are people in REU working on.
I tried to understand how to tackle the problem for $N=3$ more systematically. I also found an example of a mechanism which is simillar to RSD however it is not strategy proof. This example yields better understanding that the strategy proofness is really a crucial property. On a meeting we discussed the example and other ways how to think about the problem on the examples with 3 players. We also talked about a possible way how to strenghten one of the properties (Equal treatments of equals). The conjecture with stronger assumptions about properties should be easier to prove and may provide a better insight in the problem for the original conjecture.

Week 3

I mostly went more properly through the papers from references to see how to think about the assignment problem in a greater picture, than just from the perspective of our problem, the uniqueness of RSD. I also tried to come up with an idea which would enable us to transform the problem to another probably simpler problem, unfortunatelly I have not been succesfull yet. On the meetings we discussed how to deal with greater number of players. Naturally, we would like to use mathematical induction in some way but the induction in the way we talked about it is not enough alone because it deals only with small number of preference profiles.

Week 4

At the beginning I looked at the possible use of induction and I thought about it more precisely. Although the idea of induction looks promising, the way we thought about it is not enough. It does not deal with sufficient number of preference profiles. We also tried to look for analogy of our model with model where agents has utilities over houses. At the end of the week I started to look at the problem for $4$ players where the situation is already really complicated.

Week 5

The main focus this week was discussion about the case $N=4$. Unfortunatelly we got no major results in understanding $N=4$. We discussed a computer program which could be useful for telling us whether the way we try to go is not completely wrong. On a meeting we discussed geometrical interpretaition of the problem. Although the Ex-post efficiency has a nice geometrical interpretaition other two properties of a mechanism in some sense does not. However, the other two properties gives quite a lot constrainst which can viewed as set of equations.

Week 6

My coworker David started to write the program and I was glad to talk about it with him. Work was mostly about the better understanding of the case $N=4$. Due to discussions and results from the last week we could reformulate the problem to a problem from linear algebra. Reformulated problem is not much easier (it says something about rank of some matrix), hovewer there is a lot of tools in linear algebra which can be used, so this looks promising.

Week 7

This week was in the name of proving the hypothesis for the small fraction of preference profiles. The reformulated problem from the last week has one big issue, it is not clear what exactly the structure of it is. The only thing we know that it is a matrix. The matrix with the known number of columns and rows. However, to determine whether the rank of the matrix is equal to the number of columns we need to know the structure better. As I have seen the last few weeks the hardest part on this problem is to work with all the properties of a mechanism together.

Week 8

We managed to run the program for $N=4$, which is great. However, it is not a formal mathematical proof, but it can hopefully tells us something more about the structure of the problem. We discussed other possible ways to approach the problem. We also thought about linear programming and its possible application in proving the conjecture. The problem has then quite a nice geometrical interpretaition. However, we did not manage to reformulate the problem in the first place. The reformulation is probably the hardest about it.

Week 9

The most of the last week I was doing the paper or final presentation.

References & Links

[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.

Funding

This research is supported by CoSP, a project funded by European Union's Horizon 2020 research and innovation programme, grant agreement No. 823748.