Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Về độ phức tạp tính toán của các trò chơi bỏ phiếu có trọng số
Tóm tắt
Các trò chơi liên minh cung cấp một công cụ hữu ích để mô hình hóa sự hợp tác trong các hệ thống đa tác nhân. Một lớp đặc biệt quan trọng của các trò chơi liên minh là các trò chơi bỏ phiếu có trọng số, trong đó mỗi người chơi có một trọng số (được hiểu một cách trực quan là tương ứng với đóng góp của họ), và một liên minh thành công nếu tổng trọng số của các thành viên của nó đạt hoặc vượt quá một ngưỡng nhất định. Một câu hỏi then chốt trong các trò chơi liên minh là tìm các liên minh và các kế hoạch phân chia lợi ích ổn định, nghĩa là không có nhóm người chơi nào có bất kỳ động lực hợp lý nào để rời bỏ. Trong bài báo này, chúng tôi nghiên cứu độ phức tạp tính toán của các câu hỏi liên quan đến sự ổn định trong các trò chơi bỏ phiếu có trọng số. Chúng tôi xem xét các vấn đề liên quan đến lõi, lõi tối thiểu và hạt nhân, phân biệt giữa những vấn đề có thể tính toán trong thời gian đa thức và những vấn đề là NP-khó hoặc coNP-khó, đồng thời cung cấp các thuật toán giả đa thức và xấp xỉ cho một số vấn đề tính toán khó.
Từ khóa
#trò chơi liên minh #trò chơi bỏ phiếu có trọng số #ổn định #độ phức tạp tính toán #lõi #hạt nhânTài liệu tham khảo
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Berlin (1999)
Banzhaf, J.F.: Weighted voting doesn’t work: a mathematical analysis. Rutgers Law Rev. 19, 317–343 (1965)
Bilbao, J., Fernández, J., López, J.: Complexity in cooperative game theory (manuscript)
Bilbao, J.M., Fernández, J.R., Jiminéz, N., López, J.J.: Voting power in the European union enlargement. Eur. J. Oper. Res. 143, 181–196 (2002)
Conitzer, V., Sandholm, T.: Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In: Proceedings of the Ninteenth National Conference on Artificial Intelligence (AAAI-2004), pp. 219–225, San Jose, CA (2004)
Conitzer, V., Sandholm, T.: Complexity of constructing solutions in the core based on synergies among coalitions. Artif. Intell. 170, 607–619 (2006)
Deng, X., Fang, Q., Sun, X.: Finding nucleolus of flow game. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 124–131. ACM, New York (2006)
Deng, X., Papadimitriou, C.H.: On the complexity of cooperative solution concepts. Math. Oper. Res. 19(2), 257–266 (1994)
Elkind, E., Chalkiadakis, G., Jennings, N.R.: Coalition structures in weighted voting games. In: Proc. 18th European Conference on Artificial Intelligence (ECAI’08) (2008)
Elkind, E., Goldberg, L.A., Goldberg, P.W., Wooldridge, M.: Computational complexity of weighted threshold games. In: Proc. 22nd Conference on Artificial Intelligence (AAAI’07) (2007)
Elkind, E., Goldberg, L.A., Goldberg, P.W., Wooldridge, M.: On the dimensionality of voting games. In: Proc. 23rd Conference on Artificial Intelligence (AAAI’08) (2008)
Elkind, E., Pasechnik, D.: Computing the nucleolus of weighted voting games. In: Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA’09) (2009)
Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1990)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, 2nd edn. Springer, Berlin (1993)
Ieong, S., Shoham, Y.: Marginal contribution nets: a compact representation scheme for coalitional games. In: Proceedings of the Sixth ACM Conference on Electronic Commerce (EC’05), Vancouver, Canada (2005)
Matsui, T., Matsui, Y.: A survey of algorithms for calculating power indices of weighted majority games. J. Oper. Res. Soc. Jpn 43(1), 71–86 (2000)
Matsui, Y., Matsui, T.: NP-completeness for calculating power indices of weighted majority games. Theor. Comp. Sci. 263(1–2), 305–310 (2001)
Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT, Cambridge (1994)
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)
Peleg, B.: On weights of constant-sum majority games. SIAM J. Appl. Math. 16, 527–532 (1968)
Prasad, K., Kelly, J.S.: NP-completeness of some problems concerning voting games. Int. J. Game Theory 19(1), 1–9 (1990)
Sandholm, T., Larson, K., Andersson, M., Shehory, O., Tohmé, F.: Coalition structure generation with worst case guarantees. Artif. Intell. 111(1–2), 209–238 (1999)
Schmeidler, D.: The nucleolus of a characteristic function game. SIAM J. Appl. Math. 17, 1163–1170 (1969)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, New York (2003)
Shehory, O., Kraus, S.: Coalition formation among autonomous agents: strategies and complexity. In: Castelfranchim, C., Müller, J.-P. (eds.) From Reaction to Cognition—Fifth European Workshop on Modelling Autonomous Agents in a Multi-Agent World, MAAMAW-93. LNAI, vol. 957, pp. 56–72. Springer, Berlin (1995)
Shehory, O., Kraus, S.: Task allocation via coalition formation among autonomous agents. In: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), pp. 655–661, Montréal, Québec, Canada (1995)
Shehory, O., Kraus, S.: Methods for task allocation via agent coalition formation. Artif. Intell. 101(1–2), 165–200 (1998)
Taylor, A., Zwicker, W.: Weighted voting, multicameral representation, and power. Games Econom. Behav. 5, 170–181 (1993)
Taylor, A.D., Zwicker, W.S.: Simple Games: Desirability Relations, Trading, Pseudoweightings. Princeton University Press, Princeton (1999)
Wolsey, L.A.: The nucleolus and kernel for simple games or special valid inequalities for 0 − 1 linear integer programs. Int. J. Game Theory 5(4), 227–238 (1976)