กลับไปหน้าบทความ

อ่าน 9 นาที

กฎการลงคะแนนของ Phragmen

กฎการลงคะแนนของ Phragménเป็นกฎสำหรับการลงคะแนนแบบผู้ชนะหลายคนกฎเหล่านี้อนุญาตให้ผู้มีสิทธิเลือกตั้งลงคะแนนให้กับผู้สมัครแต่ละคนแทนที่จะเป็นพรรคการเมือง...

กฎการลงคะแนนของ Phragmen

กฎการลงคะแนนของ Phragménเป็นกฎสำหรับการลงคะแนนแบบผู้ชนะหลายคนกฎเหล่านี้อนุญาตให้ผู้มีสิทธิเลือกตั้งลงคะแนนให้กับผู้สมัครแต่ละคนแทนที่จะเป็นพรรคการเมือง แต่ยังคงรับประกันการเป็นตัวแทนตามสัดส่วน กฎเหล่านี้ได้รับการตีพิมพ์โดยLars Edvard Phragménเป็นภาษาฝรั่งเศสและสวีเดนระหว่างปี 1893 ถึง 1899 [ 1 ]และได้รับการแปลเป็นภาษาอังกฤษโดยSvante Jansonในปี 2016 [ 2 ]

พื้นหลัง

ในการลงคะแนนแบบอนุมัติผู้ชนะหลายคน ผู้มีสิทธิเลือกตั้งแต่ละคนสามารถลงคะแนนให้ผู้สมัครได้หนึ่งคนหรือมากกว่า และเป้าหมายคือการเลือกผู้ชนะจำนวนคง ที่ kคน (โดยที่kอาจเป็นจำนวนสมาชิกสภาผู้แทนราษฎรก็ได้) คำถามคือจะกำหนดชุดของผู้ชนะได้อย่างไร?

  • วิธีที่ง่ายที่สุดคือการลงคะแนนแบบหลายเสียงที่ไม่สามารถโอนได้ซึ่ง ผู้สมัคร kคนที่ได้รับคะแนนนิยมมากที่สุดจะได้รับการเลือกตั้ง แต่โดยทั่วไปแล้ววิธีนี้มักจะเลือก ผู้สมัคร kคนจากพรรคที่ใหญ่ที่สุด ทำให้พรรคเล็กๆ ไม่มีตัวแทนเลย
  • ในศตวรรษที่ 19 มีการถกเถียงกันอย่างมากเกี่ยวกับระบบการเลือกตั้งที่สามารถรับประกันการเป็นตัวแทนตามสัดส่วนได้หนึ่งในแนวทางแก้ไข ซึ่งเสนอโดยD'Hondtในปี 1878 คือการลงคะแนนเสียงให้แก่บัญชีรายชื่อพรรคการเมืองแทนที่จะลงคะแนนให้แก่ผู้สมัครรายบุคคล แนวทางนี้ยังคงใช้กันอย่างแพร่หลายในปัจจุบัน

Phragmén ต้องการคงการลงคะแนนเสียงให้กับผู้สมัครแต่ละคน เพื่อให้ผู้มีสิทธิเลือกตั้งสามารถอนุมัติผู้สมัครตามคุณสมบัติส่วนตัวได้ ในกรณีพิเศษที่ผู้มีสิทธิเลือกตั้งแต่ละคนอนุมัติผู้สมัครทั้งหมดและเฉพาะผู้สมัครจากพรรคเดียวเท่านั้น วิธีการของ Phragmén จะให้ผลลัพธ์เช่นเดียวกับวิธีการของ D'Hondt [ 2 ] : มาตรา 11 อย่างไรก็ตาม วิธีการของ Phragmén สามารถจัดการกับสถานการณ์ทั่วไปได้มากกว่า ซึ่งผู้มีสิทธิเลือกตั้งอาจลงคะแนนให้ผู้สมัครจากพรรคต่างๆ (อันที่จริง วิธีการนี้ไม่สนใจข้อมูลว่าผู้สมัครคนใดสังกัดพรรคใด)

กฎของ Phragmén สำหรับการลงคะแนนอนุมัติ

วิธีการของ Phragmén สำหรับบัตรลงคะแนนที่ไม่เรียงลำดับ (อนุมัติ) สามารถนำเสนอได้หลายวิธีที่เทียบเท่ากัน[ 2 ] : มาตรา 3

การปรับสมดุลภาระงาน

ผู้สมัครที่ได้รับเลือกแต่ละคนจะสร้าง "ภาระ" 1 หน่วย ภาระของผู้สมัครจะต้องตกเป็นของผู้มีสิทธิเลือกตั้งที่สนับสนุนเขา เป้าหมายคือการหาคณะกรรมการที่สามารถแบ่งภาระนั้นให้กับผู้มีสิทธิเลือกตั้งได้อย่าง "สมดุล" ที่สุด

ขึ้นอยู่กับคำจำกัดความที่แน่นอนของคำว่า "สมดุล" อาจมีกฎหลายข้อที่เป็นไปได้: [ 3 ]

  • วลี Leximax:ลดภาระสูงสุดให้น้อยที่สุด และภายใต้เงื่อนไขนั้น ภาระสูงสุดอันดับสองก็จะตามมา เป็นต้น (โดยใช้การเพิ่มประสิทธิภาพสูงสุด-ต่ำสุดตามลำดับตัวอักษร )
  • เลกซิมิน-วลี : การเพิ่มภาระขั้นต่ำให้สูงสุด และภายใต้เงื่อนไขนั้น ภาระขั้นต่ำอันดับสอง เป็นต้น
  • วิธี var-Phragmenหรือวิธีของ Ebert : การลดความแปรปรวนของภาระ ให้เหลือน้อยที่สุด

แต่ละรูปแบบเหล่านี้มีรูปแบบย่อยสองรูปแบบ:

  • รูป แบบ การหาค่าเหมาะสมที่สุดระดับโลกซึ่งโดยปกติแล้วเป็นปัญหา NP-hard ที่คำนวณได้ยาก
  • รูป แบบ ลำดับที่ผู้สมัครจะถูกเลือกตามลำดับ และในแต่ละรอบ ผู้สมัครที่ได้รับเลือกเป็นคนถัดไปคือผู้ที่มีคะแนนดีที่สุดในบรรดาผู้สมัครทั้งหมด (กล่าวคืออัลกอริทึมแบบโลภ )

