Teori Permainan untuk Agen

Teori permainan menyediakan kerangka matematis untuk menganalisis interaksi strategis antar agen rasional, memprediksi bagaimana pembuat keputusan yang mementingkan diri sendiri berperilaku ketika hasil setiap agen bergantung pada pilihan agen lain.

Definition

Teori permainan mempelajari situasi di mana beberapa agen rasional masing-masing memilih tindakan yang imbalannya bergantung pada pilihan semua agen, dan mengkarakterisasi perilaku bersama yang stabil atau rasional melalui konsep solusi seperti ekuilibrium.

Scope

Topik ini mencakup dasar-dasar teori permainan yang digunakan dalam AI multi-agen: permainan bentuk normal dan bentuk ekstensif, strategi dominan, ekuilibrium Nash dan keberadaannya, strategi campuran, dan contoh-contoh kunci seperti dilema tahanan dan permainan jumlah nol; bersama dengan pertanyaan algoritmik tentang penghitungan ekuilibrium. Ini membahas bagaimana agen bernalar tentang satu sama lain dan perilaku bersama apa yang stabil. Rekayasa aturan interaksi diperlakukan di bawah desain mekanisme, dan belajar bermain game termasuk dalam subbidang pembelajaran mesin.

Core questions

• Bagaimana interaksi strategis direpresentasikan sebagai permainan dalam bentuk normal atau ekstensif?
• Konsep solusi apa (strategi dominan, ekuilibrium Nash) yang memprediksi bagaimana agen rasional berperilaku?
• Kapan ekuilibrium dijamin ada, mungkin dalam strategi campuran?
• Seberapa sulit menghitung ekuilibrium, dan bagaimana ini memengaruhi penggunaannya oleh agen?

Key concepts

• permainan bentuk normal dan bentuk ekstensif
• imbalan dan strategi
• strategi dominan
• ekuilibrium Nash
• strategi campuran
• permainan jumlah nol dan minimaks
• dilema tahanan
• penghitungan ekuilibrium

Key theories

Ekuilibrium Nash

Ekuilibrium Nash adalah profil strategi di mana tidak ada agen yang dapat meningkatkan imbalannya dengan secara sepihak mengubah strateginya sendiri; Nash membuktikan bahwa setiap permainan terbatas memiliki setidaknya satu ekuilibrium semacam itu, mungkin dalam strategi campuran.

Minimaks dalam permainan jumlah nol

Dalam permainan jumlah nol dua pemain, teorema minimaks von Neumann menjamin nilai dan strategi optimal (mungkin acak) untuk kedua pemain, menghubungkan teori permainan dengan pengambilan keputusan yang bersifat antagonis.

Strategi dominan dan dilema

Menganalisis permainan melalui strategi dominan menjelaskan hasil seperti dilema tahanan, di mana pilihan rasional individu mengarah pada hasil yang secara kolektif lebih buruk, menggambarkan ketegangan antara rasionalitas individu dan kelompok.

Clinical relevance

Analisis teori permainan menginformasikan desain lelang dan pasar, strategi keamanan dan patroli, perutean dan kemacetan jaringan, serta negosiasi otomatis, dengan memprediksi bagaimana agen strategis akan bertindak dan mengidentifikasi hasil yang stabil dalam pengaturan kompetitif.

History

Teori permainan didirikan oleh von Neumann dan Morgenstern (1944) dan diperluas oleh konsep ekuilibrium Nash (1950). Ini menjadi pusat ekonomi dan, sejak tahun 1990-an, untuk AI dan ilmu komputer melalui teori permainan algoritmik, yang mempelajari kompleksitas komputasi ekuilibrium dan penggunaannya dalam sistem multi-agen.

Key figures

• John von Neumann
• Oskar Morgenstern
• John F. Nash
• Yoav Shoham
• Kevin Leyton-Brown

Seminal works

• nash1950
• vonneumann1944
• shoham2009

Frequently asked questions

Apa itu ekuilibrium Nash?

Ekuilibrium Nash adalah kombinasi strategi, satu per agen, sedemikian rupa sehingga tidak ada agen tunggal yang dapat berbuat lebih baik dengan hanya mengubah strateginya sendiri sementara agen lain mempertahankan strategi mereka. Ini menangkap gagasan perilaku rasional yang stabil dan saling konsisten.

Mengapa dilema tahanan penting bagi agen AI?

Dilema tahanan menunjukkan bahwa agen yang bertindak demi kepentingan rasional mereka sendiri dapat mencapai hasil yang lebih buruk bagi mereka semua daripada jika mereka bekerja sama. Ini menyoroti mengapa merancang insentif dan mekanisme koordinasi penting saat membangun sistem agen yang mementingkan diri sendiri.