PCP 10 — Biến đổi Fourier, định lý Arrow và tính duy lý của sự độc tài

NQH | 29/07/2010 |

Trong bài này chúng ta giới thiệu biến đổi Fourier trên các nhóm Abel hữu hạn, giải tích Fourier của các hàm Bool, và giới thiệu lý thuyết bầu cử cùng với chứng minh định lý Arrow về tính duy lý của sự độc tài.

Như vậy chúng ta đã có chuyến “de-tour” sang các phép xây dựng đồ thị expanders, tính chất của chúng, và tích zig-zag. Đáng lẽ bài kế tiếp này tôi định viết về kết quả ${\mathsf{L = SL}}$ của Omer Reingold hồi 2005. Nhưng lại thôi vì thật ra nếu hiểu tích zig-zag rồi thì hiểu chứng minh của Reingold không khó khăn gì. Năm đó có chú Vladimir Trifonov rất ư là “xui”. Số là cả Trifonov và Reingold đều có kết quả rất tốt cho bài toán tìm sự liên thông trên đồ thị vô hướng (undirected st-connectivity). Dĩ nhiên ta có thể dùng BFS/DFS để giải bài này, nhưng tổng bộ nhớ cần thiết là ${O(n)}$ . Định lý Savich (1970) nói rằng có thể giải bài này dùng ${O(\log^2n)}$ -bộ nhớ. Mấy mươi năm sau đó thì có vài kết quả tốt dần lên, cho đến ${O(\log^{4/3}n)}$ của Armoni–Ta-Shma–Wigderson–Zhou năm 1997. Trifonov cải tiến đến ${O(\log n \log\log n)}$ , còn Reingold chứng minh được ${O(\log n)}$ luôn. Trifonov xui là vì nếu không có kết quả của Reingold thì kết quả của Trifonov thật sự là một phát triển rất mạnh (từ log xuống log-log). Kết quả là Reingold được giải bài báo hay nhất, còn Trifonov được giải bài báo sinh viên hay nhất cho STOC 2005.

Để chuẩn bị kiến thức nền cho mấy bài tới, chúng ta lại làm thêm một chuyến de-tour nữa, sang món giải tích Fourier của các hàm nhị phân. Để giải trí, ta chứng minh định lý Arrow về tính duy lý của sự độc tài bằng phân tích Fourier.

9. Biểu diễn nhóm và biến đổi Fourier

9.1. Các ký tự bất khả qui của nhóm Abel hữu hạn

Trong chuỗi bài về nhân ma trận đang viết dở, tôi đã tóm tắt lại một số kiến thức cơ bản về lý thuyết biểu diễn nhóm. Xem thêm bài này của HT THT. Ta sẽ thu thập lại vài kết quả cần thiết để dùng trong bài này và trong một bài tương lai khi ta phân tích cái expander của Margulis.

Các biểu diễn bất khả qui của một nhóm Abel bất kỳ đều là các biểu diễn với số chiều bằng một. Nếu nhóm có ${n}$ phần tử thì có ${n}$ ký tự trực giao. Nhóm tuần toàn là một nhóm Abel. Nhóm tuần hoàn ${\mathbb Z_n}$ có đúng ${n}$ ký tự (characters) ${\chi_a, a\in \mathbb Z_n}$ . Mỗi ký tự ${\chi_a}$ là một vector trong không gian vector phức ${\mathbb C^n}$ , định nghĩa là ${\chi_a(b) = \omega_n^{ab}}$ , trong đó ${\omega_n = e^{2\pi i/n}}$ . Các ký tự này là một hệ trực chuẩn theo tích Hermit này:

$\displaystyle \langle \chi_a, \chi_b \rangle = \frac{1}{n} \sum_{c \in \mathbb Z_n} \overline{\chi_a(c)}\chi_b(c) = \delta_{ab}.$

Định lý cơ bản của các nhóm Abel hữu hạn cho ta biết một nhóm Abel ${G}$ hữu hạn bất kỳ đều có thể viết dưới dạng tổng trực tiếp của các nhóm tuần hoàn: ${G \cong \mathbb Z_{m_1} \oplus \cdots \oplus \mathbb Z_{m_k}}$ . Các biểu diễn bất khả qui của nhóm ${G}$ là tăng sờ của các biểu diễn bất khả qui của các nhóm tuần hoàn ${\mathbb Z_{m_i}}$ . Các ký tự bất khả qui của nhóm ${G}$ là tích tăng sờ của các ký tự bất khả qui của các nhóm tuần hoàn ${\mathbb Z_{m_i}}$ . Với mỗi ${{\bf a} = (a_1, \cdots, a_k) \in Z_{m_1} \oplus \cdots \oplus \mathbb Z_{m_k}}$ , ta có một ký tự bất khả quy ${\chi_{\bf a}}$ của nhóm ${G}$ định nghĩa như sau: với một “tọa độ” ${{\bf b} = (b_1, \cdots, b_k) \in Z_{m_1} \oplus \cdots \oplus \mathbb Z_{m_k}}$ thì

$\displaystyle \chi_{\bf a}({\bf b}) = \prod_{i=1}^k \omega_{m_i}^{a_ib_i}= \omega_{m_1}^{a_1b_1}\cdots \omega_{m_k}^{a_kb_k}.$