วิธีการดั้งเดิมของ Phragmen คือวิธีการเรียงลำดับที่ลดภาระสูงสุดให้น้อยที่สุด ซึ่งปัจจุบันเรียกว่าSeq- Phragmen [ 3 ]

ในทางปฏิบัติ กฎที่มีการรับประกันเชิงสัจพจน์ที่ดีที่สุดในหมวดหมู่การหาค่าเหมาะสมที่สุดทั่วโลกคือ leximax-Phragmen และ var-Phragmen ส่วนในบรรดารูปแบบลำดับ กฎที่มีการรับประกันที่ดีที่สุดคือ Seq-Phragmen

พลาห์เมนอธิบายวิธีการของเขาโดยเปรียบเทียบผู้มีสิทธิเลือกตั้งแต่ละคนเป็นภาชนะ น้ำในภาชนะแต่ละใบแทนผู้สมัครที่ได้รับเลือกตั้งแล้ว หากต้องการเลือกผู้สมัครคนใหม่ จะต้องเทน้ำ 1 ลิตรลงในภาชนะที่ตรงกับผู้มีสิทธิเลือกตั้งที่เลือกผู้สมัครคนนั้น โดยต้องเทน้ำให้ระดับน้ำสูงสุดอยู่ในระดับต่ำที่สุดเท่าที่จะเป็นไปได้

เงินเสมือนจริง

อีกทางเลือกหนึ่งในการอธิบาย Seq-Phragmen คือกระบวนการต่อเนื่องดังต่อไปนี้:

  • ผู้ลงคะแนนแต่ละคนเริ่มต้นด้วยเงินเสมือนจริง 0 บาท และจะได้รับเงินในอัตราคงที่วันละ 1 บาท
  • ในแต่ละช่วงเวลาtเราจะกำหนดว่าผู้สมัครที่ยังไม่ได้รับเลือกตั้งxนั้นมีกำลังซื้อหากจำนวนเงินทั้งหมดที่ผู้มีสิทธิเลือกตั้งที่เห็นชอบกับx ถือครองอยู่นั้น มีอย่างน้อย 1
  • เมื่อพบผู้สมัครที่มีคุณสมบัติเหมาะสม เราจะเลือกผู้สมัครที่มีคุณสมบัติเหมาะสมy คนใดคนหนึ่งโดยพลการ จากนั้น เพิ่มyเข้าสู่คณะกรรมการ และรีเซ็ตเงินเสมือนจริงของผู้ลงคะแนนที่เห็นชอบกับy (เนื่องจากพวกเขาได้ "ใช้" เงินเสมือนจริงของตนเพื่อสนับสนุนy แล้ว )
  • ผู้มีสิทธิเลือกตั้งจะยังคงได้รับเงินเสมือนจริงและให้เงินสนับสนุนผู้สมัครต่อไปจนกว่าสมาชิกคณะกรรมการk ทั้งหมดจะได้รับการเลือกตั้ง

ตัวอย่าง

บัญชีรายชื่อพรรค

ตัวอย่างง่ายๆ ต่อไปนี้คล้ายกับการลงคะแนนแบบบัญชีรายชื่อพรรคการเมือง มีที่นั่ง k=6 ที่นั่ง และผู้สมัคร 9 คน ซึ่งแทนด้วย a, b, c, d, e, f, g, h, i มีผู้มีสิทธิเลือกตั้ง 63 คน โดยมีลำดับความชอบดังนี้: 31 คนเห็นด้วยกับ a, b, c; 21 คนเห็นด้วยกับ d, e, f; และ 11 คนเห็นด้วยกับ g, h, i

รอบที่ 1

กำหนดให้ผู้สมัครแต่ละคนได้รับคะแนนเท่ากับส่วนกลับของจำนวนผู้ที่อนุมัติ เราจะได้ผลลัพธ์ดังต่อไปนี้:

ผู้สมัคร คะแนน
เอ 1/31
1/31
1/31
1/21
อี 1/21
เอฟ 1/21
จี 1/11
ชม. 1/11
ฉัน 1/11

เราเลือกผู้สมัครที่มีคะแนนต่ำที่สุด ในกรณีนี้ คะแนนเท่ากันระหว่าง a, b และ c สมมติว่าเราเลือก a

รอบที่ 2

ตอนนี้ คะแนนของผู้สมัครจะเพิ่มขึ้นตามผลคูณของ 1/31 (คะแนนของ a) และสัดส่วนของผู้อนุมัติที่อนุมัติ a ด้วยเช่นกัน

ผู้สมัคร อนุพันธ์ คะแนน
1/31+1(1/31) 231
1/31+1(1/31) 231
1/21+0(1/31) 1/21
อี 1/21+0(1/31) 1/21
เอฟ 1/21+0(1/31) 1/21
จี 1/11+0(1/31) 1/11
ชม. 1/11+0(1/31) 1/11
ฉัน 1/11+0(1/31) 1/11

เราเลือกผู้สมัครที่มีคะแนนต่ำที่สุด ในกรณีนี้ คะแนนเท่ากันระหว่าง d, e และ f สมมติว่าเราเลือก d

รอบที่ 3

ตอนนี้ คะแนนของผู้สมัครจะเพิ่มขึ้นตามผลรวมของผลคูณระหว่าง 1/31 (คะแนนของ a) และสัดส่วนของผู้อนุมัติที่อนุมัติ 'ครั้งล่าสุด' คือ a กับผลคูณระหว่าง 1/21 (คะแนนของ d) และสัดส่วนของผู้อนุมัติที่อนุมัติ 'ครั้งล่าสุด' คือ d

ผู้สมัคร อนุพันธ์ คะแนน
1/31+1(1/31)+0(1/21) 231
1/31+1(1/31)+0(1/21) 231
อี 1/21+0(1/31)+1(1/21) 221
เอฟ 1/21+0(1/31)+1(1/21) 221
จี 1/11+0(1/31)+0(1/21) 1/11
ชม. 1/11+0(1/31)+0(1/21) 1/11
ฉัน 1/11+0(1/31)+0(1/21) 1/11

