Cooperative Game Theory and Applications

Let us consider the following situation. Five people, Anna, Bert, Carol, Dave, and Ellen decide to combine forces to start their own business. Each one of them has some skills and some capital to contribute to the venture. After careful analysis of the situation they conclude that they can achieve a yearly profit of 100 (in $10,000). Of course, this amount has to be divided among them. At first assigning 20 to each person seems a reasonable allocation. However, after some additional analysis Dave and Ellen figure out that if the two of them work together without the other three, they can make a yearly profit of 45. This is more than the 40 that they would receive according to the allocation above. Anna, Bert, and Carol also perform some additional analysis and realize that the three of them together can only make a profit of 25. So it is in their interest to keep Dave and Ellen in the group. Consequently, they decide to give 46 to Dave and Ellen, and to divide the remaining 54 equally among the three of them. This seems to settle the problem. To make sure that they cannot do better, Carol, Dave and Ellen decide to find out how much profit the three of them can make without the other two. It turns out that they can make a profit of 70, which is more than the 64 (46+18) that the second allocation described above gives to them. Anna and Bert do not have enough capital to start on their own, so they cannot make any profit with only the two of them. Considering this, they decide to give 71 to Carol, Dave and Ellen, and to divide the remaining 29 equally between the two of them. If Carol, Dave, and Ellen also decide to divide the 71 equally among the three of them some further analysis reveals the following problem. It turns out namely, that Bert, Dave, and Ellen can make a profit of 65 which is more than the last allocation assigns to them (65 > 2 × 71/3+29/2).

Three friends, Fred, Grace, and Henry, are looking into the possibilities of starting a day care center for children from (practically) 0 to 4 years. After a thorough investigation of the local regulations and market, they come to the following assessment of the situation. They need one nursemaid per four children from 0 to 2, and one nursemaid per 10 children from 2 to 4. For each child from 0 to 2 they are required to have 8 square meters available inside, and 4 outside. For a child from 2 to 4 the requirements are 5 and 6, respectively. After calculating all costs they realize that they can make a net profit of $200 per month per child from 0 to 2 and a net profit of $150 per month per child from 2 to 4. (The difference is due to the fact that since there are not many day care centers that accept children form 0 to 2 years they can ask a higher fee for them.) Fred knows 9 people whom he can hire as nursemaids. He has the possibility of renting 260 square meters inside and 200 outside. While considering the possibility of starting a day care center on his own he wants to calculate the maximum profit that he can make while complying with all regulations. Therefore he has to solve the following linear programming problem.¹

Vladimir, Wanda, and Xavier each has a house that he/she wants to sell. Yolanda and Zarik each wants to buy a house. Vladimir values his house at $100,000, Wanda values her house at $150,000, and Xavier values his house at $200,000. Vladimir’s house is worth $80,000 to Yolanda and $150,000 to Zarik, Wanda’s house is worth $200,000 to Yolanda and $120,000 to Zarik, and Xavier’s house is worth $220,000 to Yolanda and $230,000 to Zarik. For the sake of notational shortness, we will divide all numbers by 100,000 in the following discussion. If Vladimir and Yolanda get together they will not be able to reach an agreement since Vladimir values his house at more than it is worth to Yolanda. If Vladimir and Zarik get together they can generate a profit of 1.5−1=0.5. If Wanda and Yolanda get together they can generate a profit of 2−1.5=0.5. If Wanda and Zarik get together they will not be able to reach an agreement since Wanda values her house at more than it is worth to Zarik. If Xavier and Yolanda get together then they can generate a profit of 2.2−2=0.2. If Xavier and Zarik get together then they can generate a profit of 2.3−2=0.3. If they cooperate in coalitions of more than two persons then the matching(s) between the owner of a house and a buyer that generate the most profit has to be found for each coalition. It is clear that coalitions that contain only sellers or only buyers will not generate any profit. In table 3.1, where the cooperative game arising from this situation is given, these coalitions have been left out.

