Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các Trò Chơi Che Phủ Dựa Trên LP Với Giá Thành Anarchy Thấp
Tóm tắt
Chúng tôi thiết kế một lớp trò chơi về đỉnh và tập hợp che phủ mới, nơi các ràng buộc giá thành anarchy phù hợp với các đảm bảo xấp xỉ hằng số tốt nhất đã biết cho các vấn đề tối ưu hóa tập trung cho chi phí tuyến tính và cũng như cho chi phí phụ chỉnh. Điều này trái ngược với tất cả các trò chơi che phủ trước đây đã được nghiên cứu, nơi giá thành anarchy tăng lên theo tỷ lệ với kích thước của trò chơi. Cả thiết kế trò chơi lẫn kết quả về giá thành anarchy đều dựa trên các thuộc tính cấu trúc của các phương pháp giải lập trình tuyến tính. Đối với chi phí tuyến tính, chúng tôi cũng thể hiện các động lực phản ứng tốt nhất đơn giản mà hội tụ về điểm cân bằng Nash trong thời gian tuyến tính.
Từ khóa
#trò chơi che phủ #giá thành anarchy #lập trình tuyến tính #cân bằng Nash #động lực phản ứng tốt nhấtTài liệu tham khảo
Anshelevich, E., Dasgupta, A., Tardos, É., Wexler, T.: Near-optimal network design with selfish agents. Theory Comput. 4(1), 77–109 (2008)
Balcan, M., Krehbiel, S., Piliouras, G., Shin, J.: Minimally invasive mechanism design: Distributed covering with carefully chosen advice. In: Proceedings of the IEEE 51st Annual Conference on Decision and Control (CDC), pp 2690–2695. IEEE (2012)
Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithm. 2(2), 198–203 (1981)
Baset, S., Schulzrinne, H.: An analysis of the skype peer-to-peer internet telephony protocol. In: Proceedings of the 25th IEEE International Conference on Computer Communications, pp 1–11 (2006)
Bhawalkar, K., Gairing, M., Roughgarden, T.: Weighted congestion games: Price of anarchy, universal worst-case examples, and tightness. In: European Symposium on Algorithms (ESA), pp 17–28. Springer (2010)
Buchbinder, N., Lewin-Eytan, L., Naor, J., Orda, A.: Non-cooperative cost sharing games via subsidies. Theory Comput. Syst. 47(1), 15–37 (2010)
Cardinal, J., Hoefer, M.: Selfish service installation in networks. In: Proceedings of the 2nd Workshop on Internet and Network Economics (WINE), pp 174–185. Springer (2006)
Cardinal, J., Hoefer, M.: Non-cooperative facility location and covering games. Theor. Comput. Sci. 411(16-18), 1855–1876 (2010)
Escoffier, B., Gourves, L., Monnot, J.: On the impact of local taxes in a set cover game. In: Structural Information and Communication Complexity (SIROCCO), vol. 6058, p 2. Springer, New York (2010)
Fleischer, L., Iwata, S.: A push-relabel framework for submodular function minimization and applications to parametric optimization. Discret. Appl. Math. 131(2), 311–322 (2003)
Hall, N., Hochbaum, D.: A fast approximation algorithm for the multicovering problem. Discret. Appl. Math. 15(1), 35–40 (1986)
Harks, T., Peis, B.: Resource buying games. In: European Symposium on Algorithms (ESA), pp 563–574 (2012)
Hoefer, M.: Competitive cost sharing with economies of scale. Algorithmica 60(4), 743–765 (2011)
Iwata, S., Nagano, K.: Submodular function minimization under covering constraints. In: Foundations of Computer Science (FOCS), pp 671–680. IEEE (2009)
Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2- ε. In: Computational Complexity, pp 379–386. IEEE (2003)
Koufogiannakis, C., Young, N.: Greedy Δ-approximation algorithm for covering with arbitrary constraints and submodular cost. In: Automata, Languages and Programming, pp 634–652. Springer (2009)
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Symposium on Theoretical Aspects of Computer Science (STACS), pp 404–413. Springer (1999)
Liang, J., Kumar, R., Ross, K.: The kazaa overlay: A measurement study. In: Proceedings of the 19th IEEE annual computer communications workshop, pp 2–9 (2004)
Lo, V., Zhou, D., Liu, Y., GauthierDickey, C., Li, J.: Scalable supernode selection in peer-to-peer overlay networks. In: Proceedings of the 2nd International Workshop on Hot Topics in Peer-to-Peer Systems, pp. 18–27. IEEE Computer Society,Washington (2005)
Rosenthal, R.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2(1), 65–67 (1973)
Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: ACM Symposium on Theory of Computing (STOC), pp 513–522. ACM (2009)
Roughgarden, T., Schoppmann, F.: Local smoothness and the price of anarchy in atomic splittable congestion games. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 255–267 (2011)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin Heidelberg (2003)