Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Khai thác tính đối xứng đa diện trong lựa chọn xã hội
Tóm tắt
Một lượng lớn tài liệu trong lý thuyết lựa chọn xã hội đề cập đến việc định lượng xác suất của một số kết quả bầu cử nhất định. Một phương pháp để tính toán xác suất của một tình huống bỏ phiếu cụ thể dưới giả thuyết Văn hóa Vô tư Ẩn danh là thông qua việc đếm các điểm nguyên trong các đa diện. Ở đây, lý thuyết Ehrhart có thể hỗ trợ, nhưng không may rằng chiều cao và độ phức tạp của các đa diện liên quan tăng nhanh với số lượng ứng cử viên. Tuy nhiên, nếu chúng ta khai thác những tính đối xứng đa diện có sẵn, một số phép tính trở nên khả thi mà trước đây không thể thực hiện được. Chúng tôi chỉ ra điều này trong ba ví dụ nổi tiếng: nghịch lý Condorcet, hiệu quả Condorcet của phương pháp bỏ phiếu đa số và sự so sánh giữa bỏ phiếu đa số và trở lại bỏ phiếu đa số.
Từ khóa
#lý thuyết lựa chọn xã hội #xác suất bầu cử #giả thuyết Văn hóa Vô tư Ẩn danh #lý thuyết Ehrhart #nghịch lý Condorcet #hiệu quả Condorcet #bỏ phiếu đa số.Tài liệu tham khảo
Arrow KJ (1951) Social choice and individual values. Cowles Commission monograph no. 12. Wiley, New York
Barvinok A (1994) A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math Oper Res 19(4): 769–779
Barvinok A (2008) Integer points in polyhedra. Zurich lectures in advanced mathematics. European Mathematical Society (EMS), Zürich
Berg S, Bjurulf B (1983) A note on the paradox of voting: anonymous preference profiles and May’s formula. Public Choice 40: 307–316
Baldoni V, Berline N, De Loera JA, Köppe M, Vergne M (2010) Computation of the highest coefficients of weighted Ehrhart quasi-polynomials of rational polyhedra. Found. Comput. Math. Preprint at arxiv:1011.1602. http://arxiv.org/abs/1011.1602v1 (to appear)
Baldoni V, Berline N, De Loera JA, Köppe M, Vergne M (2011) How to integrate a polynomial over a simplex. Math Comput 80(273): 297–325
Beck M, Robins S (2007) Computing the continuous discretely: integer-point enumeration in polyhedra. Undergraduate texts in mathematics. Springer, New York
Büeler B, Enge A, Fukuda K (2000) Exact volume computation for polytopes: a practical study. Polytopes—combinatorics and computation (Oberwolfach, 1997), DMV Sem., vol. 29, Birkhäuser, Basel, pp. 131–154
De Loera JA, Dutra B, Köppe M, Moreinis S, Pinto G, Wu J (2011a) A user guide for latte integrale v1.5. http://www.math.ucdavis.edu/~latte/
De Loera JA, Dutra B, Köppe M, Moreinis S, Pinto G, Wu J (2011b) Software for exact integration of polynomials over polyhedra. Preprint at arxiv:1108.0117. http://arxiv.org/abs/1108.0117v2
Dyer ME, Frieze AM (1988) On the complexity of computing the volume of a polyhedron. Soc Ind Appl Math J Comput 17(5): 967–974
Ehrhart E (1967) Sur un problème de géométrie diophantienne linéaire. I. Polyèdres et réseaux. J Reine Angew Math 226: 1–29
Gawrilow E, Joswig M (2000) Polymake: a framework for analyzing convex polytopes. In: Kalai G, Ziegler GM (eds.) Polytopes—combinatorics and computation. Birkhäuser, pp. 43–74
Gehrlein WV (1982) Condorcet efficiency of constant scoring rules. Math Soc Sci 2(2): 123–130
Gehrlein WV (2001) Condorcet winners on four candidates with anonymous voters. Econ Lett 71: 335–340
Gehrlein WV (2002) Obtaining representations for probabilities of voting outcomes with effectively unlimited precision integer arithmetic. Soc Choice Welf 19(3): 503–512
Gehrlein WV, Fishburn PC (1976) The probability of the paradox of voting: a computable solution. J Econ Theory 13(1): 14–25
Gehrlein WV, Lepelley D (2011) Voting paradoxes and group coherence Studies in Choice and Welfare. The Condorcet efficiency of voting rules. Springer, Heidelberg
Huang HC, Vincent CH Chua (2000) Analytical representation of probabilities under the IAC condition. Soc Choice Welf 17(1): 143–155
Lepelley D, Louichi A, Smaoui H (2008) On Ehrhart polynomials and probability calculations in voting theory. Soc Choice Welf 30(3): 363–383
Rehn T, Schürmann A (2010) C++ tools for exploiting polyhedral symmetries. Mathematical Software ICMS 2010. Lecture Notes in computer science, vol. 6327. Springer, Berlin, pp. 295–298
Schechter M (1998) Integration over a polyhedron: an application of the Fourier-Motzkin elimination method. Am Math Mon 105(3): 246–251
Schreuders MB (2011) Plurality Voting vs. Plurality Runoff Voting: chances for different outcomes in large elections. Bachelor Thesis, TU Delft
Tabak F (2010) Counting lattice points in polyhedra using the Ehrhart theory, applied to voting theory. Bachelor Thesis, TU Delft
Taylor AD, Pacelli AM (2008) Mathematics and politics. Strategy, voting, power and proof, 2nd edn.. Springer, New York
Verdoolaege S, Bruynooghe M (2008) Algorithms for weighted counting over parametric polytopes, a survey and a practical comparison. Eighth ACES Symposium, Edegem
Wilson MC, Pritchard G (2007) Probability calculations under the IAChypothesis. Math Soc Sci 54(3): 244–256
barvinok by S. Verdoolaege, ver. 0.34 (2011), http://freshmeat.net/projects/barvinok
Convex by M. Franz, ver. 1.1.3 (2009), http://www.math.uwo.ca/~mfranz/convex/
LattE integrale by J.A. DeLoera, M. Köppe et al., ver. 1.5 (2011), http://www.math.ucdavis.edu/~latte/
Normaliz by W. Bruns, B. Ichim, and C. Söger, ver. 2.7 (2011), http://www.mathematik.uni-osnabrueck.de/normaliz/
SymPol by T. Rehn and A. Schürmann, ver. 0.1.4 (2011), http://www.geometrie.uni-rostock.de/software/