เราเลือกผู้สมัครที่มีคะแนนต่ำที่สุด ในกรณีนี้ คะแนนเท่ากันระหว่าง b และ c สมมติว่าเราเลือก b

รอบที่ 4

ตอนนี้ คะแนนของผู้สมัครจะเพิ่มขึ้นตามผลรวมของผลคูณระหว่าง 1/31 (คะแนนของ a) กับสัดส่วนของผู้อนุมัติที่อนุมัติ 'ล่าสุด' คือ a และผลรวมของผลคูณระหว่าง 1/21 (คะแนนของ d) กับสัดส่วนของผู้อนุมัติที่อนุมัติ 'ล่าสุด' คือ d และผลคูณระหว่าง 2/31 (คะแนนของ b) กับสัดส่วนของผู้อนุมัติที่อนุมัติ 'ล่าสุด' คือ b

ผู้สมัคร อนุพันธ์ คะแนน
1/31+0(1/31)+0(1/21)+1(2/31) 3/31
อี 1/21+0(1/31)+1(1/21)+0(2/31) 221
เอฟ 1/21+0(1/31)+1(1/21)+0(2/31) 221
จี 1/11+0(1/31)+0(1/21)+0(2/31) 1/11
ชม. 1/11+0(1/31)+0(1/21)+0(2/31) 1/11
ฉัน 1/11+0(1/31)+0(1/21)+0(2/31) 1/11

เราเลือกผู้สมัครที่มีคะแนนต่ำที่สุด ในกรณีนี้ คะแนนเท่ากันระหว่าง g, h และ i สมมติว่าเราเลือก g

รอบที่ 5
ผู้สมัคร อนุพันธ์ คะแนน
1/31+0(1/31)+0(1/21)+1(2/31)+0(1/11) 3/31
อี 1/21+0(1/31)+1(1/21)+0(2/31)+0(1/11) 221
เอฟ 1/21+0(1/31)+1(1/21)+0(2/31)+0(1/11) 221
ชม. 1/11+0(1/31)+0(1/21)+0(2/31)+1(1/11) 211
ฉัน 1/11+0(1/31)+0(1/21)+0(2/31)+1(1/11) 211

เราเลือกผู้สมัครที่มีคะแนนต่ำที่สุด ในกรณีนี้ คะแนนเท่ากันระหว่าง e และ f สมมติว่าเราเลือก e

รอบที่ 6
ผู้สมัคร อนุพันธ์ คะแนน
1/31+0(1/31)+0(1/21)+1(2/31)+0(1/11)+0(2/21) 3/31
เอฟ 1/21+0(1/31)+0(1/21)+0(2/31)+0(1/11)+1(2/21) 3/21
ชม. 1/11+0(1/31)+0(1/21)+0(2/31)+1(1/11)+0(2/21) 211
ฉัน 1/11+0(1/31)+0(1/21)+0(2/31)+1(1/11)+0(2/21) 211

เราเลือกผู้สมัครที่มีคะแนนต่ำที่สุด ซึ่งก็คือ ค.

  • ผู้ลงคะแนนเริ่มได้รับเงินในอัตราคงที่ 1 ต่อวัน หลังจาก 1/31 หรือประมาณ 0.0323 วัน ผู้ลงคะแนน abc ทั้ง 31 คน จะมีเงินคนละ 0.0323 ดังนั้นพวกเขาสามารถรวมกันเพื่อสนับสนุนผู้สมัครที่พวกเขาเลือกได้หนึ่งคน โดยเลือกผู้สมัคร a, b หรือ c มาหนึ่งคนโดยพลการ สมมติว่าเป็น a
  • หลังจากผ่านไป 1/21 หรือประมาณ 0.0476 วัน ผู้ลงคะแนน abc 31 คน จะมีเงินเหลือเพียงประมาณ 0.015 ต่อคน แต่ ผู้ลงคะแนน def 21 คน จะมีเงิน 0.0476 ต่อคน ดังนั้นเมื่อรวมกันแล้วพวกเขาสามารถให้ทุนสนับสนุนผู้สมัครที่พวกเขาอนุมัติได้หนึ่งคน โดยเลือกหนึ่งใน d, e, f อย่างสุ่ม สมมติว่าเป็น d
  • หลังจากผ่านไปประมาณ 0.0645 วัน ผู้ลงคะแนนเสียง กลุ่ม abcจะมีคะแนนเสียงคนละ 0.0323 ดังนั้นพวกเขาจึงซื้อผู้สมัครที่พวกเขาอนุมัติอีกคนหนึ่ง เช่น ผู้สมัครกลุ่ม b
  • หลังจากผ่านไป 1/11 วัน หรือประมาณ 0.0909 วัน ผู้ลงคะแนนเสียง กลุ่ม ghiจะมีคะแนนเสียงคนละ 0.0909 ดังนั้นพวกเขาสามารถร่วมกันสนับสนุนผู้สมัครที่พวกเขาอนุมัติได้หนึ่งคน เช่น g (ณ จุดนี้ ผู้ลงคะแนนเสียง กลุ่ม abcจะมีคะแนนเสียงคนละ 0.0264 และ ผู้ลงคะแนนเสียง กลุ่ม defจะมีคะแนนเสียงคนละ 0.0434 ดังนั้นจึงไม่มีใครสามารถซื้อผู้สมัครคนอื่นได้อีก)
  • หลังจากผ่านไป 0.0952 วัน ผู้ลงคะแนนเสียงฝ่าย defจะมีคะแนนเสียง 0.0476 ต่อคนอีกครั้ง ดังนั้นพวกเขาจึงสามารถซื้อผู้สมัครคนอื่นได้ เช่น e
  • หลังจากผ่านไป 0.0968 วัน ผู้ลงคะแนนเสียงกลุ่ม abc จะมีคะแนนเสียงคนละ 0.0323 อีกครั้ง ดังนั้นพวกเขาจึงสามารถซื้อคะแนนเสียงให้ผู้สมัครคนอื่นได้ เช่น c