Một trường hợp đặc biệt của nhóm Abel hữu hạn rất quan trọng trong chuỗi bài này và trong KHMT nói chung là ${G = \mathbb Z_2^n = \{0,1\}^n}$ . Có thể nghĩ về mỗi phần tử của ${G}$ như một đỉnh của khối ${n}$ -cube, hoặc là một phép gán sự thật (truth assignment) vào ${n}$ biến, hoặc là một tập con ${S \subseteq [n]}$ trong đó ${S}$ là tập các tọa độ bằng ${1}$ của phần tử. Ở đây, nhóm ${G}$ có ${N = 2^n}$ phần tử, và vì thế ${N}$ ký tự bất khả qui. Do ${\omega_2 = -1}$ , với mỗi cặp ${{\bf a, b} \in \mathbb Z_2^n}$ ta có ${\chi_{\bf a}({\bf b}) = (-1)^{{\bf a \cdot b}}}$ .

Thay vì dùng ${{\bf a, b}}$ để đánh chỉ số các ký tự và các tọa độ của chúng, ta có thể dùng các tập con ${A, B}$ của ${[n]}$ để đánh chỉ số, trong đó ${A = \{i \ | \ a_i=1\}}$ , và ${B = \{i \ | \ b_i = 1\}}$ . Theo cách này, bộ các ký tự có thể định nghĩa bằng ${\chi_{A}(B) = (-1)^{|A \cap B|}}$ . Còn nếu chúng ta dùng ${{\bf b} \in \mathbb Z_2^n}$ làm tọa độ thì ${\chi_A({\bf b}) = (-1)^{\sum_{i\in A}b_i}}$ . Bạn nên làm quen với việc chuyển qua lại giữa các tập con của ${[n]}$ và các vectors của ${\mathbb Z_2^n}$ .

Lý do chính chúng ta quan tâm đến các ký tự bất khả qui của nhóm ${\mathbb Z_2^n}$ là như sau. Trong phân tích độ khó xấp xỉ, chúng ta thường quan tâm đến các hàm Bool (hàm nhị phân) gồm ${n}$ biến nhị phân loại ${f: \{0,1\}^n \rightarrow \{0, 1\}}$ . Mỗi hàm loại này có thể xem là một vector trong không gian ${\{0,1\}^N}$ . Dĩ nhiên, chúng cũng là các vectors trong không gian ${\mathbb R^N}$ và ${\mathbb C^N}$ . Như đã nói ở trên, các ký tự bất khả qui là một cơ sở trực chuẩn của không gian ${\mathbb C^N}$ . Vì thế, một hàm nhị phân ${n}$ biến bất kỳ, nếu viết thành một vector trong không gian ${\mathbb C^N}$ , đều là tổ hợp tuyến tính của các ký tự bất khả qui.

Thay vì làm việc trên không gian vector ${\mathbb C^N}$ , chúng ta cũng có thể làm việc trên không gian (tuyến tính) của hàm số ${f: \{0,1\}^n \rightarrow \mathbb C}$ . Chúng tương đương với nhau. Hàm ${f: \{0,1\}^n \rightarrow \mathbb C}$ bất kỳ đều có thể biểu diễn dưới dạng

$\displaystyle f({\bf y}) = \sum_{S \subseteq [n]} \hat f_S \chi_S({\bf y}) = \sum_{S\subseteq [n]} \hat f_S (-1)^{\sum_{i\in S}y_i}.$

Để cái đám ${y_i}$ trên số mũ thì hơi khó chịu. Chúng ta đổi biến. Đặt ${x_i = (-1)^{y_i}}$ . Nghĩa là nếu ${y_i = 0}$ (FALSE) thì ${x_i = 1}$ , còn ${y_i = 1}$ (TRUE) thì ${x_i = -1}$ . Thì mọi hàm ${f: \{-1, 1\}^n \rightarrow \mathbb C}$ đều có thể viết dưới dạng

$\displaystyle f({\bf x}) = \sum_{S\subseteq [n]} f_S \chi_S({\bf x}),$

trong đó (lạm dụng ký hiệu một chút) ${\chi_S: \{-1,1\}^n \rightarrow \{-1,1\}}$ là một hàm đơn thức

$\displaystyle \chi_S({\bf x}) = \chi_S(x_1,\cdots,x_n) = \prod_{i\in S} x_i.$

Đám ${\chi_S}$ bây giờ gọi là hệ cơ sở đơn thức (monomial basis) của các hàm ${f: \{-1,1\}^n \rightarrow \mathbb C}$ . Nhớ rằng cái hệ cơ sở đơn thức này là một hệ cơ sở trực chuẩn của không gian các hàm ${f: \{-1,1\}^n \rightarrow \mathbb C}$ . Trong đó, “tích vô hướng” của hai hàm ${f, g}$ bất kỳ được định nghĩa là

$\displaystyle \langle f, g \rangle = \frac{1}{2^n} \sum_{{\bf x} \in \{-1,1\}^n} f({\bf x}) \overline{g({\bf x})} = \mathop{\textnormal{E}}_{\bf x}[f({\bf x})\overline{g({\bf x})}],$

trong đó trị kỳ vọng ở vế phải tính trên phân bố đều của các vectors ${{\bf x} \in \{-1,1\}^n}$ . Chúng ta sẽ thấy rằng hiểu tích vô hướng của hai hàm như trị kỳ vọng của tích rất hữu dụng về sau.

9.2. Biến đổi Fourier

Ý tưởng chính của biến đổi Fourier rời rạc chỉ là một phát biểu cơ bản của đại số tuyến tính: các vector trong một không gian vector đều là tổ hợp tuyến tính của một hệ cơ sở của không gian đó. (Xem thêm bài của Terry Tao giới thiệu về biến đổi Fourier. Một chương của quyển sách mới của bác Văn với Terry cũng giới thiệu cách dùng giải tích điều hòa — harmonic analysis — trong toán tổ hợp cộng tính — additive combinatorics.)

Trong ngữ cảnh của chúng ta, mỗi hàm ${f: \{-1,1\}^n \rightarrow \mathbb R}$ đều là tổ hợp tuyến tính của các hàm đơn thức:

