Created By Tee

พิสูจน์ Arrow’s Theorem (ภาคสอง)

July 12th, 2008

ใครยังไม่ได้อ่าน ตอนหนึ่ง ควรไปอ่านก่อนครับ
ต้องบอกก่อนว่า ผมไม่ได้คิดเองนะครับ ตอนแรกอ่านเล่น ๆ ที่ wikipedia แล้วเห็นว่า proof ก็เลยมาแปลให้ฟังครับ เห็นยังไม่มีใครเขียนเป็นภาษาไทย การอ่าน proof ไม่เหมือนการอ่านนิยายนะครับ ไม่เหมือนการอ่านข่าว หรือ การอ่านบทความนะครับ บางทีประโยคเดียวต้องอ่าน หลายรอบนะครับ บางทีต้องอ่านแล้วหยุดคิดแล้วอ่าน บางทีต้องอ่านแล้วย้อนกลับไปอ่านตั้งแต่ต้นใหม่ หาได้น้อยคนครับที่อ่านรวดเดียวเข้าใจเลย(ไม่นับพวกไม่คิดเชื่อง่าย) ทุกคำที่ไม่เข้าใจต้องย้อนกลับไปดูที่นิยาม (ผมนิยามทุกคำที่ผมใช้ในนี่ไว้ที่ ภาค หนึ่ง)

อันนี้คือสิ่งที่ผมจะพิสูจน์ 2) และ 3) จะ imply ว่า dictator exists

เริ่มที่ part ที่ไม่ค่อยเท่ก่อน

เอาล่ะเริ่มที่ เคลมนี้ก่อนว่า ถ้าผมพิสูจน์ Arrow’s Theorem สำหรับเคสที่มี 3 ตัวเลือกได้ ผมจะพิสูจน์ได้สำหรับทุกเคสที่มีตัวเลือกมากกว่า เท่ากับสาม

เหตุผลก็ด้วย mathematical induction กับ IIA ง่าย ๆ ว่า ตัดตัวเลือกออกตัวนึง จะได้เคสที่เราพิสูจน์ได้แล้ว ว่ามี dictator ที่dictate ผลของการเลือกตั้ง สำหรับเคสที่คนน้อยกว่า ได้ อยู่หลายคน แล้วก็แค่พิสูจน์ว่าที่เราคิดว่าหลายคนนั้นเนี่ยเป็นคนเดียวกัน สองคนจะ กำหนด order ของ dictator ของคนที่สามได้

นั่นคือ สมมติว่าเราคิดเคสสี่ตัวเลือก A B C D แบ่งเป็นสาม dictator (เขียนแค่สอง เพราะพอแล้ว) ตัดตัวเลือกออกไป แล้วใช้ IIA นั่นคือ ลำดับของตัวเลือกที่เหลือไม่เปลี่ยน

1. คนแรก dictate ลำดับของ A B C ได้
2. คนที่สอง dictate ลำดับของ B C D ได้

เพราะฉะนั้น เราได้รู้หลายอย่างเลยว่า 1 กับ 2 ต้องเป็นคนเดียวกันเพราะว่า ไม่งั้นเค้าเถียงกันเรื่องลำดับของ B กับ C
เพราะฉะนั้นมี dictator คนเดียวและคนนั้น dictate ลำดับของ A B C และ D ได้ QED.

เอาล่ะ คราวนี้มา part สุดเท่ ผมอ่านทีแรกแล้วช้อบชอบ

คราวนี้ผมจะมา prove ว่า เคส 3 ตัวเลือกเนี่ยถ้า 2) กับ 3) เป็นจริง แล้วจะมี dictator

เพื่อความง่ายต่อการพิมพ์ผมจะให้ ตัวเลือกทั้งสามเนี่ยเป็น A B C นะครับ
จำสัญลักษณ์นี้ไว้นะครับ
F( R_1 , R_2 , … R_n) = Q

