Skip to content
Kembali ke hasil pencarian

Siklus Perdagangan Teratas

Diperkenalkan oleh
Lloyd Shapley, Herbert Scarf
Tahun
1974
Jenis
algorithm
Keluarga
Game-theoretic

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Siklus Perdagangan Teratas (TTC) adalah algoritma untuk mengalokasikan barang yang tidak dapat dibagi kepada agen sedemikian rupa sehingga alokasi tersebut efisien Pareto dan rasional secara individual. Dikembangkan oleh Lloyd Shapley dan Herbert Scarf pada tahun 1974, algoritma ini mengidentifikasi siklus perdagangan dalam digraf preferensi, melaksanakan perdagangan tersebut, dan mengulang secara iteratif hingga tidak ada lagi perdagangan yang menguntungkan.

TTC banyak digunakan dalam pertukaran ginjal dan alokasi perumahan karena efisiensinya dan kesederhanaan implementasinya.

Intuisi di balik metode

Bayangkan sekelompok orang masing-masing memiliki satu rumah, dan setiap orang memberi peringkat semua rumah berdasarkan preferensi. Algoritma TTC bertanya: siapa favorit saya? Tunjuklah mereka. Sekarang lihat siapa yang menunjuk Anda. Jika itu adalah siklus (A menunjuk B, B menunjuk C, C menunjuk A), laksanakan perdagangan tersebut—A mendapatkan rumah B, B mendapatkan rumah C, C mendapatkan rumah A. Semua orang dalam siklus senang karena mereka mendapatkan rumah seseorang yang mereka sukai daripada rumah mereka saat ini. Hapus siklus tersebut dan ulangi sampai tidak ada lagi siklus. Hasilnya efisien karena semua perdagangan yang menguntungkan telah dilakukan.

Sejarah

Lloyd Shapley dan Herbert Scarf memperkenalkan algoritma Siklus Perdagangan Teratas pada tahun 1974 sebagai solusi untuk masalah pasar perumahan, membuktikan bahwa algoritma ini menghasilkan alokasi efisien Pareto yang unik. Algoritma ini memperoleh kepentingan praktis melalui karya Alvin Roth tentang pertukaran ginjal, di mana algoritma ini menjadi pusat untuk mencocokkan donor dan penerima. Hadiah Nobel 2012 untuk Roth memvalidasi pentingnya TTC untuk desain pasar dunia nyata, khususnya dalam transplantasi organ.

Kapan digunakan

Terapkan TTC saat mengalokasikan barang yang tidak dapat dibagi (rumah, organ, kursi sekolah) di antara agen dengan preferensi ketat atas bundel. Gunakan ketika efisiensi Pareto sangat penting dan tidak ada transfer moneter yang tersedia atau diinginkan. TTC ideal untuk pasar terdesentralisasi di mana agen dapat mengidentifikasi perdagangan yang menguntungkan secara lokal. Bekerja paling baik ketika agen memiliki informasi preferensi yang lengkap dan asiklik.

Batasan dan pertimbangan

  • Membutuhkan urutan preferensi yang ketat tanpa indiferensi; perluasan ke preferensi lemah rumit
  • Tidak tahan koalisi: koalisi agen dapat salah merepresentasikan preferensi untuk meningkatkan hasil kolektif
  • Sensitivitas terhadap siklus preferensi: tidak adanya siklus dapat menyebabkan beberapa agen tidak diperdagangkan
  • Terbatas pada pencocokan tanpa transfer moneter; tidak efisien untuk penilaian heterogen

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Efisien Pareto: tidak ada perbaikan bebas perdagangan yang ada; semua pertukaran yang saling menguntungkan dilaksanakan
  • Rasional secara individual: setiap agen secara lemah lebih menyukai alokasi akhir daripada kepemilikan awal mereka
  • Tahan strategi untuk pengaturan tertentu: agen tidak dapat meningkatkan hasil dengan melaporkan preferensi yang salah
  • Efisien secara komputasi: waktu polinomial dengan implementasi sederhana
  • Transparan: agen memahami bagaimana pilihan yang mereka tunjuk mengarah pada alokasi