$\displaystyle f({\bf x}) = \sum_{S\subseteq [n]} \hat f_S \chi_S({\bf x}),$

Tổ hợp này là duy nhất. Các hệ số ${\hat f_S = \langle f, \chi_S \rangle}$ gọi là các hệ số Fourier của ${f}$ . Chúng là các số thực vì ${f}$ và ${\chi_S}$ là các vectors thực. Từ giờ trở đi chúng ta có thể làm việc luôn trên không gian ${\mathbb R^N}$ thay vì ${\mathbb C^N}$ và không cần cái liên hợp (conjugate) khi tính tích vô hướng của hai vectors nữa. Hệ cơ sở đơn thức ${\chi_S}$ cũng được gọi là hệ cơ sở Fourier.

Hai đẳng thức cơ bản nhất của biến đổi Fourier là

đẳng thức Plancherel
$\displaystyle \mathop{\textnormal{E}}_{\bf x}[f({\bf x})g({\bf x})] = \langle f, g \rangle = \sum_{S\subseteq [n]} \hat f_S \hat g_S = N \langle \hat f, \hat g \rangle$
và trường hợp đặc biệt là đẳng thức Paserval
$\displaystyle \mathop{\textnormal{E}}_{\bf x}[f^2({\bf x})] = \langle f, f \rangle = \sum_{S\subseteq [n]} \hat f^2_S.$

Bài tập. chứng minh hai đẳng thức trên từ định nghĩa và tính trực chuẩn của các ${\chi_S}$ .

10. Luật bầu cử và biến đổi Fourier cho các hàm nhị phân

Trong trường hợp hàm nhị phân ${f: \{-1,1\}^n \rightarrow \{-1,1\}}$ thì ${f^2({\bf x}) = 1}$ với mọi ${\bf x}$ , vì thế đẳng thức Parseval cho

$\displaystyle \sum_{S\subseteq [n]} \hat f^2_S = \mathop{\textnormal{E}}_{\bf x}[f^2({\bf x})] = 1.$

Có thể nghĩ về một hàm nhị phân như một “luật” bầu cử. Có ${n}$ phiếu bầu ${x_i}$ cho hai ứng cử viên ${1}$ và ${-1}$ . Hàm ${f}$ trả về người thắng cử. Sau đây là một số hàm (luật) bầu cử hay thấy trên thực tế:

${\text{Maj}_n}$ là hàm bầu đa số, chỉ định nghĩa với ${n}$ lẻ, trả về ${1}$ nếu đa số các “phiếu” là ${1}$ và ngược lại.
${\text{Dict}_i}$ là hàm độc tài (dictator) thứ ${i}$ , trả về phiếu bầu của ${x_i}$ , nghĩa là ${\text{Dict}_i({\bf x}) = x_i}$ .
${\text{Const}_1}$ và ${\text{Const}_{-1}}$ là các hàm hằng số (hay hàm “đảng cử, dân bầu”), luôn trả về giá trị đảng cử ${1}$ hoặc ${-1}$ .

Ta cũng có thể định nghĩa một số hàm khác như hàm chẵn lẻ, hàm “electoral college” (như trong luật bầu cử của Mỹ), vân vân. Xem bài này của Ryan O’Donnell để thêm một số ví dụ.

Với một luật bầu cử nhất định, chúng ta muốn biết nhiều thuộc tính của nó.

Nó có thiên vị không? Thiên vị ở đây được hiểu như sau, nếu ta lấy một bộ ${n}$ phiếu bầu ngẫu nhiên thì xác suất mà kết quả là ${1}$ hoặc ${-1}$ khác nhau cỡ nào. Một luật bầu là “công bằng” nếu hai xác suất này bằng nhau. Do đó, ta định nghĩa sự thiên vị của hàm ${f}$ bằng
$\displaystyle \mathop{\textnormal{Prob}}_{\bf x}[f({\bf x})=1] - \mathop{\textnormal{Prob}}_{\bf x}[f({\bf x})=-1] = \mathop{\textnormal{E}}_{\bf x}[f({\bf x})].$

Đến đây thì ta thấy phân tích Fourier có lợi thế nào. Do hàm ${\chi_{\emptyset} = 1}$ , độ thiên vị của ${f}$ là
$\displaystyle \mathop{\textnormal{E}}_{\bf x}[f({\bf x})] = \mathop{\textnormal{E}}_{\bf x}[f({\bf x})\chi_{\emptyset}({\bf x})] = \hat f_\emptyset.$

Độ thiên vị của ${f}$ chính là hệ số Fourier thứ nhất! Dễ thấy rằng các hàm đảng cử/dân bầu có thiên vị là ${\pm 1}$ . Các hàm độc tài và hàm đa số có độ thiên vị bằng ${0}$ .
Ảnh hưởng của một phiếu nào đó ra sao? Nếu Tám Tàng đổi phiếu từ ${-1}$ sang ${1}$ thì kết quả bị đổi thế nào? Với bộ phiếu ${{\bf x}}$ , gọi ${{\bf x}^{\oplus i}}$ là bộ phiếu mà ta đổi phiếu ${x_i}$ lại. Thì tầm ảnh hưởng của phiếu thứ ${i}$ trên kết quả được định nghĩa là
$\displaystyle \text{Inf}_i(f) := \mathop{\textnormal{Prob}}_{\bf x}[f({\bf x}) \neq f({\bf x}^{\oplus i})].$

Trong lý thuyết chọn lựa xã hội (social choice theory) thì tầm ảnh hưởng này còn được gọi là Banzhaf power index hoặc Banzhaf-Penrose index. Chỉ số này đã được dùng trong một vài phiên tòa về bầu cử. Các hệ số Fourier lại giúp ta:
$\displaystyle \text{Inf}_i(f) = \sum_{i \in S} \hat f^2_S.$

