İçeriğe atla
Arama sonuçlarına dön

En İyi Alım Döngüleri

Ortaya koyan
Lloyd Shapley, Herbert Scarf
Yıl
1974
Tür
algorithm
Aile
Game-theoretic

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

En İyi Alım Döngüleri (EAD) (İng.

Top Trading Cycles - TTC), bölünemez malların aracılara, Pareto verimliliği ve bireysel rasyonellik sağlayacak şekilde tahsis edilmesi için geliştirilmiş bir algoritmadır. Lloyd Shapley ve Herbert Scarf tarafından 1974'te geliştirilen algoritma, bir tercih yönlü çizgedeki alım döngülerini belirler, bu alımları gerçekleştirir ve daha fazla alımın faydalı olmadığı duruma kadar tekrarlar. EAD, verimliliği ve uygulama basitliği nedeniyle böbrek değişimi ve konut tahsisinde yaygın olarak kullanılmaktadır.

Yöntemin mantığı

Her birinin bir ev sahibi olduğu ve her kişinin tüm evleri tercih sırasına göre derecelendirdiği bir grup insan hayal edin. EAD algoritması şunu sorar: en sevdiğim kim? Ona işaret edin. Şimdi size kimin işaret ettiğine bakın. Eğer bu bir döngüyse (A, B'yi işaret ediyor, B, C'yi işaret ediyor, C, A'yı işaret ediyor), bu alımları gerçekleştirin—A, B'nin evini alır, B, C'nin evini alır, C, A'nın evini alır. Döngüdeki herkes mutludur çünkü mevcut evlerinden daha çok tercih ettikleri birinin evini almışlardır. Döngüyü kaldırın ve daha fazla döngü kalmayana kadar tekrarlayın. Sonuç verimlidir çünkü tüm faydalı alımlar yapılmıştır.

Tarih

Lloyd Shapley ve Herbert Scarf, 1974'te En İyi Alım Döngüleri algoritmasını konut piyasası sorununa bir çözüm olarak tanıttılar ve benzersiz Pareto-verimli tahsisler sağladığını kanıtladılar. Algoritma, Alvin Roth'un böbrek değişimi üzerine yaptığı çalışmalarla pratik önem kazandı ve burada donör ile alıcı eşleştirmesinde merkezi bir rol oynadı. Roth'a verilen 2012 Nobel Ödülü, özellikle organ nakli alanında, gerçek dünya piyasa tasarımı için EAD'nin önemini doğruladı.

Ne zaman kullanılır?

Bölünemez malların (evler, organlar, okul sıraları) aracılar arasında, demetler üzerindeki katı tercihlerle tahsis edilmesi durumunda EAD'yi uygulayın. Pareto verimliliğinin esas olduğu ve parasal transferlerin mevcut olmadığı veya arzu edilmediği durumlarda kullanın. EAD, aracılarının faydalı alımları yerel olarak belirleyebildiği merkezi olmayan piyasalar için idealdir. Aracılar tam, döngüsüz tercih bilgisine sahip olduğunda en iyi sonucu verir.

Sınırlar ve dikkat edilmesi gerekenler

  • Belirsizlik olmaksızın katı tercih sıralamaları gerektirir; zayıf tercihlere yönelik uzantılar karmaşıktır
  • Koalisyonlara karşı korumalı değil: aracılardan oluşan koalisyonlar kolektif sonucu iyileştirmek için tercihleri yanlış beyan edebilir
  • Tercih döngülerine duyarlılık: döngülerin yokluğu bazı aracılarının takas edilmeden kalmasına neden olabilir
  • Parasal transferler olmaksızın eşleştirmeyle sınırlı; heterojen değerlemeler için verimsiz

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • Pareto verimli: takassız iyileştirmeler mevcut değil; tüm karşılıklı faydalı takaslar gerçekleştirildi
  • Bireysel rasyonel: her temsilci nihai tahsisi başlangıç varlığına göre zayıfça tercih eder
  • Belirli durumlarda stratejiye dayanıklı: aracılar tercihleri yanlış bildirerek iyileştiremez
  • Hesaplama açısından verimli: basit uygulamayla polinom zamanda
  • Şeffaf: aracılar işaret ettikleri seçimin tahsise nasıl yol açtığını anlar

Uygulama alanları

  • Böbrek değişimi: çok taraflı takaslar yoluyla nakil uyumluluğunu artırmak için organ donörleri ve alıcılarını eşleştirme
  • Konut tahsisi: üniversite yurt odalarını veya kamu konut birimlerini verimli bir şekilde atama
  • Okul seçimi: kapasite kısıtlamaları ve tercih çeşitliliği olan öğrencileri okullara atama
  • Karaciğer lobu değişimi: canlı donör karaciğer nakli için eşleştirilmiş donasyon değişimlerini kolaylaştırma
  • Mobilya ve mal takasları: topluluk paylaşım platformlarında verimli barter takasları düzenleme

Nasıl çalışır?

Nasıl çalışır?

1

Her temsilcinin piyasada kalanlar arasından en çok tercih ettiği temsilciyi işaret ettiği yönlü bir çizge oluşturun.

2

Çizgedeki tüm döngüleri bulun (A'nın B'yi işaret ettiği, B'nin C'yi işaret ettiği, ..., A'ya geri döndüğü diziler).

3

Belirlenen her döngü için alımları gerçekleştirin: her temsilci, işaret ettiği temsilcinin varlığını alır.

4

Alım yapılan temsilcileri ve varlıklarını piyasadan kaldırın. Kalan temsilciler arasındaki tercih çizgesini yeniden oluşturun ve daha fazla döngü kalmayana kadar tekrarlayın.

Sık yapılan hatalar

  • Pareto verimliliğini adalet veya hakkaniyetle karıştırmak; EAD verimliliği en üst düzeye çıkarır ancak sonuçların eşitliğini sağlamaz
  • Tüm durumlarda stratejiye dayanıklılık varsaymak; EAD yalnızca belirli bağlamlarda (örneğin, konut piyasaları, önceliklendirmeli böbrek değişimi değil) doğrudur
  • Algoritmanın daha fazla karlı döngü kalmadığında sonlandığını göz ardı etmek, potansiyel olarak aracılar eşleşmeden kalabilir
  • EAD'nin belirsizlik olmaksızın katı tercihler gerektirdiğini unutmak; zayıf tercihlerle uygulandığında uzantı gerektirir

Sık sorulan sorular

Kaynak tahsisinde Pareto verimliliği neden önemlidir?

Pareto verimliliği, başka birini kötüleştirmeden kimsenin daha iyi duruma getirilememesini sağlar. 'İyi' bir tahsis için asgari bir gerekliliktir; bunu ihlal etmek, kaynakların boşa harcandığı ve birini faydalandırmak üzere yeniden tahsis edilebileceği anlamına gelir.

EAD birden fazla farklı tahsis üretebilir mi?

Hayır. EAD algoritması, benzersiz tercih yönlü çizgesiyle benzersiz bir Pareto-verimli tahsis üretir. O tahsise giden yol (döngü belirleme ve alım gerçekleştirme sırası) değişebilir, ancak nihai sonuç her zaman aynıdır.

Tüm donör-alıcı çiftlerinin uyumlu olmadığı böbrek değişimi için EAD nasıl değiştirilir?

Böbrek değişiminde, tercih yönlü çizge yalnızca uyumlu çiftler üzerinden oluşturulur. Algoritma daha sonra uyumlu aracılar arasındaki döngüleri ve zincir takasları belirler, orijinal EAD'yi biyolojik kısıtlamaları hesaba katacak şekilde genişletir.

İlgili yöntemler

Kaynaklar

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

    DOI kaynağını aç
    Kopyalandı.
  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.

    DOI kaynağını aç
    Kopyalandı.