เริ่มที่การพิจารณา เคสแรก ทุกคนชอบ B มาก
นั่นคือ สำหรับทุก R_i จะเป็น form ของ B > ? > ? ลำดับของ A กับ C ไม่สน
ในเคสนี้เนื่องจากทุกคนชอบ B มากกว่าทุกอย่าง Q หรือผลลัพธ์ของการเลือกตั้งต้องบอกว่า B ชนะ โดย Pareto(2)
นั่นคือ Q = B > ? > ?

คราวนี้เปลี่ยนนะครับ เป็นเคสที่สอง ทุกคนเกลียด B สุด ๆ
นั่นคือสำหรับทุก R_i จะเป็นแบบ ? > ? > B
โดยเหตุผลคล้าย ๆ กับข้างบน(pareto) Q = ? > ? > B

คราวนี้ เริ่มจากเคสแรก ถ้าผมค่อยเปลี่ยนลำดับของ B จากบนสุด(ทุกคนชอบ) มาเป็นล่างสุด(เกลียดสุด) ของ R_1 … R_n ทีละคนแล้วผมดูว่า Q เป็นอะไรบ้าง
สังเกตว่าผมไม่เอา B ไปใส่ตรงกลาง และ ไม่แตะลำดับของ A กับ C นะครับ

เคลมของผมคราวนี้ที่ผมจะพิสูจน์คือใน Q เนี่ยจะไม่มี B อยู่ตรงกลางเลยในการเปลี่ยนลำดับของผม นั่นคือ Q จะเปลี่ยนลำดับ ของ B จากข้างบนเป็นข้างล่างทันทีเมื่อผมผ่าน คนที่ R_m (ตั้งชื่อไว้เรียกก่อน)

ผมจะพิสูจน์ด้วย contradiction นะครับ
เริ่มด้วยว่า สมมติว่าเมื่อผมเปลี่ยน B จากข้างบนเป็นข้างล่างของคุณ R_m ปุ๊บ B ใน Q เปลี่ยนไปอยู่ตรงกลาง
นั่นคือในสถานการณ์นี้
R_1…R_m-1 เนี่ยเกลียด B สุด ๆ เป็น ? > ? > B
R_m+1…R_n เนี่ยชอบ B สุด ๆ เป็น B > ? > ?
และคุณ R_m เจ้าปัญหา เกลียด B เป็น ? > ? > B
แล้ว Q เนี่ยก่อนที่ R_m จะเกลียด B(R_m = B > ? > ?) เป็น B > A > C (ลำดับของ A กับ C ไม่ค่อยสำคัญ สำคัญแค่ B อยู่บนสุด ด้วย definition ของ R_m) without loss of generality (หมายถึงถ้าจะ prove เคสที่เหลือก็สลับ C กับ A และเปลี่ยน C กับ A ใน proof ตามสมควร)
และหลังเปลี่ยนเป็นชอบเนี่ย เป็น A > B > C (ลำดับของ A กับ C ต้องเหมือนเดิม เพราะ IIA เราเปลี่ยนแต่ B ไม่ได้เปลี่ยนลำดับ A กับ C) เรียกอันนี้ว่า เคสที่ 3

คราวนี้ เราสมมติว่า ทุกคนเปลี่ยนมาชอบ C มาชอบมากกว่า A ทุกคน(แต่ไม่แซง B) ดังตัวอย่างข้างล่าง
อย่างเช่นเมื่อก่อน เป็น A > C > B (อยู่ในกลุ่ม R_1…R_m) เปลี่ยน เป็น C > A > B
หรือเมื่อก่อน เป็น C > A > B (อยู่ในกลุ่ม R_1…R_m) ก็ไม่ต้องเปลี่ยนอะไรเป็น C > A > B เหมือนเดิม
หรือเมื่อก่อน เป็น B > A > C (อยู่ในกลุ่ม R_m+1…R_n) ก็เปลี่ยนเป็น B > C > A
หรือเมื่อก่อน เป็น B > C > A (อยู่ในกลุ่ม R_m+1…R_n) ก็ไม่ต้องเปลี่ยนอะไรเป็น B > C > A เหมือนเดิม

