Trading Card Game Consider a trading card game (TCG) with n players. Each player i=1,2,,n initially receives a different collectible card. Let us index the cards according to their owners: c1,c2,,cn, so that player 1 starts with card c1, player 2 starts with card c2, etc. The players want to trade their cards with others, but there is no money/currency. They decide to use the following trading procedure/algorithm: Round 1: Each player points to the owner of their favorite card. Since there are finitely many players, there will be at least one cycle. Each player in a cycle is assigned the card of the aplayer he points to and is removed from the market with his assignment. If there is at least one player left, then proceed to the next round. Round k: Each remaining player points to the owner of their remaining favorite card. Since there are finetly many players, there will be at least one cycle. Each player in a cycle is assigned the card of the aplayer he points to and is removed from the market with his assignment. If there is at least one player left, then proceed to the next round. The algorithm ends when there are no players left. (a) Prove that the algorithm ends in a Pareto Efficient assignment. (b) Prove that the final assignment from the algorithm is the only assignment in the Core, Here is an example demonstrating how the algorithm works: Suppose that preferences of each player over cards are as follows: Player1:c1c2c3c4c5c6c7c8c9Player2:c3c2c1c1c5c6c7c8c9Player3:c4>c2>c3c1>c5>c6>c7>c8>c9Player4:c5>c2>c1c4c3c6>c7>c8c9Player5:c2>c1c3c1c5c0c7cxc0Player6:c1>c7>c3>c4>c5>c6>c2>c8>c9Player7:c4>c6c3c1c3c7c2c8c9Player8:c0>c2>c3>c4>c5>c1>c7>c8c9Playera?:c7>c8c3c4c5c4c2c1c0 In round 1 each player points towards the owner of their favorite card: There are two cycles: player 1 pointing to hamself and the cycle including players 2,3,4,5. This means that the assigntment after rotnd 1 is (p1,c1),(p2,c3),(p1,c4),(p4,c5),(p5,c2). Each of these players in the cycles leave the algorithm forever with the card they pointed to. Note that even though there are other players pointing towards the cyele, they are not part of it (player 7 pointing at player 4). In round 2 there are 4 players left (players 1 through 5 and their cards were already assigned). The remaining players point to the owner of their remaining favorite card. There is one cycle including players 6 and 7 only. They both leave the algorithm with the assignment: (p6,c7),(p7,c6) In round 3 there are two players left: There is one cycle including player 8 only. He leaves holding his initial card (p8,c8). In round 4 there is only player 9 left, he points to the only remaining card 9(p9,c9). Thus the final assignment is: (p1,c1),(p2,c3),(p3,c4),(p4,c5),(p5,c2),(p6,c7),(p7,c6),(p8,c8),(p9,c9) Trading Card Game Consider a trading card game (TCG) with n players. Each player i=1,2,,n initially receives a different collectible card. Let us index the cards according to their owners: c1,c2,,cn, so that player 1 starts with card c1, player 2 starts with card c2, etc. The players want to trade their cards with others, but there is no money/currency. They decide to use the following trading procedure/algorithm: Round 1: Each player points to the owner of their favorite card. Since there are finitely many players, there will be at least one cycle. Each player in a cycle is assigned the card of the aplayer he points to and is removed from the market with his assignment. If there is at least one player left, then proceed to the next round. Round k: Each remaining player points to the owner of their remaining favorite card. Since there are finetly many players, there will be at least one cycle. Each player in a cycle is assigned the card of the aplayer he points to and is removed from the market with his assignment. If there is at least one player left, then proceed to the next round. The algorithm ends when there are no players left. (a) Prove that the algorithm ends in a Pareto Efficient assignment. (b) Prove that the final assignment from the algorithm is the only assignment in the Core, Here is an example demonstrating how the algorithm works: Suppose that preferences of each player over cards are as follows: Player1:c1c2c3c4c5c6c7c8c9Player2:c3c2c1c1c5c6c7c8c9Player3:c4>c2>c3c1>c5>c6>c7>c8>c9Player4:c5>c2>c1c4c3c6>c7>c8c9Player5:c2>c1c3c1c5c0c7cxc0Player6:c1>c7>c3>c4>c5>c6>c2>c8>c9Player7:c4>c6c3c1c3c7c2c8c9Player8:c0>c2>c3>c4>c5>c1>c7>c8c9Playera?:c7>c8c3c4c5c4c2c1c0 In round 1 each player points towards the owner of their favorite card: There are two cycles: player 1 pointing to hamself and the cycle including players 2,3,4,5. This means that the assigntment after rotnd 1 is (p1,c1),(p2,c3),(p1,c4),(p4,c5),(p5,c2). Each of these players in the cycles leave the algorithm forever with the card they pointed to. Note that even though there are other players pointing towards the cyele, they are not part of it (player 7 pointing at player 4). In round 2 there are 4 players left (players 1 through 5 and their cards were already assigned). The remaining players point to the owner of their remaining favorite card. There is one cycle including players 6 and 7 only. They both leave the algorithm with the assignment: (p6,c7),(p7,c6) In round 3 there are two players left: There is one cycle including player 8 only. He leaves holding his initial card (p8,c8). In round 4 there is only player 9 left, he points to the only remaining card 9(p9,c9). Thus the final assignment is: (p1,c1),(p2,c3),(p3,c4),(p4,c5),(p5,c2),(p6,c7),(p7,c6),(p8,c8),(p9,c9)
