เกมการวางตำแหน่งที่ไม่เป็นธรรม
เกมตำแหน่งที่มีอคติ[ 1 ] [ 2 ] : 27–42เป็นรูปแบบหนึ่งของเกมตำแหน่งเช่นเดียวกับเกมตำแหน่งส่วนใหญ่ เกมนี้อธิบายโดยชุดของตำแหน่ง/จุด/องค์ประกอบ () และตระกูลของเซตย่อย (ซึ่งโดยทั่วไปเรียกว่าชุดที่ชนะ เกมนี้เล่นโดยผู้เล่นสองคนที่ผลัดกันเลือกองค์ประกอบจนกว่าองค์ประกอบทั้งหมดจะถูกเลือก ในขณะที่ในเกมมาตรฐาน ผู้เล่นแต่ละคนจะเลือกองค์ประกอบหนึ่งชิ้นต่อตา แต่ในเกมที่ไม่เป็นธรรม ผู้เล่นแต่ละคนจะเลือกองค์ประกอบจำนวนไม่เท่ากัน
กล่าวอย่างเป็นทางการมากขึ้น สำหรับจำนวนเต็มบวกสองจำนวนใดๆpและqเกมแบบ (p:q)-positional คือเกมที่ผู้เล่นคนแรกเลือก องค์ประกอบ pตัวต่อตา และผู้เล่นคนที่สองเลือก องค์ประกอบ qตัวต่อตา
คำถามสำคัญที่น่าสนใจเกี่ยวกับเกมที่มีอคติเชิงตำแหน่งคือระดับอคติที่เป็นเกณฑ์ นั้นคืออะไร กล่าวคือ ระดับอคติที่ทำให้พลังแห่งชัยชนะเปลี่ยนจากผู้เล่นคนหนึ่งไปเป็นผู้เล่นอีกคนหนึ่งคืออะไร
ตัวอย่าง
ยกตัวอย่างเช่นเกมสามเหลี่ยมในเกมนี้ องค์ประกอบทั้งหมดคือขอบของกราฟสมบูรณ์ที่มีnจุดยอด และเซตที่ชนะคือสามเหลี่ยมทั้งหมด (=คลิกที่มี 3 จุดยอด) สมมติว่าเราเล่นเกมนี้ในรูปแบบเกมผู้สร้าง-ผู้ทำลาย กล่าวคือ เป้าหมายของผู้สร้าง (ผู้เล่นคนแรก) คือการเลือกสามเหลี่ยม และเป้าหมายของผู้ทำลาย (ผู้เล่นคนที่สอง) คือการป้องกันไม่ให้ผู้สร้างเลือกสามเหลี่ยม จากการวิเคราะห์กรณีอย่างง่าย สามารถพิสูจน์ได้ว่าผู้สร้างมีกลยุทธ์ที่ชนะเมื่อใดก็ตามที่nมีค่าอย่างน้อย 6 ดังนั้นจึงน่าสนใจที่จะถามว่าข้อได้เปรียบนี้สามารถเปลี่ยนแปลงได้หรือไม่โดยการให้ผู้ทำลายเลือกองค์ประกอบมากกว่า 1 รายการต่อตา
แท้จริงแล้วสามารถพิสูจน์ได้ว่า: [ 1 ]
- สำหรับทุกๆMaker ชนะเกมสามเหลี่ยม (1: q ) บน จุดยอดn จุด
- สำหรับทุกๆเบรกเกอร์ชนะเกมสามเหลี่ยม (1: q ) บน จุดยอดn จุด
เงื่อนไขแห่งชัยชนะสำหรับเบรกเกอร์
ในเกม Maker-Breaker ที่ไม่มีอคติ ทฤษฎีบท Erdos-Selfridge ให้เงื่อนไขการชนะสำหรับ Breakerเงื่อนไขนี้สามารถขยายไปสู่เกมที่มีอคติได้ดังนี้: [ 3 ] [ 2 ] : 30–32
- ถ้าดังนั้น Breaker จึงมีกลยุทธ์ที่ชนะในเกม (p:q) เมื่อเล่นก่อน
- ถ้าดังนั้น Breaker จึงมีกลยุทธ์ที่ชนะในเกม (p:q) แม้ว่าจะเล่นเป็นฝ่ายที่สองก็ตาม
กลยุทธ์นี้ใช้ฟังก์ชันศักยภาพซึ่งเป็นการขยายฟังก์ชันของ Erdos-Selfridge ศักยภาพของเซตที่ชนะ (ไม่แตก) Eที่มีองค์ประกอบที่ยังไม่ได้ถูกเลือก | E | ตัว ถูกกำหนดดังนี้ถ้า Maker ชนะเกม แสดงว่ามีเซตEที่มี | E |=0 ดังนั้นค่าศักยภาพของเซตนี้คือ 1 ดังนั้น เพื่อพิสูจน์ว่า Breaker ชนะ จึงเพียงพอที่จะพิสูจน์ว่าผลรวมศักยภาพสุดท้ายน้อยกว่า 1 อันที่จริง ตามสมมติฐาน ผลรวมศักยภาพในตาแรกของ Breaker น้อยกว่า 1 และถ้า Breaker เลือกองค์ประกอบที่ทำให้ค่าศักยภาพลดลงสูงสุดเสมอ ก็สามารถแสดงได้ว่าผลรวมศักยภาพจะลดลงอย่างอ่อนๆ เสมอ
เมื่อแต่ละเซ็ตที่ชนะมีสำหรับค่าk ที่กำหนดไว้ เงื่อนไขการชนะของ Breaker จะลดรูปเหลือดังนี้: (เมื่อเล่นครั้งแรก) หรือ(เมื่อเล่นเป็นคนที่สอง) เงื่อนไขนี้ค่อนข้างเข้มงวด: มีเซตตระกูลk -uniform ที่มีชุดที่ผู้สร้างชนะ[ 4 ]
เงื่อนไขแห่งชัยชนะสำหรับเมกเกอร์
ในเกม Maker-Breaker ที่ไม่มีอคติ ทฤษฎีบทของ Beck ให้เงื่อนไขการชนะสำหรับฝ่าย Makerโดยใช้ระดับคู่ของไฮเปอร์กราฟ ซึ่งแสดงด้วยเงื่อนไขนี้สามารถนำไปใช้กับเกมที่มีอคติได้ดังนี้: [ 3 ]
ถ้าดังนั้น Maker จึงมีกลยุทธ์ที่ชนะในเกม (p:q) เมื่อเล่นก่อน
เงื่อนไขแห่งชัยชนะสำหรับ Avoider
ในเกม Avoider-Enforcer ที่มีอคติ เงื่อนไขต่อไปนี้รับประกันว่า Avoider มีกลยุทธ์ที่ชนะ: [ 2 ] : 47–49
- ถ้าจากนั้น Avoider จะชนะเกม (p:q) เมื่อเล่นก่อน ภายใต้กฎทั้งแบบเข้มงวดและแบบโมโนโทนิก นี่เกือบจะพอดี: มีตระกูลเกม (p:q) ที่ไม่มีที่สิ้นสุดซึ่งนิพจน์นี้มีค่ามากกว่า 1 เล็กน้อยและ Enforcer ชนะ[ 5 ]โดยเฉพาะอย่างยิ่งในเกมที่ไม่ลำเอียง เงื่อนไขจะกลายเป็นถ้ากราฟเป็น แบบ k -uniform เงื่อนไขจะกลายเป็นเป็นเรื่องน่าทึ่งที่เงื่อนไขนี้ไม่ขึ้นอยู่กับค่า qเลย
- ถ้าเซตที่ชนะแต่ละเซตมีสมาชิกไม่เกิน k ตัว และ จากนั้น Avoider จะชนะเกม (p:q) เมื่อเล่นก่อน[ 6 ]