Nerd Test result
คนอื่นเค้าทำกันก็ทำมั่ง
Add comment July 12th, 2008
Archive for July, 2008
พิสูจน์ Arrow’s Theorem (ภาคสอง)
ใครยังไม่ได้อ่าน ตอนหนึ่ง ควรไปอ่านก่อนครับ
ต้องบอกก่อนว่า ผมไม่ได้คิดเองนะครับ ตอนแรกอ่านเล่น ๆ ที่ 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 นั่นคือ ลำดับของตัวเลือกที่เหลือไม่เปลี่ยน
- คนแรก dictate ลำดับของ A B C ได้
- คนที่สอง 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 ของไทย)
Add comment July 12th, 2008
Arrow’s Impossibility Theorem (ตอนหนึ่ง)
เรื่องนี้คิดอยู่นานว่าเขียนดีไม่เขียนดี เพราะเดาว่าเขียนไปคนที่อ่านรู้เรื่องคงมีไม่กี่คน ต้องเป็นคนที่เข้าใจ logic พอสมควรทีเดียวที่จะอ่านแล้วเข้าใจได้ ผมว่ามีน้อยคนที่จะอ่านรู้เรื่อง เพราะฉะนั้นอ่านไม่รู้เรื่องไม่ต้องเสียใจครับ แต่เห็นว่าไม่เคยมีใครเขียนเรื่องนี้เป็นภาษาไทย ก็เลยเขียนไว้เผื่อมีคนอยากรู้
การเลือกตั้ง ลงคะแนนเสียง จริง ๆ แล้วก็คือคือ การจัดลำดับความชอบของคนในสังคมแบบที่ make sense ตรงสัญชาตญาณ หรือ ที่หลาย ๆ คนเรียกว่า common sense จะบอกว่าอย่างนั้น แต่ที่จริงแล้วมันสามารถพิสูจน์ได้ว่า การเลือกตั้งมันไม่ค่อย make sense (ถ้ามีตัวเลือกตั้งแต่สามคนขึ้นไป) เท่าไหร่ เอาล่ะพูดแล้วงง ผมจะพูดให้ชัดเจนขึ้นนะครับ พยายามเอา ความยากทางเทคนิคออกไปทำให้ อาจจะทำให้บางที่ไม่สมบูรณ์ได้
เอาละมาเข้าใจก่อนว่า การเลือกตั้งเนี่ยแปลว่าอะไร สมมติว่ามีคนสามพรรค มาสมัครรับเลือกตั้ง พรรค A พรรค B และ พรรค C ให้คนเลือกเลยว่าชอบพรรคไหนมากกว่าพรรคไหนลำดับอย่างไร
อย่างเช่น ผมอาจจะชอบ A มากกว่า B มากกว่า C ( A > B > C) เป็นต้น ผมจะเรียกสิ่งนี้ว่า Preference (ลำดับความชอบ) และแทนมันด้วยตัว R
ถ้ามีหลายคนผมก็จะเรียกว่า R_1 , R_2 , R_3 …. ไปหมายถึง ความชอบของคนที่หนึ่ง คนที่สอง คนที่สาม และ ไปเรื่อย ๆ เพื่อเป็นความสั้นผมจะเรียกมันทั้งหมดว่า R_i
คราวนี้การเลือกตั้งถ้าคิดดี ๆ มันก็แค่ การเอา ความชอบของทุกคน ( R_i ) มาแล้วคิด ๆ ๆ ๆ แล้วได้ ความชอบของสังคมออกมา Q อย่างเช่น Q = B > A > C เป็นต้น ผมเลือกใช้ การเลือกตั้งว่า F เพราะฉะนั้นเขียนสั้น ๆ ว่า F(R_1,R_2,….) = F(R_i) = Q
คราวนี้ลองถามซิว่าการเลือกตั้งที่ ยุติธรรมและ make sense มีอะไรบ้าง นั่นคือ F ต้องทำอะไรบ้าง
- no dictator นั่นหมายความว่า ไม่มีคนที่สามารถเลือกผลลัพท์ของสังคมได้ ไม่ว่าคนอื่นเลือกว่าอะไร ตัวอย่างคือ สมมติว่าผมเป็น dictator หรือที่คนไทยชอบเรียกว่าจอมเผด็จการ คนอื่นจะโหวตอะไรก็ตาม ผมลัพธ์ที่ออกมาจากการเลือกตั้งจะเหมือนที่ผมเลือกเสมอ หรือในสัญลักษณ์ที่ผมเขียนข้างบนไว้ว่า ไม่มี j ใด ๆ ที่ทำให้ F(R_1,R_2 …, R_j, … ) = R_j สำหรับทุก R_i
- Pareto Efficiency(PE) อันนี้คือ ถ้าสมมติว่าทุกคนชอบ A มากกว่า B ผลความชอบของสังคมออกมาต้องบอกว่า สังคมชอบ A มากกว่า B ด้วย make sense มาก
- Independence of Irrelevant Alternatives(IIA) อันนี้คล้ายกับข้างบนแต่ต่างกันนิดหน่อย(มีสมมติฐานเพิ่มนิดหน่อยแล้วจะ พิสูจน์ข้างบนได้) อันนี้บอกว่า สมมติว่า ความชอบของสังคมบอกว่า สังคมชอบ A > B คราวนี้ สมมติอีกว่าเมื่อก่อนเนี่ย ตัวผม(ไม่ใช่สังคม) ชอบ B > A > C คราวนี้ผมเปลี่ยนใจว่าผมชอบ C สุด ๆเปลี่ยนใจมาเป็น C > B > A โดยลำดับความชอบระหว่าง A ยังคงเดิม ความชอบของสังคม ระหว่าง A กับ B ต้องเหมือนเดิม
ถ้างงสมมติว่า สังคมบอกว่า ชอบ ส้มตำ มากกว่า ลาบ โดยที่ผมโหวตไปว่า ผมชอบ ลาบ > ส้มตำ > น้ำตก คราวนี้สมมติว่าผมเปลี่ยนใจชอบน้ำตกสุด ๆ เปลี่ยนโหวตผมเป็น น้ำตก > ลาบ > ส้มตำ โดยผมก็ยังชอบลาบมากกว่าส้มตำอยู่ดี เพราะฉะนั้น ผมความชอบของสังคมระหว่าง ส้มตำกับลาบ ไม่ควรจะเปลี่ยน
สามข้อนี้ ดูออกจะ make sense เข้าท่า ว่าเป็นข้อบังคับง่าย ๆ ของการเลือกตั้งที่ควรจะเป็น แต่….มันพิสูจน์ได้ว่า สามข้อนี้เป็นจริงพร้อมกันไม่ได้
นั่นคือพิสูจน์ได้ว่า PE กับ IIA เป็นจริง จะมีคนที่กำหนดผลการเลือกตั้งได้ (ไม่ต้องซื้อเสียงด้วย ไม่ต้องใช้ม.7 ด้วย) การพิสูจน์จะตามมาในตอนสองนะครับ เดี๋ยวจะอ่านกันเหนื่อย เพราะบางคนอาจจะไม่สนใจพิสูจน์ ก็เลยแยกเป็นสองตอนให้ แต่ผมว่าเป็นการพิสูจน์ที่ค่อนข้างเท่มากนะครับ (คำว่าพิสูจน์ในที่นี้คือพิสูจน์ทางคณิตศาสตร์ ไม่ใช่การพิสูจน์แบบ “เมื่อมีเหตุอันควรเชื่อได้ว่า” นะครับ )
ตอนสองอยู่นี่ครับ
Add comment July 9th, 2008