This paper develops several new strategy-proof mechanisms for matching problems with minimum quotas, with an application to a problem of assigning students to labs. Our mechanisms inspired by the well-known TTC mechanism are strategy-proof and Pareto efficient, though may not be fair in the sense of eliminating justified envy. Previous studies have shown that there may be no matching that eliminates all (traditional) justified envy, even if labs have a master list. Thus, we introduce a stronger notion of justified envy, then define two mechanisms based on the famous Gale-Shapley mechanism that eliminates all strong justified envy. These mechanisms are again strategy-proof for the students, but, unlike the TTC-based mechanisms, will not be Pareto efficient. We also identify an additional trade off between our mechanisms depending on whether the minimum quotas are large or small.
The matching problem with minimum quotas is complex. No one mechanism will
be able to satisfy all desirable properties, and thus we provide several mechanisms, giving guidance on which type of mechanism a designer should use depending on the details of the setting and policy goals. If the minimum quotas are small and the designer is more concerned with efficiency, then MS-TTC should be used, while if the designer is more concerned with fairness (justified envy), then MS-GS should be implemented. On the other hand, if the minimum quotas are large, then ES-TTC should be chosen when efficiency is the primary concern, while ES-GS should be used when elimination of justified envy is deemed more important.
In future work, we would like to examine how approximately optimal the match-ings our mechanisms produce are, since they do not minimize the number of blocking pairs. We would additionally like to evaluate how our mechanisms performs when the preferences of the students and labs are correlated.
Chapter 8 Conclusions
8.1 Summary
In the dissertation, we studied coalition formation problem including matching prob-lem from computational point of view. The dissertation deals with two topic; (i) concise representation and (ii) constrained coalition formation.
For (i), we proposed two new concise representations i.e., Distributed Constraint Optimization Problem (DCOP) based representation and type-based representation.
These two representations can represent a characteristic function more concisely com-pared to existing representations. Also, by efficiently using the structure of repre-sentation schemes, we can obtain algorithms for many problems related to coalition formation. Furthermore, we then extend the formalization of coalition structure gen-eration utilizing Marginal Contribution networks in Ohtaet al.[46] to handle negative values and games with externalities.
For (ii), we considered coalition formation problem where allowable coalitions are limited. By utilizing the dual solution of linear problem, we developed new algorithm CoreD for checking the nonemptiness of the core. Furthermore, we propose a new solution concept called the weak ε-core+, which can utilize the approximate value of V(CS∗). We then proposed strategy-proof mechanisms for two sided matching with minimum and maximum quotas. We developed two basic ideas to extend existing mechanisms for matching with minimum and maximum quotas, i.e., extended-seats mechanisms and multi-stage mechanisms. Extended-seats mechanisms can perform well in instances where the minimum quotas are large. On the other hand, multi-stage mechanisms can perform well in instances where the minimum quotas are small.
We believe that these results can contribute to the progress of multi-agent systems and cooperative game theory.
8.2 Future Works
Finally let me outline some future directions in computational coalition formation.
Concise RepresentationOur goal is to develop the representation which should be concise and general and enable efficient computation for solving various problems related to cooperative game theory. Although DCOP-based representation is concise and general representation, we cannot obtain polynomial time algorithm for coali-tion structure generacoali-tion with DCOP-based representacoali-tion since the problem is NP-hard. On the other hand, by using type-based representation, we can compute many problems in polynomial time in the number of agents with fixed number of types.
However, the computation time depends on the number of agent types. Obviously, if all agents have different types, computation time would be exponential. Thus, we have to develop another ideal representation scheme. We believe that we can obtain the representation by combining DCOP-based representation and type-based representation.
Constrained Coalition Formation and Matching In Chapter 6, we assume that monetary transfers among coalitions are allowed. It is interesting future work that extending our results to the case where monetary transfers among coalitions are not allowed. In such a case, forming optimal coalition structure CS∗ is not necessarily best, i.e., a suboptimal coalition structure might have a better payoff vector that can make the coalition structure more stable. Developing an algorithm that can find a desirable pair of a coalition structure and a payoff vector at once will be challenging. Also, for matching mechanisms, it would be interesting to more fully study the potential uses of our mechanisms in real-world markets in which both individual rationality constraints and minimum quotas are present.
References
[1] A. Abdulkadiroglu and T. Sonmez. House allocation with existing tenants. Jour-nal of Economic Theory, 88:233–260, 1999.
[2] A. Abdulkadiroglu and T. Sonmez. School choice: A mechanism design approach.
American Economic Review, 93(3):729–747, 2003.
[3] A. Abizada and S. Chen. The college admission problem with entrance criterion.
2011. mimeo, University of Rochester.
[4] S. Airiau and S. Sen. On the stability of an optimal coalition structure. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI), pages 203–208, 2010.
[5] R. J. Aumann and J. H. Dreze. Cooperative games with coalition structures.
International Journal of Game Theory, 3:217–237, 1974.
[6] H. Aziz and B. de Keijzer. Complexity of coalition structure generation. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 191–198, 2011.
[7] H. Aziz, O. Lachish, M. Paterson, and R. Savani. Power indices in spanning connectivity games. InProceedings of the 5th International Conference on Algo-rithmic Aspects in Information and Management (AAIM), pages 55–67, 2009.
[8] Y. Bachrach and E. Elkind. Divide and conquer: false-name manipulations in weighted voting games. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 975–982, 2008.
[9] Y. Bachrach, E. Elkind, R. Meir, D. V. Pasechnik, M. Zuckerman, J. Rothe, and J. S. Rosenschein. The cost of stability in coalitional games. In Proceedings of the 2nd International Symposium on Algorithmic Game Theory (SAGT), pages 122–134, 2009.
[10] Y. Bachrach and J. S. Rosenschein. Coalitional skill games. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1023–1030, 2008.
[11] Y. Bachrach, J. S. Rosenschein, and E. Porat. Power and stability in connectiv-ity games. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 999–1006, 2008.
[12] B. Banerjee and L. Kraemer. Coalition structure generation in multi-agent sys-tems with mixed externalities. InProceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 175–182, 2010.
[13] G. Chalkiadakis, E. Elkind, and N. R. Jennings. Simple coalitional games with beliefs. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), pages 85–90, 2009.
[14] G. Chalkiadakis, E. Elkind, and M. Wooldridge. Computational Aspects of Co-operative Game Theory. Morgan and Claypool Publishers, 2011.
[15] A. Chechetka and K. Sycara. No-commitment branch and bound search for dis-tributed constraint optimization. In Proceedings of the 5th International Con-ference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1427–
1429, 2006.
[16] V. Conitzer and T. Sandholm. Complexity of constructing solutions in the core based on synergies among coalitions. Artificial Intelligence, 170(6):607–
619, 2006.
[17] V. D. Dang, R. K. Dash, A. Rogers, and N. R. Jennings. Overlapping coalition formation for efficient data fusion in multi-sensor networks. In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI), pages 635–640, 2006.
[18] M. Davis and M. Maschler. The kernel of a cooperative game. Naval Research Logistics Quarterly, 12(3):223–259, 1965.
[19] R. Dechter. Bucket elimination: A unifying framework for reasoning. Artificial Intelligence, 113(1-2):41–85, 1999.
[20] R. Dechter. Constraint Processing. Morgan Kaufmann, 2003.
[21] X. Deng, T. Ibaraki, and H. Nagamochi. Algorithms and complexity in com-binatorial optimization games. In Proceedings of the 8th Annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 720–729, 1997.
[22] X. Deng and C. H. Papadimitriou. On the complexity of cooperative solution concepts. Mathematics of Operations Research, 19(2):257–266, 1994.
[23] R. Diestel. Graph Theory. Springer, 2005.
[24] L. Ehlers. School choice with control. 2010. mimeo, University of Montreal.
[25] E. Elkind and D. V. Pasechnik. Computing the nucleolus of weighted voting games. In Proceedings of the 20th Annual ACM-SIAM symposium on Discrete algorithms (SODA), pages 327–335, 2009.
[26] D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9–15, 1996.
[27] I. P. Gent. A symmetry breaking constraint for indistinguishable values. In Proceedings of International Workshop on Symmetry in CSPs, pages 469–473, 2001.
[28] D. Gillies. Some Theorems on n-Person Games. PhD thesis, Princeton Univer-sity, 1953.
[29] G. Greco, E. Malizia, L. Palopoli, and F. Scarcello. On the complexity of core, kernel, and bargaining set. Artificial Intelligence, 175(12-13):1877–1910, 2011.
[30] G. Greco, E. Malizia, L. Palopoli, and F. Scarcello. On the complexity of the core over coalition structures. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 216–221, 2011.
[31] K. Hamada, K. Iwama, and S. Miyazaki. The hospitals/residents problem with quota lower bounds. InProceedings of the 19th Annual European Symposium on Algorithms (ESA 2011), pages 180–191.
[32] J. W. Hatfield and P. R. Milgrom. Matching with contracts. American Economic Review, 95(4):913–935, 2005.
[33] G. Hines, T. Rahwan, and N. R. Jennings. An anytime algorithm for finding the epsilon-core in nontransferable utility coalitional games. In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI), pages 414–419, 2012.
[34] S. Ieong and Y. Shoham. Marginal contribution nets: a compact representation scheme for coalitional games. In Proceedings of the 6th ACM Conference on Electronic Commerce (ACM EC), pages 193–202, 2005.
[35] R. W. Irving, D. F. Manlove, and S. Scott. The stable marriage problem with master preference lists. Discrete Applied Mathematics, 156:2959–2977, August 2008.
[36] E. Kalai and E. Zemel. Totally balanced games and games of flow. Mathematics of Operations Research, 7(3):476–478, 1982.
[37] H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, 2004.
[38] K. Leyton-Brown, M. Pearson, and Y. Shoham. Towards a universal test suite for combinatorial auction algorithms. InProceedings of the 1st ACM Conference on Electronic Commerce (ACM EC), pages 66–76, 2000.
[39] R. Mailler and V. Lesser. Solving distributed constraint optimization problems using cooperative mediation. In Proceedings of the 3rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 438–445, 2004.
[40] R. Meir, J. S. Rosenschein, and E. Malizia. Subsidies, stability, and restricted cooperation in coalitional games. InProceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 301–306, 2011.
[41] T. Michalak, J. Sroka, T. Rahwan, M. Wooldridge, P. McBurney, and N. R.
Jennings. A distributed algorithm for anytime coalition structure generation.
In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1007–1014, 2010.
[42] T. P. Michalak, D. Marciniak, M. Szamotulski, T. Rahwan, M. Wooldridge, P. McBurney, and N. R. Jennings. A logic-based representation for coalitional games with externalities. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 125–132, 2010.
[43] P. J. Modi, W.-M. Shen, M. Tambe, and M. Yokoo. An asynchronous complete method for distributed constraint optimization. In Proceedings of the 2nd Inter-national Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 161–168, 2003.
[44] R. B. Myerson. Graphs and cooperation in games. Mathematics of Operations Research, 2(3):225 – 229, 1977.
[45] N. Nisan. Bidding and allocation in combinatorial auctions. In Proceedings of the 1st ACM Conference on Electronic Commerce (ACM EC), pages 1–12, 2000.
[46] N. Ohta, V. Conitzer, R. Ichimura, Y. Sakurai, A. Iwasaki, and M. Yokoo.
Coalition structure generation utilizing compact characteristic function repre-sentations. In Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP), pages 623–638, 2009.
[47] S. Papai. Strategyproof assignment by hierarchical exchange. Econometrica, 68(6):1403–1433, 2000.
[48] N. Perach, J. Polak, and U. G. Rothblum. A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the technion. International Journal of Game Theory, 36:519–535, 2007.
[49] N. Perach and U. G. Rothblum. Incentive compatibility for the stable matching model with an entrance criterion.International Journal of Game Theory, 39:657–
667, 2010.
[50] A. Petcu and B. Faltings. A scalable method for multiagent constraint opti-mization. InProceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), pages 266–271, 2005.
[51] T. Rahwan and N. R. Jennings. An algorithm for distributing coalitional value calculations among cooperative agents. Artificial Intelligence, 171(8–9):535–567, 2007.
[52] T. Rahwan and N. R. Jennings. Coalition structure generation: dynamic pro-gramming meets anytime optimisation. In Proceedings of the 23rd AAAI Con-ference on Artificial Intelligence (AAAI), pages 156–161, 2008.
[53] T. Rahwan and N. R. Jennings. An improved dynamic programming algorithm for coalition structure generation. In Proceedings of the 7th International Con-ference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1417–
1420, 2008.
[54] T. Rahwan, T. P. Michalak, E. Elkind, P. Faliszewski, J. Sroka, M. Wooldridge, and N. R. Jennings. Constrained coalition formation. InProceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI), 2011.
[55] T. Rahwan, T. P. Michalak, and N. R. Jennings. Minimum search to establish worst-case guarantees in coalition structure generation. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pages 338–343, 2011.
[56] T. Rahwan, T. P. Michalak, and N. R. Jennings. A hybrid algorithm for coalition structure generation. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI), pages 1443–1449, 2012.
[57] T. Rahwan, T. P. Michalak, N. R. Jennings, M. Wooldridge, and P. McBurney.
Coalition structure generation in multi-agent systems with positive and nega-tive externalities. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), 2009.
[58] T. Rahwan, S. D. Ramchurn, V. D. Dang, A. Giovannucci, and N. R. Jennings.
Anytime optimal coalition structure generation. InProceedings of the 22nd Con-ference on Artificial Intelligence (AAAI), pages 1184–1190, 2007.
[59] T. Rahwan, S. D. Ramchurn, N. R. Jennings, and A. Giovannucci. An any-time algorithm for optimal coalition structure generation. Journal of Artificial Intelligence Research (JAIR), 34:521–567, 2009.
[60] M. H. Rothkopf, A. Pekeˇc, and R. M. Harstad. Computationally manageable combinatorial auctions. Management Science, 44(8):1131–1147, 1998.
[61] T. Sandholm. An implementation of the contract net protocol based on marginal cost calculations. In Proceedings of the 11th National Conference on Artificial Intelligence (AAAI), pages 295–308, 1993.
[62] T. Sandholm. Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135(1-2):1–54, 2002.
[63] T. Sandholm, K. Larson, M. Andersson, O. Shehory, and F. Tohm´e. Coalition structure generation with worst case guarantees. Artificial Intelligence, 111(1-2):209–238, 1999.
[64] T. Sandholm and V. R. Lesser. Coalitions among computationally bounded agents. Artificial Intelligence, 94(1-2):99–137, 1997.
[65] L. S. Shapley and H. Scarf. On cores and indivisibility. Journal of Mathematical Economics, 1:23–28, 1974.
[66] L. S. Shapley and M. Shubik. Quasi-cores in a monetary economy with nonconvex preferences. Economitrica, 34:805–827, 1966.
[67] O. Shehory and S. Kraus. Methods for task allocation via agent coalition for-mation. Artificial Intelligence, 101(1-2):165–200, 1998.
[68] T. Shrot, Y. Aumann, and S. Kraus. On agent types in coalition formation problems. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 757–764, 2010.
[69] M. Tennenholtz. Some tractable combinatorial auctions. In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI), pages 98–103, 2000.
[70] S. Ueda, D. Fragiadakis, A. Iwasaki, P. Troyan, and M. Yokoo. Strategy-proof mechanisms for two-sided matching with minimum and maximum quotas. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1327–1328, 2012.
[71] S. Ueda, T. Hasegawa, N. Hashimoto, N. Ohta, A. Iwasaki, and M. Yokoo.
Handling negative value rules in mc-net-based coalition structure generation. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 795–804, 2012.
[72] S. Ueda, A. Iwasaki, M. Yokoo, M. C. Silaghi, K. Hirayama, and T. Mat-sui. Coalition structure generation based on distributed constraint optimization.
In Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI), pages 197–203, 2010.