คณะกรรมการชุดสุดท้ายประกอบด้วย a, b, c; d, e; g โปรดสังเกตว่าแต่ละ "พรรค" จะมีตัวแทนตามสัดส่วนขนาดพรรคโดยประมาณ คือ ผู้สมัคร 3 คนต่อผู้มีสิทธิเลือกตั้ง 31 คน, ผู้สมัคร 2 คนต่อผู้มีสิทธิเลือกตั้ง 21 คน และผู้สมัคร 1 คนต่อผู้มีสิทธิเลือกตั้ง 11 คน

ขนาดเล็ก ไม่สังกัดพรรคการเมือง

ตัวอย่างเช่น หากไม่มีโครงสร้างพรรค ให้พิจารณากรณีต่อไปนี้ที่มีผู้สมัคร 4 คน ซึ่งแทนด้วย a, b, c, d และผู้มีสิทธิเลือกตั้ง 5 คน โดยมีชุดการอนุมัติ 1: a; 2: b; 3: b และ c; 4: a, b และ c; 5: d [ 3 ]

รอบที่ 1

อีกครั้งหนึ่ง กำหนดให้ผู้สมัครแต่ละคนได้รับคะแนนเท่ากับส่วนกลับของจำนวนผู้ที่อนุมัติ เราจะได้ผลลัพธ์ดังต่อไปนี้:

ผู้สมัคร คะแนน
เอ 1/2
1/3
1/2
11

เราเลือกผู้สมัครที่มีคะแนนต่ำที่สุด ซึ่งก็คือ ข.

รอบที่ 2

ตอนนี้ คะแนนของผู้สมัครจะเพิ่มขึ้นตามผลคูณของ 1/3 (คะแนนของ b) และสัดส่วนของผู้อนุมัติที่เห็นชอบกับ b ด้วย

ผู้สมัคร อนุพันธ์ คะแนน
เอ 1/2+(1/2)(1/3) 23
1/2+1(1/3) 56
1/1+0(1/3) 11

เราเลือกผู้สมัครที่มีคะแนนต่ำที่สุด ซึ่งก็คือ ก.

รอบที่ 3

ตอนนี้ คะแนนของผู้สมัครจะเพิ่มขึ้นตามผลรวมของผลคูณระหว่าง 1/3 (คะแนนของ b) กับสัดส่วนของผู้อนุมัติที่อนุมัติ b ครั้งล่าสุด และผลคูณระหว่าง 2/3 (คะแนนของ a) กับสัดส่วนของผู้อนุมัติที่อนุมัติ a ครั้งล่าสุด

ผู้สมัคร อนุพันธ์ คะแนน
1/2+(1/2)(1/3)+(1/2)(2/3) 1
1/1+0(1/3)+0(2/3) 1

เราเลือกผู้สมัครที่มีคะแนนต่ำที่สุด ในกรณีนี้ คะแนนเท่ากันระหว่าง c และ d

  • ผู้ลงคะแนนเริ่มได้รับเงินอีกครั้งในอัตราคงที่ 1 ต่อวัน หลังจากผ่านไป 1/3 วัน ผู้ที่อนุมัติ b จะมีเงินเพียงพอที่จะซื้อ b ทำให้เงินของพวกเขากลับไปเป็น 0 ส่งผลให้การกระจายเงินเป็น (1/3, 0, 0, 0, 1/3)
  • หลังจาก 2/3 วัน การกระจายเงินจะเป็น (2/3, 1/3, 1/3, 1/3, 2/3) ดังนั้น ผู้ที่อนุมัติสามารถซื้อตัวผู้สมัครได้ โดยเงินของพวกเขาจะถูกรีเซ็ตเป็น 0 ในภายหลัง ทำให้การกระจายเงินเป็น (0, 1/3, 1/3, 0, 2/3)
  • สุดท้าย หลังจาก 1 วัน การกระจายเงินจะเป็น (1/3, 2/3, 2/3, 1/3, 1) ดังนั้น สามารถซื้อ c หรือ d ได้ตามเกณฑ์การตัดสินกรณีเสมอกันที่ใช้

ดังนั้น สำหรับขนาดคณะกรรมการ k = 3 ทั้ง {a,b,c} และ {a,b,d} จึงเป็นคณะกรรมการ seq-Phragmén ที่ถูกต้อง

สมจริง

นี่คือตัวอย่างที่ 'สมจริง' มากขึ้น มี ที่นั่ง k = 3 ที่นั่ง และผู้สมัคร 6 คน ซึ่งแทนด้วย A, B, C, P, Q, R ผลการลงคะแนนคือ: 1034 คะแนนสำหรับ ABC, 519 คะแนนสำหรับ PQR, 90 คะแนนสำหรับ ABQ, 47 คะแนนสำหรับ APQ ผู้ชนะจะได้รับการเลือกตั้งตามลำดับดังนี้:

รอบที่ 1

อีกครั้งหนึ่ง กำหนดให้ผู้สมัครแต่ละคนได้รับคะแนนเท่ากับส่วนกลับของจำนวนผู้ที่อนุมัติ เราจะได้ผลลัพธ์ดังต่อไปนี้:

ผู้สมัคร คะแนน
เอ 11171
บี 11124
ซี 11034
พี 1566
คิว 1656
อาร์ 1519

เราเลือกผู้สมัครที่มีคะแนนต่ำที่สุด ซึ่งก็คือผู้สมัครชื่อ A

รอบที่ 2

ตอนนี้ คะแนนของผู้สมัครจะเพิ่มขึ้นตามผลคูณของ 1/1171 (คะแนนของ A) และสัดส่วนของผู้อนุมัติที่อนุมัติ A ด้วยเช่นกัน

ผู้สมัคร อนุพันธ์ คะแนน
บี 1/1124+1(1/1171) 22951316204
ซี 1/1034+1(1/1171) 22051210814
พี 1/566+(47/566)(1/1171) 609331393
คิว 1/656+(137/656)(1/1171) 327192044
อาร์ 1/519+0(1/1171) 1519

เราเลือกผู้สมัครที่มีคะแนนต่ำที่สุด ซึ่งก็คือ Q

