Persoalan pertemuan

Dilema pertemuan bisa digambarkan sebagai berikut:

Dua orang berjanji temu di sebuah taman yang belum pernah mereka kunjungi. Mereka datang sendiri dan baru tahu bahwa tamannya sangat besar. Mereka pun kesulitan bertemu satu sama lain. Dalam situasi seperti ini, masing-masing dari mereka harus memilih antara menunggu di suatu tempat supaya ditemukan orang lain atau mencari orang lain yang mungkin sudah menunggu di suatu tempat.

Apabila mereka berdua memilih menunggu, mereka tidak akan pernah bertemu. Apabila mereka memilih mencari, mereka bisa saja bertemu atau tidak bertemu. Apabila satu orang memilih menunggu dan satu lagi berjalan, mereka pada akhirnya akan bertemu; dalam praktiknya, proses mencari seperti ini memakan waktu yang sangat lama. Persoalannya adalah: apa strategi yang perlu mereka ambil untuk memaksimalkan peluang bertemu?

Contoh persoalan seperti ini dikenal dengan istilah persoalan pertemuan. Persoalan ini pertama kali diperkenalkan secara tidak formal oleh Steve Alpern pada tahun 1976.. Ia membahas lebih lanjut persoalan ini secara formal pada tahun 1995. Sejak itu, banyak peneliti yang mendalami permasalahan ini.. Persoalan pertemuan simetris yang disimulasikan di n lokasi tertentu (kadang disebut Mozart Cafe Rendezvous Problem). ternyata sangat sulit diselesaikan. Pada tahun 1990, Richard Weber dan Eddie Anderson memperkirakan strategi yang optimal.. Perkiraan yang dibuktikan Weber adalah n = 3.. Ini merupakan persoalan pertemuan simetris non-trivial pertama yang selesai sepenuhnya. Ingat bahwa persoalan pertemuan asimetris memiliki satu solusi optimal yang sederhana: satu pihak menunggu di lokasi awal dan pihak lain mencarinya menggunakan permutasi lokasi acak.

Selain dalam teori, dilema janji temu juga diterapkan di dunia nyata, misalnya di bidang sinkronisasi, rancangan sistem operasi, penelitian operasi, dan bahkan perencanaan operasi pencarian dan penyelamatan.

 Persoalan pertemuan deterministik 

Persoalan pertemuan deterministik adalah varian dilema pertemuan. Para pihak atau robot harus menemukan satu sama lain dengan mengikuti urutan instruksi yang deterministik. Meski setiap robot mengikuti urutan instruksi yang sama, sebuah label unik di setiap robot digunakan untuk mencegah kemiripan.

 Lihat pula 
 Permainan koordinasi
 Persoalan makan-makan pemikir
 Algoritma probabilistik
 Permainan pencarian
 Persoalan tukang cukur tidur
 Superrasionalitas
 Pemecahan simetri

 Referensi 

Kategori:Permainan kerja sama