Game Theory - Fair And Envy-Free Cake Cutting скачать в хорошем качестве

Game Theory - Fair And Envy-Free Cake Cutting

How to fairly cut cakes is a classic mathematical problem which can be considered as a metaphor for a group of real-world problems. There are two requirements for the cutting solution, namely, Fairness and Envy-Free. Fairness means that, if there are N players to attend the game to cut a cake, the final solution will make each of them feel that they get at least 1 over N of the cake. You may wonder why each of them will get no less than 1 over N but the total is 1? This 1 over N is a subjective interpretation from an individual player instead of the physical size. For example, some people prefer chocolate to fruits. So they will consider the parts containing more chocolate are better than the part having more fruits, although the two parts are the same size, and thus think they will get more than 1 over N if they choose the parts having more chocolate. Another requirement to cut the cake is the envy-free solution. Although a player may get a part more than 1 over N, if some other players get more than him, he may envy them. For example, if there are three players in the game, and from player 1's perspective, he gets one third of the total cake and the other two players get one fourth and 5 over 12 respectively. So, for player 1, although he gets at least one third of the cake. However, it is not an envy-free solution because the third player gets more than him. So, envy-free is an enhanced requirement than fairness. An envy-free solution must be a fair solution, but not vice versa. This video will introduce the famous Selfridge-Conway procedure which perfectly provides the fairly and envy-free solution for dividing a cake for three players. Let's consider a simple scenario in which two players are in the game. How to provide a fair and evey-free solution for two players? The simple solution will be that player 1 cuts the cake and player 2 will do the pick-up first. Since player 2 will pick up first, player 1 will honestly divide the cake evenly into two pieces from his perspective. No matter which one player 2 takes, player 1 will believe that he gets 1/2 of the cake and there will be no envy. For player 1, since he will be the person to pick up first. He will definitely choose the one which he thinks to be better than another piece. So, this procedure will be a fair and envy-free solution. Also, we have a conclusion that the person who picks up first will not envy the one who picks up after him. If there are three players in the game, the procedure will be more complicated. The first step, player 1 will cut the cake into three pieces from his perspective and let other players choose first. Similar to the 2-player case, to avoid the result that he will get the smallest part, player 1 will try his best to divide the cake evenly into 3 pieces. The second step, let player 2 and player 3 pick up their favorite pieces. If they pick up different pieces, then the third piece will be assigned to player 1 and the whole problem will be resolved. Everybody will be happy with what they get and there will be no envy. If player 2 and play 3 are both picking up the same piece, say piece C. The third step, if player 2 think the ranking of those 3 pieces are C, B and A, then we will ask player 2 to cut a small piece off from piece C to make the leftover the same size as piece B. Let's name this extra piece as D. Then we ask player 3 to pick up one from the modified piece C and piece B. We will create a rule like this. If player 3 doesn't pick up the modified piece C, player 2 must pick it up. This means that modified piece C cannot be left to player 1. The fourth step, if player 3 picks up the modified piece C, then player 2 will cut the extra piece D into three pieces, say D1, D2 and D3, which will be picked up via the following turn : player 3, player 1 and player 2. Now, let's consider how each player will consider what they get. Since player 3 picks up C and player 2 picks up B, player 1 will get A. From player 1's perspective, he will finally get 1/3 of the cake plus one of D1, D2 or D3. Since he will pick up those small pieces before player 2. So, he will not envy player 2. Of course, he will not envy player 3 either because, from player 1's point of view, player 3 didn't even get 1/3 of the cake. For player 2, since he cut D evenly into D1, D2 and D3. He will finally get B plus one of those three pieces. From player 2's point of view. D1, D2 and D3 are the same. B and modified C will be bigger than A. So, player 2 will not envy other players because he won't think they will get more. For player 3, he will also think B and modified C will be bigger than A. He takes the modified C plus a piece from D1, D2 and D3. Since he will pick up the small piece before other players, he will not envy them. For now, everyone picks up their own parts and everyone will be happy.