Four mathematics professors, Mrs. Hewitt, Mr. Isaacs, Mrs. Jones, and Mr. Kent have handed in work to be copied to the mathematics department’s copy room. Only one copy machine is functioning so they have to wait for their turn. Mrs. Hewitt was the first to hand in her job which is a referee report that she has completed. She needs to have copies made before she can send it to the editor. Mr. Isaacs, the second one to hand in his job, needs copies of exams that he has to give the next day in class, so he is in a hurry. Mrs. Jones, who handed in third, wants them to make copies of a proposal that she has to send out to apply for a grant. The last one to hand in his job, Mr. Kent, needs copies of a paper that he wants to submit to a journal. By talking to each other they get a notion that there must be a better order to make copies than the order in which they have handed in the work. Since they are mathematicians they decide to analyze the situation systematically. Each one of them writes down how much time his job will take and also how much each additional hour will cost her/him Mrs. Hewitt’s job will take 1 hour and her per hour cost is 1, Mr. Isaacs’ job will take 5 hours and his per hour costs are 10, Mrs. Jones’ job will take 6 hours and her per hour costs are 8, Mr. Kent’s job will take 2 hours and his per hour costs are 3.

Four universities, one in Ohio, one in Pennsylvania, one in Quebec, and one in Rhode Island are considering to invite a speaker from Paris, France, to give lectures at each of the universities. They are studying how to make the costs of travel as low as possible. It is clear to all of them that it does not make sense for each one of them to pay a two way ticket from Paris and back. Once the speaker is in North America they should let him visit each university and then travel back. They want to find an order for him to visit the universities that minimizes the total travel costs. The costs for a one way ticket between Paris and the universities in either direction are: for Ohio, $350, for Pennsylvania, $300, for Quebec, $200, and for Rhode Island, $250. The costs for a one way ticket between the universities in either directions are: Ohio-Pennsylvania, $100, Ohio-Quebec, $150, Ohio-Rhode Island, $150, Pennsylvania-Quebec, $150, Pennsylvania-Rhode Island, $100, and Quebec-Rhode Island, $100. These costs are summarized in table 5.1. After some analysis the universities realize that they will minimize the travel costs if the let the speaker travel form Paris to Pennsylvania, to Ohio, to Rhode Island, to Quebec, and then back to Paris. With this tour the total travel costs are $850. Now they still need a way to divide these costs among them. Simply assigning the cost pertaining to each leg of the tour to the university at which that leg ends will not work, because the speaker will have to return to Paris and the universities will have to cover those costs too.

Four geographically separated communities in the desert, Wasteland Village, Xactustown, Yuccaville, and Zun Valley, are desperate. Their water resources are running out and they don’t see a way to survive. If nothing happens they will have to leave their villages to settle somewhere else. Then, just when they think that everything is lost, a spring is found not too far away. At first there is much rejoicing, but then they have to sit down and decide on a way to build a water distribution system that is as cheap as possible. It is quite evident that to connect each community to the spring is not the cheapest way. In table 6.1 the costs involved in building a water distribution system are given in $10,000. After some analysis they realize that the cheapest thing to do is to build pipes connecting Wasteland Village and Yuccaville directly to the spring, while Zun Valley has a pipe connecting it to Wasteland Village and Xactustown has a pipe connecting it to Zun Valley. Now they have to settle on a way to distribute the costs. The total costs are 6.

Four communities, Amesville, Bethany, Charlestown and Drenton have obtained permission from the county, to which all four of them belong, to build hospitals to service their residents. The county is paying for the costs of building the hospitals under certain conditions. It will not pay for a single community to build a hospital. The communities will have to share hospitals. The county allows any group of two communities to build one hospital, any group of three communities may build two hospitals, and the four communities together may build three hospitals. If a community is not serviced by a hospital it has to fly its patients to a hospital further away at an extremely high cost. The four communities are connected by existing roads. The layout of the four communities is given in figure 7.1. The distances are given in ten miles, i.e., Amesville and Charlestown are connected by a 30 miles long road. The communities can build a hospital anywhere along a road, including at the site of a community.