ดูจากข้างบนจะเห็นได้ว่า การเปลี่ยนมาขอบ C มากกว่า A ของทุกคนเนี่ยเนี่ยเราไม่ได้เปลี่ยนลำดับของ A กับ B หรือ B กับ C ของใครซักคนเลย (เทียบกับเคส 3 )

ลองมาดูซิว่า Q เป็นอะไรได้บ้าง ก่อนอื่นเรารู้ว่า Q ต้องชอบ C มากกว่า A เพราะว่าทุกคนชอบ C มากกว่า A ( pareto)

คราวนี้มาดูซิว่า B จะต้องอยู่ไหน ถ้าเราเทียบกับ เคส 3 เนื่องจากเราไม่ได้เปลี่ยนลำดับของ A กับ B ลำดับของ A กับ B ของ Q ในเคส 3 กับเ คสนี้ต้องเหมือนกัน(โดย IIA) เพราะฉะนั้นเราได้ว่า Q ต้องชอบ B น้อยกว่า A

คราวนี้ถ้าเราใช้เหตุผลเดียวกันกับ ลำดับของ C กับ B ก็จะได้ว่า Q ต้องชอบ B มากกว่า C

สรุปเราได้มาสามอันว่า C > A , A > B , B > C ซึ่งเป็นไปไม่ได้
นั่นคือ สองอันแรกจะบอกว่า Q = C > A > B
อันแรกกับอันที่สามจะบอกว่า Q = B > C > A
ซึ่ง Q มีได้ค่าเดียวเพราะฉะนั้น สิ่งที่เราสมมติ ว่า R_m จะเปลี่ยน B ไปอยู่ตรงกลางของ Q เป็นไปไม่ได้

สรุปก่อนว่า ตอนนี้เราได้ว่าถ้าเราเปลี่ยนความชอบของ B ของแต่ละคนจากข้างบนไปล่าง เนี่ยจะไม่มี เลยที่ B จะไปอยู่ตรงกลางของ Q นั่นคือ B เปลี่ยนจากข้างบนเป็นข้างล่างทันที จำอันนี้ไว้

เกือบจบละ
คราวนี้เราจะใช้ที่เราเพิ่งพิสูจน์กันให้เป็นประโยชน์ ดูว่ามันสอนอะไรเรา
คราวนี้ผมจะนิยาม R_m ใหม่ว่าแทนที่จะเป็นคนที่ทำให้ B มาอยู่ตรงกลาง เป็นคนแรกที่จะทำให้ B มาอยู่ข้างบน
นั่นคือ
R_1…R_m-1 เนี่ยเกลียด B สุด ๆ เป็น ? > ? > B
R_m+1…R_n เนี่ยชอบ B สุด ๆ เป็น B > ? > ?
และคุณ R_m เจ้าปัญหา เนี่ย ถ้า B อยู่ข้างบน เป็น B > ? > ? แล้ว Q = B > A > C เรียกเคสนี้ว่าเคสที่ 4 (without loss of generality ผมเอา A ขึ้น ก่อน C)
แต่ถ้าคุณ R_m เจ้าปัญหาเนี่ยเอา B อยู่ข้างล่างเป็น ? > ? > B แล้ว Q = A > C > B และเรียกเคสนี้ว่าเคสที่ 5 (ลำดับของ A กับ C ตามเคส 4 ด้วย IIA นั่นคือผมไม่ได้สลับลำดับ Aกับ C ของใครเลย)

คราวนี้ลองพิจารณาเคส คุณ R_m เอา B มาอยู่ตรงกลาง

R_1…R_m-1 เนี่ยเกลียด B สุด ๆ เป็น ? > ? > B
R_m+1…R_n เนี่ยชอบ B สุด ๆ เป็น B > ? > ?
และ R_m เลือก A > B > C

ลองดูซิว่า Q จะเป็นอะไรลองดูแค่ ลำดับของ A กับ C
เคสนี้ง่ายครับ เพราะ ผมไม่ได้สลับลำดับของ A กับ C ของใครเลย ในเคสนี้กับเคสที่ 4 เพราะฉะนั้น A > C (โดย IIA ) เหมือนที่ R_m เลือก