รอบที่ 3

ตอนนี้ คะแนนของผู้สมัครจะเพิ่มขึ้นตามผลรวมของผลคูณของ 1/1171 (คะแนนของ A) และสัดส่วนของผู้อนุมัติที่มีการอนุมัติ 'ล่าสุด' เป็น A และผลคูณของ 327/192044 (คะแนนของ Q) และสัดส่วนของผู้อนุมัติที่มีการอนุมัติ 'ล่าสุด' เป็น Q

ผู้สมัคร อนุพันธ์ คะแนน
บี 1/1124+(517/562)(1/1171)+(45/562)(327/192044) 195525107928728
ซี 1/1034+1(1/1171)+0(327/192044) 22051210814
พี 1/566+0(1/1171)+1(327/192044) 18856354348452
อาร์ 1/519+0(1/1171)+1(327/192044) 36175799670836

เราเลือกผู้สมัครที่มีคะแนนต่ำที่สุด ซึ่งก็คือ B

การคำนวณ

Var-Phragmen และ Leximax-Phragmen เป็นปัญหา NP-hard ในการคำนวณ แม้ว่าตัวแทนแต่ละคนจะอนุมัติผู้สมัคร 2 คน และผู้สมัครแต่ละคนได้รับการอนุมัติจากผู้ลงคะแนน 3 คนก็ตาม การพิสูจน์ทำได้โดยการลดจากเซตอิสระสูงสุดบนกราฟลูกบาศก์[ 3 ]

Leximax-Phragmen สามารถคำนวณได้โดยใช้ลำดับของโปรแกรมเชิงเส้นจำนวนเต็มผสม อย่างมากที่สุด 2n โปรแกรม โดยแต่ละ โปรแกรม มีตัวแปร O( nm + ) ตัว (โดยที่nคือจำนวนผู้ลงคะแนน และmคือจำนวนผู้สมัคร) ดูที่การเพิ่มประสิทธิภาพสูงสุด-ต่ำสุดแบบ Lexicographic

Var-Phragmen สามารถคำนวณได้โดยการแก้โปรแกรมกำลังสองแบบ ผสมจำนวนเต็มหนึ่งโปรแกรมที่มี ตัวแปร O( nm )

วลีลำดับสามารถคำนวณได้ในเวลาพหุนาม การคำนวณอย่างง่ายแสดงให้เห็นว่าเวลาในการทำงานคือ O( kmn ): มีkขั้นตอน (หนึ่งขั้นตอนสำหรับผู้สมัครที่ได้รับเลือกแต่ละคน) ในแต่ละขั้นตอน เราต้องตรวจสอบผู้สมัครทั้งหมดเพื่อดูว่าใครบ้างที่สามารถได้รับการสนับสนุนทางการเงิน และสำหรับผู้สมัครแต่ละคน เราต้องตรวจสอบผู้มีสิทธิเลือกตั้งทั้งหมดเพื่อดูว่าใครบ้างที่สามารถสนับสนุนทางการเงินได้ อย่างไรก็ตาม เพื่อความแม่นยำ เราต้องทำงานกับจำนวนตรรกยะ และขนาดของมันจะเพิ่มขึ้นถึงk log n เนื่องจากการคำนวณในbบิตอาจต้องใช้เวลา O( ) ดังนั้นเวลาในการทำงานทั้งหมดคือ O ( k³mn log²n )

กฎของ Phragmén สำหรับการลงคะแนนแบบจัดอันดับ

กฎ Phragmén มักใช้กับการลงคะแนนแบบอนุมัติ (นั่นคือการลงคะแนนแบบอนุมัติผู้ชนะหลายคน ) แต่ก็มีรูปแบบที่ใช้การลงคะแนนแบบจัดลำดับ (นั่นคือการลงคะแนนแบบจัดลำดับ ผู้ชนะหลายคน ) การปรับปรุง Seq-Phragmen ได้รับการเสนอในปี 1913 โดยคณะกรรมการราชวงศ์ว่าด้วยวิธีการเลือกตั้งตามสัดส่วน วิธีนี้ถูกนำมาใช้ในการเลือกตั้งของสวีเดนสำหรับการจัดสรรที่นั่งภายในพรรคการเมืองตั้งแต่ปี 1921 [ 2 ] : มาตรา 9

ในเวอร์ชันที่ปรับปรุงแล้ว ในแต่ละรอบ ผู้ลงคะแนนแต่ละคนจะลงคะแนนให้เฉพาะผู้สมัครที่เหลืออยู่ที่มีอันดับสูงสุดเท่านั้น และเมื่อผู้สมัครคนใดได้รับเลือก "คะแนนเสียง" 1 หน่วยของเขาควรจะถูกกระจายไปยังผู้สมัครคนอื่นๆ ที่ลงคะแนนให้เขา (เช่น จัดอันดับเขาเป็นอันดับแรก) โดยการแบ่งคะแนนเสียงนี้ควรทำให้คะแนนเสียงสูงสุดของผู้ลงคะแนนแต่ละคนมีค่าน้อยที่สุด

ตัวแปร

การลงคะแนนเสียงของพรรค

สามารถใช้วิธีของ Phragmen สำหรับพรรคการเมืองได้ ผู้ลงคะแนนแต่ละคนสามารถอนุมัติพรรคการเมืองได้หนึ่งพรรคหรือมากกว่า ขั้นตอนยังคงเหมือนเดิม ยกเว้นว่าตอนนี้แต่ละพรรคการเมืองสามารถถูกเลือกได้หลายครั้ง ตั้งแต่ 0 ถึงจำนวนผู้สมัครทั้งหมดในพรรคการเมือง[ 4 ]

การจัดทำงบประมาณแบบมีส่วนร่วม

กฎ Seq-Phragmen ได้รับการปรับให้เข้ากับการตั้งค่าทั่วไปของการจัดทำงบประมาณแบบมีส่วนร่วมเชิงผสมผสาน[ 5 ]

สัดส่วนแบบถดถอยและย้อนกลับ

