digilib@itb.ac.id +62 812 2508 8800

Di Institut Teknologi Bandung (ITB), mahasiswa baru tidak langsung diterima ke program studi (prodi), melainkan melalui masa Tahap Persiapan Bersama (TPB) di fakultas terlebih dahulu selama satu tahun pertama. Pada akhir masa TPB, akan dilakukan seleksi prodi yang menentukan prodi tiap mahasiswa. Seleksi prodi dapat dimodelkan menjadi suatu permainan dengan teori permainan, dan keidealan hasil seleksi dapat dilihat melalui model permainan tersebut. Pemain dalam permainan ini adalah prodi pada Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA), dengan sifat kooperatif. Setiap prodi memiliki fungsi payoff yang berkaitan dengan nilai korelasi antara mahasiswa dengan prodi berdasarkan kriteria seleksi. Keidealan hasil seleksi dapat dilihat dari nilai payoff tiap prodi, dimana hasil seleksi dikatakan ideal apabila jumlahan nilai payoff semua prodi maksimal. Permainan seleksi dapat dimodelkan kembali menjadi suatu graf bipartit lengkap berbobot, dengan partisi pada graf tersebut berkorespondensi dengan himpunan mahasiswa dan himpunan prodi. Bobot tiap sisi berkorespondensi dengan nilai korelasi antara mahasiswa dan prodi yang dihubungkan oleh sisi tersebut. Graf tersebut dapat dimodifikasi dengan menduplikasikan titik prodi sehingga banyaknya titik yang dimiliki suatu prodi sama dengan kuota maksimum prodi tersebut, kemudian menambahkan titik mahasiswa dengan bobot nol pada setiap sisinya sehingga banyaknya titik mahasiswa sama dengan banyaknya titik prodi. Pada graf hasil modifikasi tersebut, dapat dicari suatu maximumweight perfect matching dengan menggunakan Hungarian algorithm. Matching yang diperoleh menunjukkan hasil seleksi yang ideal.