Penerapan

  • Pertukaran ginjal: mencocokkan donor dan penerima organ untuk meningkatkan kompatibilitas transplantasi melalui pertukaran multi-pihak
  • Alokasi perumahan: menugaskan kamar asrama universitas atau unit perumahan umum secara efisien
  • Pilihan sekolah: menugaskan siswa ke sekolah dengan batasan kapasitas dan keragaman preferensi
  • Pertukaran lobus hati: memfasilitasi pertukaran donasi berpasangan untuk transplantasi hati donor hidup
  • Pertukaran furnitur dan barang: mengatur pertukaran barter yang efisien di platform berbagi komunitas

Cara kerjanya

Cara kerjanya

1

Buat graf berarah di mana setiap agen menunjuk agen yang paling mereka sukai di antara mereka yang masih ada di pasar.

2

Temukan semua siklus dalam digraf (urutan di mana A menunjuk B, B menunjuk C, ..., kembali ke A).

3

Untuk setiap siklus yang teridentifikasi, laksanakan perdagangan: setiap agen menerima kepemilikan agen yang mereka tunjuk.

4

Hapus agen yang diperdagangkan dan kepemilikan mereka dari pasar. Rekonstruksi digraf preferensi di antara agen yang tersisa dan ulangi sampai tidak ada lagi siklus.

Kesalahan umum

  • Mencampuradukkan efisiensi Pareto dengan keadilan atau kesetaraan; TTC memaksimalkan efisiensi tetapi bukan kesetaraan hasil
  • Mengasumsikan ketahanan strategi di semua pengaturan; TTC hanya jujur dalam konteks tertentu (misalnya, pasar perumahan, bukan pertukaran ginjal dengan prioritas)
  • Mengabaikan bahwa algoritma berakhir ketika tidak ada lagi siklus yang menguntungkan, berpotensi meninggalkan agen tidak cocok
  • Melupakan bahwa TTC membutuhkan preferensi yang ketat tanpa indiferensi; menerapkannya dengan preferensi lemah membutuhkan perluasan

Pertanyaan yang sering diajukan

Mengapa efisiensi Pareto penting dalam alokasi sumber daya?

Efisiensi Pareto memastikan tidak ada agen yang dapat dibuat lebih baik tanpa membuat agen lain lebih buruk. Ini adalah persyaratan minimal untuk alokasi yang 'baik'; melanggarnya berarti sumber daya terbuang dan dapat dialokasikan kembali untuk menguntungkan seseorang.

Bisakah TTC menghasilkan beberapa alokasi yang berbeda?

Tidak. Algoritma TTC, dengan digraf preferensi uniknya, menghasilkan alokasi efisien Pareto yang unik. Jalur menuju alokasi tersebut (urutan identifikasi siklus dan pelaksanaan perdagangan) mungkin bervariasi, tetapi hasil akhirnya selalu sama.

Bagaimana TTC dimodifikasi untuk pertukaran ginjal ketika tidak semua pasangan donor-penerima kompatibel?

Dalam pertukaran ginjal, digraf preferensi dibangun hanya di atas pasangan yang kompatibel. Algoritma kemudian mengidentifikasi siklus dan rantai pertukaran di antara agen yang kompatibel, memperluas TTC asli untuk memperhitungkan kendala biologis.

Metode terkait

Sumber

  1. Shapley, L. S., & Scarf, H. (1974). On cores and indivisibility. Journal of Mathematical Economics, 1(1), 23-37.

    Buka referensi DOI
    Disalin.
  2. Roth, A. E., Sönmez, T., & Ünver, M. U. (2008). Efficient kidney exchange: Coincidence of wants in markets with compatibility. American Economic Review, 97(3), 828-851.

    Buka referensi DOI
    Disalin.