(bài tập!)

Dễ thấy rằng tầm ảnh hưởng của các hàm đảng cử là ${0}$ , tầm ảnh hưởng của hàm độc tài là ${0}$ cho tất cả trừ anh độc tài có ảnh hưởng bằng ${1}$ . Tầm ảnh hưởng của hàm đa số thì mất công hơn một chút. Dùng xấp xỉ Stirling ta tính được nó bằng khoảng ${\sqrt{\frac{2}{\pi n}}}$ .
Ảnh hưởng của nhiễu ra sao? Khi ghi lại cả triệu phiếu bầu thì xác suất mà một phiếu bị ghi sai không bỏ qua được. Gọi xác suất này là ${\epsilon}$ chẳng hạn. Giả sử ta lấy một bộ phiếu bầu ${\bf x}$ hoàn toàn ngẫu nhiên. Gọi ${\bf y}$ là bộ phiếu đạt được bằng cách lật mỗi phiếu ${x_i}$ với xác suất ${\epsilon}$ . Dễ thấy, với mọi ${i}$ ,
$\displaystyle \mathop{\textnormal{E}}[x_iy_i] = 1-2\epsilon.$

Do đó cặp ${(\bf x, y)}$ được gọi là ${(1-2\epsilon)}$ -correlated. Độ ổn định nhiễu của ${f}$ tại ${(1-2\epsilon)}$ được định nghĩa là
$\displaystyle \text{Stab}_{1-2\epsilon}(f) = \mathop{\textnormal{E}}_{\stackrel{{\bf x, y}}{(1-2\epsilon)-\text{cor}}} [f({\bf x})f({\bf y})] = \mathop{\textnormal{Prob}}_{\bf x}[f({\bf x}) = f({\bf y})] - \mathop{\textnormal{Prob}}_{\bf x}[f({\bf x}) \neq f({\bf y})].$

Ngược lại:
$\displaystyle \mathop{\textnormal{Prob}}_{\bf x}[f({\bf x}) = f({\bf y})] = \frac 1 2 + \frac 1 2 \text{Stab}_{1-2\epsilon}(f).$

Ta cũng tính được độ ổn định nhiễu dùng các hệ số Fourier:
$\displaystyle \text{Stab}_{1-2\epsilon}(f) = \sum_{S\subseteq [n]} (1-2\epsilon)^{|S|} \hat f_S^2.$

(bài tập!)

Độ ổn định nhiễu của các hàm đảng cử là ${1}$ , của hàm độc tài thứ ${i}$ là ${1-2\epsilon}$ . Độ ổn định nhiễu của hàm đa số là thú vị nhất. Có thể chứng minh được điều sau đây:
$\displaystyle \lim_{n \rightarrow \infty} \text{Stab}_{1-2\epsilon}(\text{Maj}_n) = 1 - \frac 2 \pi \arccos(1-2\epsilon).$

Nếu ta dùng xấp xỉ ${\arccos(1-2\epsilon) \approx 2\sqrt{\epsilon}}$ (khá tốt khi ${\epsilon}$ nhỏ) thì ta thấy rằng cái nhiễu ${\epsilon}$ dẫn đến xác suất khoảng ${\frac{2}{\pi} \sqrt{\epsilon}}$ là kết quả bầu cử bị thay đổi.

11. Định lý Arrow và tính duy lý của sự độc tài

Marquis de Condorcet là một triết gia, nhà toán học, và nhà khoa học chính trị người Pháp sống ở thế kỷ 18. Năm 1785, ông viết bài “Essay on the Application of Analysis to the Probability of Majority Decisions” có ảnh hưởng sâu rộng đến lý thuyết chọn lựa xã hội, kinh tế học, và hiện nay đến các thuật toán xếp hạng quảng cáo của các công ty như Google, Yahoo, Microsoft. Condorcet là một trong những người đầu tiên mang (tính chặt chẽ của) toán học vào nghiên cứu khoa học xã hội. Ông tham gia cách mạng Pháp, viết vài quyển sách bất hủ ủng hộ cho tinh thần Khai Sáng. Ông bị bắt giam gần một năm, và mất trong tù. Nhiều khả năng là do tự uống thuốc độc.

Ông khám phá ra “nghịch lý Condorcet”. Đại để cái nghịch lý này như sau. Giả sử nhà nước cần đầu tư vào ngành đóng tàu (ĐT), cầu đường (CĐ), hoặc giáo dục (GD). Nhà nước làm trưng cầu dân ý. Mỗi người cho biết xếp hạng của riêng mình về tầm quan trọng của ba thứ này. Ví dụ, anh Tám Tàng bảo tôi nghĩ GD trước, rồi đến CĐ, rồi đến ĐT. Anh Bảy Xị cho một thứ tự khác, vân vân. Thì có khả năng là đa số mọi người xếp GD trên CĐ, đa số xếp CĐ trên ĐT, và đa số xếp ĐT trên GD. Đó là tính phi lý của chọn lựa xã hội. Khi biết cái nghịch lý Condorcet rồi, chúng ta đọc các thống kê xã hội cẩn thận hơn. Obama với McCain cãi nhau, đều lôi thống kê ra. Một ông bảo phải đầu tư cái này do đa số dân chúng ủng hộ cái này hơn cái kia, McCain bảo cái kia hơn cái nọ. Chúng ta nên nghĩ ngay đến khả năng vô lý của chọn lựa xã hội. Có khả năng cả Obama lẫn McCain đều đúng, nhưng đều vô lý.