Jaworski และ Skowron [ 6 ]สร้างคลาสของกฎที่ขยาย seq-Phragmen สำหรับ สัดส่วน แบบก้าวหน้าและถดถอย ตามสัญชาตญาณ:

  • หลักการแบ่งสัดส่วนแบบถดถอยได้มาจากการสมมติว่าผู้มีสิทธิเลือกตั้งที่มีผู้แทนมากกว่าจะได้รับเงินเดือนในอัตราที่ช้ากว่าผู้ที่มีผู้แทนน้อยกว่า
  • หลักการแบ่งสัดส่วนแบบถดถอย (Regressive proportionality) ถูกนำมาใช้โดยการสมมติว่าผู้สมัครที่ได้รับการสนับสนุนจากผู้มีสิทธิเลือกตั้งมากกว่าจะมีค่าใช้จ่ายน้อยกว่าผู้สมัครที่ได้รับการสนับสนุนน้อยกว่า

การใช้วิธีของ Phragmen ในการจัดอันดับทางเลือก

วิธีการ Phragmen แบบลำดับสามารถใช้ไม่เพียงแต่ในการเลือกชุดย่อยเท่านั้น แต่ยังใช้ในการสร้างการจัดอันดับทางเลือกตามลำดับที่เลือกอีกด้วย Brill และ Israel [ 7 ]ขยายวิธีการนี้ไปสู่การจัดอันดับแบบไดนามิกโดยได้รับแรงบันดาลใจจากแอปพลิเคชันถามตอบออนไลน์[ 8 ]พวกเขาตั้งสมมติฐานว่าผู้สมัครบางรายได้รับการเลือกแล้ว และใช้ข้อมูลนี้ในการคำนวณการจัดอันดับ พวกเขาเสนอการปรับเปลี่ยนกฎของ Phragmen สองแบบ:

  • พลวัตของ Phragmen: ในแต่ละขั้นตอน จะวนซ้ำไปตามลำดับของผู้สมัครที่ได้รับการเลือกตั้งแล้ว และแบ่ง "ต้นทุน" ของพวกเขาให้กับผู้สนับสนุน ซึ่งจะสร้าง "หนี้" ที่เป็นไปได้สำหรับผู้ใช้แต่ละคน - ยอดคงเหลือติดลบ การคำนวณหนี้สามารถทำได้ในเวลา O( mn² )โดยที่mคือจำนวนผู้สมัคร และnคือจำนวนผู้ใช้ จากนั้น ผู้ใช้จะเริ่มสะสมเงินตามปกติ โดยผู้ใช้สามารถเริ่มซื้อผู้สมัครใหม่ได้ก็ต่อเมื่อชำระ "หนี้" แล้ว ผู้ใช้จะซื้อผู้สมัครตามลำดับจนกว่าจะคำนวณลำดับใหม่ได้ ลำดับใหม่จะเป็นสัดส่วน การคำนวณลำดับใหม่สามารถทำได้ในเวลาO ( m²n² )
  • Myopic Phragmen: "หนี้" ของผู้ใช้แต่ละคนจะถูกคำนวณเช่นเดียวกับใน Dynamic Phragmen จากนั้น แทนที่จะสร้างการจัดอันดับที่สมบูรณ์โดยการเรียกใช้ Sequential Phragmen ผู้สมัครจะถูกจัดอันดับตามจำนวน "หนี้" ที่พวกเขาจะสร้างให้กับผู้ใช้ กล่าวคือ ผู้สมัครจะถูกจัดอันดับตามความเหมาะสมที่จะได้รับการเลือกตั้งในลำดับถัดไป การจัดอันดับที่ได้นั้นไม่จำเป็นต้องเป็นสัดส่วน (โดยเฉพาะอย่างยิ่ง เมื่อลำดับว่างเปล่า Myopic Phragmen จะสอดคล้องกับการลงคะแนนอนุมัติแบบอรรถประโยชน์นิยม) การคำนวณลำดับใหม่สามารถทำได้ในเวลา O( mn² )

พวกเขาทำการวิเคราะห์คุณสมบัติความสม่ำเสมอและความเป็นธรรมของการปรับตัวเหล่านี้ ทั้งในเชิงทฤษฎีและเชิงประจักษ์

คุณสมบัติ

ความเป็นเนื้อเดียวกัน

สำหรับบัตรลงคะแนนที่เป็นไปได้แต่ละใบbให้v เป็นจำนวนผู้ลงคะแนนที่ลงคะแนนb อย่างแน่นอน (ตัวอย่างเช่น อนุมัติชุดผู้สมัครชุดเดียวกันอย่างแน่นอน) ให้p เป็นเศษส่วนของผู้ลงคะแนนที่ลงคะแนนb อย่างแน่นอน (= v / จำนวนคะแนนเสียงทั้งหมด) วิธีการลงคะแนนเรียกว่าเป็นเอกพันธุ์หากขึ้นอยู่กับเศษส่วนp เท่านั้น ดังนั้นหากจำนวนคะแนนเสียงทั้งหมดถูกคูณด้วยค่าคงที่เดียวกัน วิธีการจะให้ผลลัพธ์เดียวกัน วิธีการของ Phragmén เป็นเอกพันธุ์ในแง่นั้น[ 2 ] : Rem.2.1

ความเป็นอิสระของผู้สมัครที่ไม่ได้รับเลือกตั้ง

หากมีการเพิ่มผู้สมัครจำนวนหนึ่งลงในบัตรเลือกตั้ง แต่ไม่มีผู้สมัครคนใดได้รับเลือก (แม้ว่าจะมีผู้ลงคะแนนให้บางคนก็ตาม) ผลลัพธ์ก็จะไม่เปลี่ยนแปลง[ 2 ] : มาตรา 6 สิ่งนี้ช่วยลดแรงจูงใจในการบิดเบือนเชิงกลยุทธ์อย่างหนึ่ง นั่นคือ การเพิ่มผู้สมัคร "ปลอม" เพื่อดึงดูดคะแนนเสียง

ความสม่ำเสมอ

Seq-Phragmén จัดสรรที่นั่งทีละที่ ดังนั้นจึงเป็นไปตาม คุณสมบัติ ความเป็นเอกภาพของคณะกรรมการ : เมื่อมีการเพิ่มที่นั่งมากขึ้น ชุดของผู้ชนะก็จะเพิ่มขึ้น (ไม่มีผู้ชนะคนใดเสียที่นั่ง) [ 2 ] : มาตรา 5