คราวนี้ถ้าเป็นเหมือนเดิมแต่ R_m เลือก C > B > A ล่ะ นั่นคือ
R_1…R_m-1 เนี่ยเกลียด B สุด ๆ เป็น ? > ? > B
R_m+1…R_n เนี่ยชอบ B สุด ๆ เป็น B > ? > ?
และ R_m เลือก C > B > A

คราวนี้ผมใช้ IIA เทียบกับลำดับ C กับ A ในเคส 4 ไม่ได้ละเพราะว่า ผมสลับลำดับ C กับ A ของ R_m แต่ว่า…
ถ้าเทียบกับเคส 4 ผมไม่ได้สลับลำดับ B กับ A เพราะฉะนั้น ด้วย IIA เราได้ว่า B > A
และเทียบกับเคส 5 ผมไม่ได้สลับลำดับ B กับ C เพราะฉะนั้นด้วย IIA เราได้ว่า C > B
รวมสองอันเราได้ว่า C > B > A หรือเราสนใจแค่ลำดับ ของ A กับ C คือ C > A เหมือนที่ R_m เลือก

สรุปได้ว่า R_m เลือกลำดับของ A กับ C ได้ ถ้าตำแหน่องของ B เป็นตามที่ผมบอก
แต่ว่าด้วย IIA ลำดับของ A กับ C เนี่ยไม่ควรขึ้นอยู่กับว่า R ต่าง ๆ จะชอบหรือเกลียด B ยังไงด้วย

เพราะฉะนั้นบอกได้ว่า R_m กำหนดลำดับของ A กับ C ได้ หรือบอกได้ว่า
มีคนที่กำหนดลำดับA กับ C ได้

เกือบจบจริง ๆ ละ

ด้วยการ พิสูจน์แบบเดียวกัน (เปลี่ยนชื่อ A B C เฉย ๆ ) จะได้ว่า
มีคนที่กำหนดลำดับ B กับ C ได้ เรียกว่า คุณ B-C
และมีคนที่กำหนดลำดับ A กับ B ได้ เรียกว่าคุณ A-B
และมีคนที่กำหนดลำดับA กับ C ได้ เรียกว่าคุณ A-C

คราวนี้เราก็เหลือให้พิสูจน์ง่าย ๆ ว่า สามคนนี้เป็นคนเดียวกัน

อันนี้ง่ายมากครับ เพราะว่า ถ้าเราพิจารณาว่า ถ้าคุณ A-C กับ กับ คุณ A-B เลือกลำดับตัวใครตัวมันแล้ว คุณ B-C อาจจะไม่มีสิทธิเลือก เพราะลำดับ B กับ C ถูก fixed แล้ว (อย่างเช่น A > C กับ A < B จะสรุปได้ว B > C โดยที่คุณ B-C ยังไม่ได้เลือก)

เพราะฉะนั้น ต้องมีคนนึงใน คุณ A-C กับคุณ A-B ที่เลือกลำดับ B - C ได้ ไม่ว่าจะเป็นใครพอบังคับลำดับได้สองอันแล้ว อีกคนนึงจะไม่มีสิทธิเลือกเพราะฉะนั้น ทางเดียวที่จะเป็นไปได้คือ ทั้งสามคนนี้คือคนเดียวกัน

เพราะฉะนั้นผมพิสูจน์ได้ว่า dictator exists สำหรับ เคส 3 ตัวเลือก
และใช้ induction ที่ผมโชว์ไว้ข้างบนก็จะบอกได้ว่า dictator exists สำหรับเคสมากกว่าหรือเท่ากับ 3 ตัวเลือก ( 2 รอด)

proof นี้เอา idea มาจาก proof ของคุณ John Geanakoplos ผมมอบ proof นี้ให้เป็น public domain ครับ(จริง ๆ มันเป็นอยู่แล้ว proof ทางคณิตศาสตร์ทุกอัน copyright และ patent ไม่ได้) (เดี๋ยวว่าง ๆ จะเอาไปแปะบน wikipedia ของไทย)

Entry Filed under: Uncategorized