Đến năm 1950, Kenneth Arrow (giải Nobel kinh tế 1972) viết một bài báo rất nổi tiếng về các luật bầu cử, trong đó ông chứng minh định lý Arrow nói rằng hàm độc tài là luật bầu cử duy nhất có tính “duy lý” tuyệt đối. Chúng ta sẽ chứng minh định lý Arrow bằng giải tích Fourier.

Để đơn giản (nhưng không mất tính tổng quát) ta giả sử xã hội có 3 đề mục A, B, C cần xếp hạng bằng bầu cử (GD-CĐ-ĐT, hoặc Obama-McCain-Nader, hoặc cơm-sữa-bia). Người thứ ${i}$ bầu 3 phiếu: phiếu ${x_i}$ chọn A hơn B ( ${x_i = 1}$ ) hoặc B hơn A ( ${x_i=-1}$ ), ${y_i}$ chọn giữa B và C, và ${z_i}$ chọn giữa C và A. Nếu anh nào xếp hạng vòng tròn (A hơn B, B hơn C, và C hơn A) thì anh ấy bị chập, không cho bầu. Do đó chúng ta giả sử là ba phiếu bầu ${x_i, y_i, z_i}$ của người thứ ${i}$ mang tính duy lý. Nói cách khác, bộ ba ${(x_i, y_i, z_i)}$ là duy lý nếu và chỉ nếu chúng không cùng bằng ${1}$ hoặc ${-1}$ .

Như vậy, nếu có ${n}$ người thì ta có ba vectors ${{\bf x, y, z} \in \{-1,1\}^n}$ . Từ ba vectors này, “luật” bầu cử sẽ phải tính xem xã hội xếp hạng A, B, C như thế nào, nghĩa là xã hội thích cái nào hơn giữa A và B, giữa B và C, và giữa C và A. Luật bầu cử sẽ phải thỏa mãn một số tiên đề nhất định:

Tính nhất trí (còn gọi là hiệu suất Pareto): nếu mỗi người đều thích A hơn B thì xã hội cũng phải chọn A hơn B.
Không độc tài: xếp hạng của xã hội không thể luôn giống hệt như xếp hạng của một anh Bảy Xị nào đó.
Sự độc lập của các chọn lựa không liên quan (independence of irrelevant alternatives — IIA): việc xã hội xếp hạng A hơn B hay B hơn A thì độc lập với thứ hạng của anh C trong các chọn lựa cá nhân.
Tính duy lý: xã hội không thể xếp hạng quẩn quanh theo vòng tròn (A hơn B, B hơn C, và C hơn A).

Arrow chứng minh rằng không có hàm nào thỏa cả bốn điều kiện trên, cho dù các cá nhân đều duy lý. (Bài báo của Arrow khá là dài dòng văn tự. Với mỗi giả thuyết, tiên đề, ông lại đá sang triết lý và vài kết quả trước đó.) Định lý của Arrow thật sự là một định lý mang tính tổ hợp, và có các chứng minh tổ hợp ngắn gọn cho nó.

Chúng ta sẽ chứng minh định lý Arrow bằng phân tích Fourier. Chứng minh này là phát kiến tuyệt vời của Gil Kalai.

Từ giả thiết IIA, ta kết luận rằng chọn lựa xã hội có thể đúc kết bằng ba hàm số ${f({\bf x}): \{-1,1\}^n \rightarrow \{-1,1\}}$ , ${g({\bf y})}$ , và ${h({\bf z})}$ . Hàm ${f}$ cho ta biết xã hội thích A hơn hay B hơn, ${g}$ xếp hạng B và C, và ${h}$ xếp hạng C và A.