นอกจากนี้ยังตรงตามเกณฑ์ความเป็นเอกรูป อื่นๆ อีกหลาย ประการ[ 2 ] : มาตรา 14

สำหรับวิธีการลงคะแนนแบบอนุมัติของ Phragmén : หากผู้สมัครCได้รับเลือก และผู้สมัครCได้รับการอนุมัติจากผู้มีสิทธิเลือกตั้งใหม่ที่ลงคะแนนให้Cหรือจากผู้มีสิทธิเลือกตั้งเดิมที่เพิ่มCลงในบัตรเลือกตั้งของตน และไม่มีการเปลี่ยนแปลงอื่นใดเกิดขึ้นCก็ยังคงได้รับเลือก อย่างไรก็ตาม ความสอดคล้องนี้ไม่เป็นจริงสำหรับคู่ของผู้สมัคร แม้ว่าพวกเขาจะปรากฏร่วมกันเสมอ ตัวอย่างเช่น เป็นไปได้ที่ผู้สมัคร C, D จะปรากฏร่วมกันในบัตรเลือกตั้งทั้งหมดและได้รับสองที่นั่ง แต่ถ้ามีการเพิ่มบัตรเลือกตั้งอีกใบสำหรับ C, D พวกเขาจะได้รับที่นั่งร่วมกันเพียงที่นั่งเดียว (ดังนั้นคนใดคนหนึ่งจะเสียที่นั่ง) [ 2 ] : ตัวอย่าง 14.4, 14.5 ในทำนองเดียวกัน ความสอดคล้องนี้ไม่เป็นจริงในรูปแบบที่มีพรรคการเมือง: พรรคการเมืองอาจได้รับการอนุมัติมากขึ้น แต่ยังคงได้รับที่นั่งน้อยลง ตัวอย่างเช่น: [ 4 ]

  • สมมติว่ามี ที่นั่ง k = 3 ที่นั่ง และมีผู้สมัคร 3 คน คือ a, b, c ผลการลงคะแนนคือ 4 เสียงให้ a, 7 เสียงให้ b, 1 เสียงให้ a+b, 16 เสียงให้ a+c, 4 เสียงให้ b+c ดังนั้น คณะกรรมการที่ได้รับเลือกคือ {a, b, a} แต่ถ้าหนึ่งในผู้ลงคะแนน b เห็นชอบกับ a ด้วย (ดังนั้นผลการลงคะแนนจะเป็น 4 เสียงให้ a, 6 เสียงให้ b, 2 เสียงให้ a+b, 16 เสียงให้ a+c, 4 เสียงให้ b+c) แล้ว คณะกรรมการที่ได้รับเลือกคือ {a, c, b} ดังนั้น พรรค a ได้รับการอนุมัติ แต่เสียที่นั่งไปหนึ่งที่นั่ง

สำหรับวิธีการลงคะแนนแบบจัดลำดับของ Phragmén : หากผู้สมัครCได้รับเลือก และต่อมาผู้สมัครCได้รับการเลื่อนขั้นในการลงคะแนนบางส่วน หรือได้รับคะแนนเสียงใหม่ และไม่มีการเปลี่ยนแปลงอื่นใดเกิดขึ้นCก็ยังคงได้รับเลือก อย่างไรก็ตาม หากมีการเปลี่ยนแปลงอื่นเกิดขึ้นพร้อมกันCอาจเสียที่นั่งได้ ตัวอย่างเช่น เป็นไปได้ที่ผู้มีสิทธิเลือกตั้งบางคนเปลี่ยนใจ และแทนที่จะลงคะแนนให้ A และ B พวกเขาลงคะแนนให้ C และ D และการเปลี่ยนแปลงนี้ทำให้ C เสียที่นั่ง[ 2 ] : ตัวอย่าง 13.16

การนำเสนอที่สมเหตุสมผล

กฎของ Sequential Phragmen สอดคล้องกับสัจพจน์ที่เรียกว่าProportional Justified Representation (PJR) [ 3 ]ซึ่งทำให้เป็นหนึ่งในวิธีการเพียงไม่กี่วิธีที่สอดคล้องกับทั้ง PJR และความเป็นเอกรูป

อย่างไรก็ตาม มันไม่เป็นไปตามสัจพจน์ที่แข็งแกร่งกว่าที่เรียกว่าExtended Justified Representation (EJR) ตัวอย่างหนึ่งแสดงไว้ที่นี่: [ 3 ]

  • มีผู้สมัคร 14 คน ได้แก่ a, b, c1, ..., c12 มีตำแหน่งว่าง 12 ตำแหน่ง
  • มีผู้ลงคะแนน 24 คน: สองคนเห็นชอบกับ {a,b,c1}; สองคนเห็นชอบกับ {a,b,c2}; 6 คนเห็นชอบกับ {c1,c2,...,c12}; 5 คนเห็นชอบกับ {c2,c3,...,c12}; 9 คนเห็นชอบกับ {c3,c4,...,c12}
  • Seq-Phragmen เลือก c1,...,c12 ซึ่งขัดกับ EJR สำหรับผู้ลงคะแนนสี่คนที่อนุมัติ {a,b,c1} และ {a,b,c2}: กลุ่มนี้มีโควต้า 2 รายการและมีความสอดคล้องกัน 2 แบบ แต่ไม่มีสมาชิกคนใดมีผู้ชนะที่ได้รับการอนุมัติ 2 คน