Từ tính nhất trí và tính duy lý, ta sẽ chứng minh rằng ${f=g=h}$ . Tính duy lý nói rằng không thể tồn tại các vectors ${{\bf x, y, z}}$ , mỗi bộ ${(x_i,y_i,z_i)}$ đều duy lý, mà lại cho ra kết quả phi lý ${f({\bf x}) = g({\bf y}) = h({\bf z})}$ . Xét bộ ba ${{\bf x}, {\bf y = -x}}$ , và ${{\bf z} = (f({\bf x}), \cdots, f({\bf x})}$ . Do tính nhất trí ta có ${h({\bf z}) = f({\bf x})}$ . Như vậy ${g({\bf y})}$ phải khác với ${f({\bf x})}$ . Nghĩa là ${g(-{\bf x}) = -f({\bf x})}$ với mọi ${{\bf x}}$ . Tương tự ta có ${g(-{\bf x}) = -h({\bf x})}$ với mọi ${{\bf x}}$ . Do đó ${f=h}$ . Tương tự ta có ${f=g=h}$ .

Bây giờ giả sử tồn tại hàm ${f}$ sao cho, với bất kỳ bộ ba duy lý ${({\bf x, y, z})}$ nào, cái chọn lựa xã hội ${(f({\bf x}), f({\bf y}), f({\bf z}))}$ cũng duy lý. Ta sẽ chứng minh rằng ${f}$ phải là hàm độc tài. Với mỗi cá nhân ${i}$ , chọn bộ ba ${(x_i,y_i,z_i)}$ ngẫu nhiên từ một trong 6 bộ ba duy lý ${(1,1,-1)}$ , ${(1,-1,1)}$ , ${(1,-1,-1)}$ , ${(-1,1,1)}$ , ${(-1,-1,1)}$ , và ${(-1,1,-1)}$ . Ta sẽ có một bộ ba vectors ${({\bf x, y, z})}$ duy lý. Xác suất mà ${(f({\bf x}), f({\bf y}), f({\bf z}))}$ là duy lý phải bằng ${1}$ , nếu luật bầu cử ${f}$ là duy lý trong mọi trường hợp.

Định nghĩa hàm ${\textnormal{NAE}(a,b,c): \{-1,1\}^3 \rightarrow \{0,1\}}$ như sau. (NAE là “not all equal”.) ${\textnormal{NAE}(a,b,c) = 0}$ nếu và chỉ nếu ${a=b=c}$ . Khai triển Fourier của hàm này là

$\displaystyle \textnormal{NAE}(a,b,c) = \frac 3 4 - \frac 1 4 ab-\frac 1 4 bc-\frac 1 4 ca.$

Như vậy, xác suất mà ${(f({\bf x}), f({\bf y}), f({\bf z}))}$ là duy lý sẽ bằng

$\displaystyle \mathop{\textnormal{E}}_{{\bf x,y,z}}[\text{NAE}(f({\bf x}), f({\bf y}), f({\bf z})] = \frac 3 4 - \frac 1 4 \text{E}[f({\bf x})f({\bf y})] - \frac 1 4 \text{E}[f({\bf y})f({\bf z})] - \frac 1 4 \text{E}[f({\bf z})f({\bf x})].$

Do ${{\bf x, y, z}}$ có vai trò như nhau, ta kết luận

$\displaystyle \mathop{\textnormal{E}}_{{\bf x,y,z}}[\text{NAE}(f({\bf x}), f({\bf y}), f({\bf z})] = \frac 3 4 - \frac 3 4 \text{E}[f({\bf x})f({\bf y})].$

Nhớ rằng trị kỳ vọng được tính từ cách lấy các bộ ba duy lý ${{\bf x, y, z}}$ như mô tả ở trên. Từ đó dễ thấy rằng ${{\bf x,y}}$ là một cặp ${(-1/3)}$ -correlated. Do đó

$\displaystyle \text{E}[f({\bf x})f({\bf y})] = \text{Stab}_{-1/3}(f) = \sum_{S\subseteq [n]} (-1/3)^{|S|} \hat f_S^2.$

Để cho gọn, ta định nghĩa ${W_k(f) = \sum_{|S|=k|}\hat f^2_S}$ . Nhớ rằng ${\sum_S \hat f_S^2 = 1}$ , do đó ${\sum_k W_k(f)=1}$ . Do đó, xác suất mà ${(f({\bf x}), f({\bf y}), f({\bf z}))}$ là duy lý bằng

$\displaystyle \frac 3 4 - \frac 3 4 \sum_{k=0}^n (-1/3)^k W_k(f) = \frac 3 4 - \frac 3 4 W_0(f) + \frac{1}{4}W_1(f) - \frac{1}{12} W_2(f) + \frac{1}{36} W_3(f) \cdots$

Xác suất này chỉ có thể bằng ${1}$ nếu ${W_1(f)=1}$ và ${W_k(f)=0}$ với mọi ${k\neq 1}$ . Nhưng ${W_1(f)=1}$ nếu và chỉ nếu ${f = \text{Dict}_i}$ hoặc ${f = -\text{Dict}_i}$ với ${i}$ nào đó. Nhưng ${f}$ phải thỏa tính nhất trí, do đó ${f = \text{Dict}_i}$ . Và đó là tính duy lý của sự độc tài.

Chứng minh định lý Arrow bằng phương pháp này không chỉ để cho vui. Chứng minh cũ của Arrow không cho chúng ta biết xác suất sự phí lý của chọn lựa xã hội là bao nhiêu. Phân tích Fourier cho chúng ta biết, nếu ta dùng hàm đa số, khi ${n}$ tiến đến vô cùng thì xác suất có chọn lựa xã hội duy lý là

$\displaystyle \frac 3 4 - \frac 3 4\left(1-\frac 2 \pi \arccos(-1/3)\right) \approx .912.$

Con số ${.912}$ này gọi là số Guilbaud. Chúng ta không những biết nghịch lý Condorcet có thể xảy ra mà còn biết cả xác suất của nó. Còn nhiều điều hay ho nữa từ chứng minh này, nhưng để dịp khác. Bài tới ta bàn về cái PCP của Hastad.

Chủ đề : KHMT và Kinh Tế, Lý thuyết tính toán, Thuật Toán, Xác suất & thống kê and tagged Biến đổi Fourier, Biểu diễn nhóm, Lý thuyết bầu cử, PCP, xác suất, Định lý Arrow. Bookmark the permalink. Trackbacks are closed, but you can post a comment.

13 Comments

Nkd

Posted 29/07/2010 at 10:18 am | Permalink

Cái bài này của bác nghe tên đã thấy hấp dẫn rồi đấy. Bỏ qua những phần toán Furier với Abel này nọ mà tôi chưa có thời gian nghiền ngẫm, tôi nghĩ rằng cả 4 cái tiên đề ấy có thể hoàn toàn không cần thiết để xây dựng các thể chế bầu cử cũng như nhà nước.

Như bác giáo sư vật lý nào đó từng nói:”chân lý khoa học độc lập khách quan với khả năng nhận thức của quần chúng”. Ý kiến của đám đông chả có ý nghĩa quái gì,ngay cả trong các vấn đề về KHXH, Việc bầu cử ai làm lãnh đạo hoàn toàn có thể dựa trên nguyên tắc phi dân chủ, nghĩa là bằng những phương pháp đo năng lực một cách thuần túy máy móc, dựa trên một số tiêu chí chẳng hạn như Phát triển bền vững của quốc gia.

Quan trọng là ở chỗ giảm tầm quan trọng của chiếc ghế quyền lực thôi. Hiện nay công chúng đều chấp nhận các chức vụ kiểu như bộ trưởng, thậm chí ở 1 số nước tổng thống là to nhất thì cả chức thủ tướng, không được bổ nhiệm bằng cách bỏ phiếu dân chủ, thì họ cũng có thể chấp nhận chức vụ tổng thống thông qua đề cử bằng máy đo hoặc hàm đo năng lực

Người ta cứ đòi bầu cử tổng thống chẳng qua là do cái ghế tổng thống hiện nay còn quá to. Nếu giảm tầm quan trọng của chiếc ghế đó, biến nó thành 1 công việc ít reputation thì quần chúng sẽ chấp nhận thôi.

Cải tổ hình thái nhà nước cũng là một đề tài hấp dẫn mà tôi quan tâm. Cũng có một số ý tưởng, nhưng chưa tiện trình bày ở đây.

Reply
Ngô Quang Hưng

Posted 29/07/2010 at 5:40 pm | Permalink

Nkd :

Việc bầu cử ai làm lãnh đạo hoàn toàn có thể dựa trên nguyên tắc phi dân chủ, nghĩa là bằng những phương pháp đo năng lực một cách thuần túy máy móc, dựa trên một số tiêu chí chẳng hạn như Phát triển bền vững của quốc gia.

Ừ, xong rồi mình … bầu để xếp hạng các tiêu chí xem tiêu chí nào là quan trọng nhất

Reply
Nkd

Posted 29/07/2010 at 6:47 pm | Permalink

À, là tôi lấy ví dụ thế. Chứ còn tiêu chí như thế nào mà chẳng có ủy ban chuyên môn soạn thảo và xét duyệt, chẳng như như cái HDI, hay cái Happiness Index.

Reply
uyen

Posted 02/08/2010 at 4:53 am | Permalink

Tiến tới sản xuất ra máy làm bộ trưởng luôn, khi mà không nghe lời ra rút pin ra

Reply
ntzung

Posted 23/08/2010 at 3:17 am | Permalink

Bài viết của Hưng rất hay. Ai còn dám bảo toán là vô dụng

Đảng cứ/dân bầu là thuật ngữ tự nghĩ ra hay có từ trước thế ?

chế độ của ta được tự do phát biểu, có điều không đảm bảo tự do sau khi phát biểu thôi

Reply
Ngô Quang Hưng

Posted 23/08/2010 at 3:55 am | Permalink

Chào bác Dũng,

Toán (kể cả loại trừu tượng) chắc chắn là không vô dụng, tôi sẽ có bài tặng anh Trung Hà sớm

“Đảng cử dân bầu” là tự nghĩ ra bác ạ, bọn Mỹ/Israel chắc không có cụm từ tương đương, nó chị gọi là “hàm hằng số” nghe chán chết.

Hê hê, cái câu “chế độ của ta được tự do phát biểu, có điều không đảm bảo tự do sau khi phát biểu thô” là do bác tự nghĩ ra hay có từ trước ạ?

Reply
Khoa

Posted 23/08/2010 at 11:28 pm | Permalink

Bài viết của anh Hưng rất thú vị, ngồi nhai cũng mất thời gian phết . Lỡ nhai xong thì phải comment:

1. Khi bàn về xác xuất của tính duy lý, anh đã giả định nhiều thứ: (a) 6 bộ 3 duy lý có xác suất như nhau và (b) hàm lựa chọn là hàm đa số. Thậm chí chỉ cần nếu (a) không đúng thì cũng không suy ra được (x,y) $\alpha$ -correlated và phương pháp chứng minh trên cũng không sử dụng được.

Trong khi đó định lý Arrow tổng quát và powerful hơn thế nhiều. Ví dụ: có rất nhiều nơi sử dụng phương pháp assign điểm cho mỗi thứ hạng và cộng điểm từ tất cả các votes. Định lý Arrow vẫn đúng nhưng assumptions ở trên thì không.

2. Anh Hưng có biết tại phép biển đổi trên lại gọi là Fourier? Em chỉ mới thấy phương pháp trên chỉ là sử dụng một tập orthonormal basis functions nhất định chứ chưa thấy linh hồn của Fourier Transform đâu cả . Tính chất Plancherel và Parseval chỉ follow định nghĩa của orthonormal basis.

3. Giả sử có một cơ chế lựa chọn 2 giai đoạn như sau:
(a) Chọn một ‘đại ca’ bằng phương pháp loại trừ irrelevant option, option được voted ít nhất, qua từng vòng một
(b) Sau đó social ranking sẽ là ranking của vị đại ca này (nếu cần phải ranking)

Cơ chế này không compatible với các nguyên tắc của Arrow nhưng vẫn có cùng một mục đích. Nhưng cơ chế này có fair không?

Reply
- Ngô Quang Hưng
  
  Posted 24/08/2010 at 4:04 am | Permalink
  
  Hello Khoa,
  
  1. Điểm mấu chốt của phương pháp xác suất: nếu xác suất khác 0 thì tồn tại một cách bầu phi lý. (Ta chọn 6 bộ duy lý xác suất kiểu gì cũng được hết, vì nếu xác suất bầu phi lý khác 0 thì tồn tại một cách bầu có density dương và đó là cách bầu duy lý.) Định lý Arrow chỉ nói là tồn tại một cách bầu phi lý thôi.
  
  Còn (b), tôi đâu có giả sử hàm lựa chọn là đa số đâu nhỉ? Nếu giả sử là hàm đa số rồi sao lại chứng minh nó là hàm độc tài? Có lẽ Khoa “miss” điểm mấu chốt của ppsx nên lấn cấn ở chỗ này.
  
  2. Biến đổi Fourier (rời rạc hay liên tục) cũng chỉ là viết một hàm thành tổ hợp tuyến tính của các hàm cơ sở thôi. Dĩ nhiên đoạn này người ta lạm dụng tên gọi một chút.
  
  3. “Fair” hay không về mặt xã hội thì phải … bầu (trưng cầu dân ý), và ta có một vòng lặp vô tận
  
  Reply
  - Khoa
    
    Posted 24/08/2010 at 7:48 am | Permalink
    
    1. Em correct lại statement của mình: phương pháp tính xác suất kiểu trên chỉ sử dụng được khi (a) các ứng viên có equal chance. Nếu không sẽ không có triển khai $\displaystyle \text{E}[f({\bf x})f({\bf y})] = \text{Stab}_{-1/3}(f) = \sum_{S\subseteq [n]} (-1/3)^{|S|} \hat f_S^2$ .
    
    Còn (b) là nói đến con số .912 chứ không liên quan gì đến phương pháp chứng minh. Sorry hơi nhập nhằng.
    
    Btw, định lý Arrow nói rằng không tồn tại cách bầu duy lý chứ đâu phải là tồn tại cách bầu phi lý.
    
    2. Hiện tại chưa định nghĩa khi nào một biến đổi trên một không gian bất kỳ được gọi là biến đổi Fourier. Nhưng Fourier transform truyền thống có vài characteristic properties làm cho lý thuyết này được sử dụng rộng rãi:
    * Duality giữa 1 hàm và Fourier transform của hàm đó
    * [Lý thuyết xấp xỉ] Fourier coefficients của các hàm tuần hoàn tiến về 0 với tốc độ exponential
    * Tính chất convolution
    
    Nếu chỉ đưa về một hệ cơ sở thì hình như người ta đã có tên gọi: orthonormal basis decomposition hoặc phương pháp Gram-Schmidt. Nếu lạm dụng tên thì có thể sẽ dễ confuse những người học sau này. Đây chỉ là personal opinion .
    
    Reply
  - Ngô Quang Hưng
    
    Posted 24/08/2010 at 8:26 am | Permalink
    
    Hello Khoa,
    
    1. Định lý Arrow nói rằng không tồn tại cách bầu “duy lý tuyệt đối trong mọi trường hợp”. Chứng minh xác suất cho thấy là xác suất có một kết quả phi lý là khác 0, do đó — tồn tại kết quả phi lý — dẫn đến không tồn tại cách bầu duy lý.
    
    (Đáng lẽ tôi phải dùng chữ “kết quả phí lý” thay vì viết là “cách bầu phí lý”. Hy vọng câu trên rõ ràng hơn câu đã viết.)
    
    Do đó, equal chance hay không không quan trọng, mình chọn phân bố xác suất nào cũng được, miễn là chứng minh được rằng tồn tại một kết quả bầu cử phi lý là chứng minh được định lý Arrow.
    
    Con số .912 dùng trong trường hợp mình hoàn toàn không có thông tin nào khác về preferences của voters. Trong trường hợp này prior distribution hữu lý duy nhất là uniform distribution.
    
    2. Biến đổi Fourier rời rạc như viết trong bài thì dĩ nhiên không có vụ “hàm tuần hoàn”, nhưng như vậy hơi so sánh táo với cam.
    
    Tôi không viết ra vì không cần thiết cho bài này, nhưng mấy cái duality và convolution (với định nghĩa convolution operator thích hợp) đều vẫn đúng trong cái framework đã trình bày ở trên. Cái Discrete Fourier Transform dùng trong xử lý tín hiệu là trường hợp đặc biệt của cái framework trên.
    
    “Fourier transform on Finite Abelian groups” là một thuật ngữ được dùng rộng rãi. Khoa xem bất kỳ sách Harmonic analysis nào đều thấy.
    
    Reply
  - Khoa
    
    Posted 24/08/2010 at 4:43 pm | Permalink
    
    1. * Em hiểu phương pháp dùng xác suất. Tuy nhiên, nếu distribution của các bộ là bất kỳ thì lúc triển khai sẽ rất messy, và có thể too messy. Cụ thể, chứng minh ở trên sẽ break down ở đoạn này:
    “Do x, y, z có vai trò như nhau, ta kết luận $\displaystyle \mathop{\textnormal{E}}_{{\bf x,y,z}}[\text{NAE}(f({\bf x}), f({\bf y}), f({\bf z})] = \frac 3 4 - \frac 3 4 \text{E}[f({\bf x})f({\bf y})]$ .
    
    * Trong bài toán social choice thì mình không biết được a priori distribution. Nếu biết được thì đã không cần bầu làm gì, do luật số lớn. Và không phải bài toán nào cũng cần giả định a priori distribution.
    
    2. Thank you. Now I understand why it is called Fourier transform.
    
    Reply
  - Khoa
    
    Posted 25/08/2010 at 6:13 am | Permalink
    
    Well, cho em dinh chinh them 1 lan nua . Dung la em da khong de y nguyen tac chung minh ton tai, i.e. minh co the assume any reasonable distribution.
    
    Reply
Khoa

Posted 23/08/2010 at 11:36 pm | Permalink

PS: “Toán (kể cả loại trừu tượng) chắc chắn là không vô dụng”

Well, chẳng môn học nào là vô dụng . Nhưng như thế không ý nghĩa mấy khi bàn đến vấn đề hoạch định tài nguyên (resource allocation). Mình chỉ có thể bàn Toán (trừu tượng) có đáng được đầu tư (nhiều hơn).

Reply

PCP 10 — Biến đổi Fourier, định lý Arrow và tính duy lý của sự độc tài

13 Comments

Post a Comment Cancel reply

Thông điệp ngắn

Phản hồi mới

Bài mới

Thư khố

Chuyên Mục

Báo chí

Bảo mật

Blog Việt

Chưa phân loại

Giáo dục

Kỹ thuật

Khoa học khác

Kinh tế, luật pháp, xã hội

Lý thuyết & thuật toán

Mạng

Não học

Toán học

Vật Lý