ตัวอย่างอื่นแสดงไว้ที่นี่ (สำหรับการตั้งค่าของฝ่ายต่างๆ): [ 9 ]

  • มีพรรคการเมืองผู้สมัคร 3 พรรค และมีที่นั่งให้เลือกตั้ง 10 ที่นั่ง
  • มีผู้ลงคะแนน 10 คน โดยมีชุดการอนุมัติเป็น ab,ab,ab; ac,ac,ac,ac; bc,bc; b
  • Seq-Phragmen เลือก a (ที่เวลา 1/7); จากนั้น b; จากนั้น a,b,a,b,a,b,a,b
  • ผู้ลงคะแนนหมายเลข 1, 2, 3 เห็นชอบผู้สมัครทั้ง 10 คน แต่ผู้ลงคะแนนหมายเลข 4, ..., 10 เห็นชอบเพียง 5 คน อย่างไรก็ตาม กลุ่มผู้ลงคะแนนหมายเลข 4, 5, 6, 7, 8, 9 เห็นพ้องต้องกันในพรรค c ดังนั้น EJR จึงกำหนดว่าอย่างน้อยหนึ่งคนในกลุ่มนี้จะต้องเห็นชอบผู้สมัคร 6 คน ดังนั้นจึงมีการละเมิด EJR (โปรดทราบว่า PJR ไม่ถูกละเมิดสำหรับกลุ่มนี้ เนื่องจากผู้สมัครทั้ง 10 คนได้รับความเห็นชอบจากสมาชิกอย่างน้อยหนึ่งคนในกลุ่ม)

นอกจากนี้ Seq-Phragmen ยังไม่ผ่านสัจพจน์ที่ไม่สอดคล้องกันอีกประการหนึ่งที่เรียกว่าPerfect Representation (PER)

Var-Phragmen ตรงตามมาตรฐาน PER แต่ไม่ตรงตามมาตรฐาน PJR และ EJR (ยกเว้นกรณี L=1)

Leximan-Phragmen ผ่านเกณฑ์ PJR และ PER แต่ยังคงไม่ผ่านเกณฑ์ EJR

ความสม่ำเสมอ

วิธีการของ Phragmén ไม่ตรงตามเกณฑ์ความสอดคล้องยิ่งไปกว่านั้น พวกเขาไม่ได้ละเลยบัตรลงคะแนนทั้งหมด: การเพิ่มผู้ลงคะแนนที่ลงคะแนนให้ผู้สมัครทุกคน (และดังนั้นจึงไม่สนใจโดยสิ้นเชิง) อาจส่งผลต่อผลลัพธ์[ 2 ] : ตัวอย่าง 15.4, 15.6, 15.8, 15.9

กรณีพิเศษ

เมื่อมีที่นั่งว่างเพียงที่เดียว ( k = 1):

  • วิธีการลงคะแนนแบบอนุมัติของ Phragmén ลดทอนลงเหลือเพียงการลงคะแนนแบบอนุมัติซึ่งจะเลือกผู้สมัครที่ได้รับคะแนนอนุมัติมากที่สุดเสมอ
  • วิธีการลงคะแนนแบบจัดลำดับของ Phragmén ลดทอนลงเหลือเพียงการลงคะแนนแบบเสียงข้างมากซึ่งจะเลือกผู้สมัครที่ได้รับคะแนนเสียงมากที่สุดเป็นอันดับแรกเสมอ

อ่านเพิ่มเติม

  • ข้อมูลเพิ่มเติมเกี่ยวกับวิธีการของ Phragmén สามารถดูได้ที่[ 10 ]
  • คุณสมบัติทางคณิตศาสตร์ของวิธีการของ Phragmen เทียบกับวิธีการของ Thiele [ 11 ]
  • วิธีการของ Enestrom และ Phragmen [ 12 ]

การนำไปปฏิบัติและการสาธิต

  • กฎการลงคะแนนบางส่วนของ Phragmén ถูกนำไปใช้ในแพ็กเกจ Python ที่ชื่อ abcvoting
  • คุณสามารถทดลองใช้กฎการลงคะแนนบางส่วนของ Phragmén ได้ทางออนไลน์ที่ เว็บไซต์ https://pref.tools/abcvoting/ pref.tools
  • ทั้งเวอร์ชันแบบง่ายและแบบซับซ้อน[ 13 ] [ 14 ]ถูกนำมาใช้ในโครงสร้างพื้นฐานของสกุลเงินดิจิทัลPolkadot [ 15 ]

การสรุปโดยทั่วไป

Motamed, Soeteman, Rey และ Endriss [ 16 ]นำเสนอ กลไก การปรับสมดุลภาระตามลำดับซึ่งเป็นการขยายกฎของ Phragmen ไปสู่การจัดทำงบประมาณแบบมีส่วนร่วมด้วยทรัพยากรหลายรายการ

ดูเพิ่มเติม

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Phragmen%27s_voting_rules&oldid=1334923710 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ กฎการลงคะแนนของ Phragmen

กฎการลงคะแนนของ Phragménเป็นกฎสำหรับการลงคะแนนแบบผู้ชนะหลายคนกฎเหล่านี้อนุญาตให้ผู้มีสิทธิเลือกตั้งลงคะแนนให้กับผู้สมัครแต่ละคนแทนที่จะเป็นพรรคการเมือง...

พื้นหลัง

ในการลงคะแนนแบบอนุมัติผู้ชนะหลายคน ผู้มีสิทธิเลือกตั้งแต่ละคนสามารถลงคะแนนให้ผู้สมัครได้หนึ่งคนหรือมากกว่า และเป้าหมายคือการเลือกผู้ชนะจำนวนคง ที่ k คน (โดยที่ k อาจเป็นจำนวนสมาชิกสภาผู้แทนราษฎรก็ได้) คำถามคือจะกำหนดชุดของผู้ชนะได้อย่างไร?

กฎของ Phragmén สำหรับการลงคะแนนอนุมัติ

วิธีการของ Phragmén สำหรับบัตรลงคะแนนที่ไม่เรียงลำดับ (อนุมัติ) สามารถนำเสนอได้หลายวิธีที่เทียบเท่ากัน [ 2 ] : มาตรา 3

การปรับสมดุลภาระงาน

ผู้สมัครที่ได้รับเลือกแต่ละคนจะสร้าง "ภาระ" 1 หน่วย ภาระของผู้สมัครจะต้องตกเป็นของผู้มีสิทธิเลือกตั้งที่สนับสนุนเขา เป้าหมายคือการหาคณะกรรมการที่สามารถแบ่งภาระนั้นให้กับผู้มีสิทธิเลือกตั้งได้อย่าง "สมดุล" ที่สุด