Bilgisayar alanında çalışan bir şair, oyun teorisinin temel sorununu ortaya koyuyor
Constantinos Daskalakis, 2018 Rolf Nevanlinna Ödülü'nü kazandı. | Resim kaynağı: Cassandra Klos / Quanta Magazine
Bilgisayardaki bir sorunu çözmek ne kadar sürer?
Bu görünüşte zararsız soru genel olarak cevaplanamaz. Ancak, içinde Hesaplamalı karmaşıklık teorisi Çekirdek. Bu alandaki araştırmalar derinlemesine matematik ve mantığa dayanmaktadır ve bilgisayarlar anlamak için kullanılabilir. Etkili çözüm karşı Çözemiyorum Bu iki konu arasındaki sınır.
Hesaplamalı karmaşıklık teorisi, bilgisayar biliminin en dinamik ve yaratıcı dallarından biridir ve Constantinos Daskalakis Bu alandaki en parlak yeni yıldızlardan biridir. Onun çalışması, oyun teorisi, piyasalar, müzayedeler ve diğer ekonomik yapılarda bir dizi temel problemin hesaplama karmaşıklığına ilişkin anlayışımızı değiştirdi. Daskalakis'in kapsamlı merakı, teknik ustalığı ve derin teorik içgörüsü, bu konulara yeni bir bakış açısı sağlamasına olanak tanır.
Nash dengesi ve hesaplama karmaşıklığı
İlk olağanüstü başarısı, oyun teorisi ve bilgisayar bilimi arasındaki sınırda yer alan doktora tezinden geldi. Oyun teorisi, çatışma, rekabet veya işbirliği durumlarında rasyonel konuların (bireyler, ticari kuruluşlar, devlet daireleri vb. Olabilir) etkileşimini simüle eder.
Oyun teorisinin temel bir kavramı Nash Dengesi . Bir oyundaki her konu mümkün olan en iyi stratejiyi benimser ve diğer konuların stratejilerini hesaba katarsa, hiç kimse stratejiyi değiştirme motivasyonuna sahip olmazsa, oyun ulaşacaktır. Nash dengesi. Matematikçi John Nash (John F. Nash). 1950'de tüm oyunların Nash dengesine ulaşacağını kanıtladı. Bu sonucun ekonomi üzerinde derin bir etkisi vardır ve Nash, 1994'te Nobel Ekonomi Ödülü'nü kazandı.
Ana yapı, kendi stratejilerini optimize ederek nihayet Nash dengesine ulaşır. | Resim kaynağı: ICM
Oyun teorisinin uygulaması ekonomi alanıyla sınırlı değildir, uluslararası ilişkiler, biyoloji ve diğer alanlarda geniş bir uygulama alanına sahiptir. Açıkçası, deneğin benimseyebileceği stratejileri tahmin etmek için Nash dengesini etkili bir şekilde hesaplayabilmek çok yararlıdır. Bu nedenle, Nash teoremini kanıtladıktan kısa bir süre sonra, uzun araştırmalar başladı ve araştırmacılar Nash dengesini hesaplamak için bir algoritma geliştirdiler. Bununla birlikte, hiçbir algoritma verimli değildir ve hatta bazılarının 21. yüzyılın başına kadar etkisiz olduğu kanıtlanmıştır.
İnsanlar Nash dengesini hesaplamanın çözülmesi zor bir problem olabileceğinden şüphelenmeye başladılar. Eğer bu sorunu çözmek zorsa, stratejik ajanların - yani sınırlı beyinleri olan insanların - bu dengeyi her zaman bulmasını beklemek için hiçbir neden yoktur. Böyle bir sonuç, insanların Nash dengesinin insan davranışını ne ölçüde öngörebileceğine ilişkin beklentilerini zayıflatacaktır.
Hesaplamalı çözülebilirlik sorunu meşhurdur " P ve NP Genellikle "paradigma" bağlamında görünür. "P ve NP" problemi, 1970'lerde hızlı bir şekilde hesaplama karmaşıklığı teorisinin ana teması haline geldi. Genel olarak, P, bilgisayarlar tarafından kolayca çözülebilen bir problem türünü temsil eder (polinom zamanda) , Problemin cevabını çözmek için etkili bir algoritma olduğu anlamına gelir.Aksine, NP kategorisi, bilgisayarların çözmesi zor olan problemleri içerir, yani bir cevap verilirse, bilgisayar, cevabın doğru olup olmadığını etkili bir şekilde doğrulayabilir, ancak doğrudan yapabilecek etkili bir algoritma yoktur Cevap ver.
NP tipi problemlerin zorluğu, problemin çözümünün mevcut olmayabilmesidir. Nash dengesinin hesaplanması için, Nash'in kanıtı, anlayışın varlığını doğrular. Bu nedenle, Nash denge problemi "P ve NP" paradigması için geçerli değildir. 1994 yılında Christos Papadimitriou Adı verilen bir türü tanımlar PPAD Yeni karmaşıklık sınıfı. PPAD gibi problemler için çözüm her zaman mevcuttur, ancak hesaplanması ve çözülmesi için bilinen etkili bir algoritma yoktur, bu nedenle Nash dengesi gibi problemler için uygundur.
Constantinos Daskalakis ve Nash 2013'te fotoğraflandı. | Resim kaynağı: Vasilis Syrgkanis
PPAD " Yönlendirilmiş grafiğin polinom kontrol parametreleri "(Yönlendirilmiş grafikler için Polinom Parite Argümanı), kombinatoryal matematiğin varlığını kanıtlamak için kullanılan belirli bir standart parametreyi ifade eder. Bu parametreye" El sıkışma lemma "(El sıkışma lemması) Sonucun yönlendirilmiş versiyonu. PPAD, bu lemma ile bir çözümün varlığını kanıtlamak için kullanılabilecek tüm hesaplama sorunlarını içerir.
Yönlendirilmiş bir grafik, sivri uçlu (sol) bir grafiğe atıfta bulunur ve yönsüz grafik (sağda) işaret etmez. | Resim kaynağı: Wikipedia
Grafik teorisi alanında, el sıkışma lemması, her sonlu yönsüz grafik için, tek kenarlı köşe sayısının çift olduğunu söyler. Bir partide bir grup insanın tokalaşması durumunda, bu, çift sayıda ve tek sayıda insanın el sıkıştığı anlamına gelir. Örneğin, şekilde, çift numaralı köşeler (2, 4, 5 ve 6 olarak etiketlenmiş köşeler) tek numaralı kenarlara sahiptir. Ve köşelerle bağlanan kenarların toplamı 2 + 3 + 2 + 3 + 1 = 14'dür, bu da kenar sayısının iki katına eşittir. El sıkışma lemması 1736'da matematikçi Euler tarafından kanıtlandı. | Resim kaynağı: Wikipedia
PPAD'deki en önemli problemlerden biri, saf matematikte bir sonucun hesaplanan versiyonudur. Brouwer sabit nokta teoremi (Brouwer sabit nokta teoremi). Bu teorem Brouwer 1911'de kanıtlandı diyor ki, Bir küreden kendisine sürekli bir eşleme tüm noktaları hareket ettiremez; eşlemenin altında en az bir nokta sabit kalır . Bu temel sonuç, Nash dengesinin varlığının kanıtı da dahil olmak üzere sayısız matematiksel kanıtın temelidir.
Brouwer'in kanıtı Yapısal olmayan , Yani sabit noktaların varlığını sağlasa da bu sabit noktaların nasıl bulunacağını göstermez. Brouwer'in sabit nokta teoreminin hesaplamalı versiyonu, sabit noktaları bulmak için algoritmalar geliştirmeye çalışır. Papadimitriou, 1994 tarihli makalesinde bu hesaplanmış versiyondaki sorunun " PPAD-tamamlandı "Tür; bu, bu sorunun PPAD türüne ait olduğu anlamına gelir ve PPAD türündeki herhangi bir sorun, PPAD tam türüne indirgenebilir, bu da PPAD türü sorun kadar zor olduğu anlamına gelir.
On yıl sonra Daskalakis, Papadimitriou'nun doktora öğrencisi oldu ve Nash denge problemini incelemeye başladı. O ve Papadimitriou, Paul Goldberg Birlikte önemli ilerleme kaydetti ve kanıtladılar Hesaplama açısından Nash dengesi problemi, Brouwer sabit noktasını bulma problemine eşdeğerdir, dolayısıyla Nash denge problemi de PPAD-tamdır .
Nash denge probleminin çözülmesinin zor olduğunu kanıtlarken, Daskalakis ve diğerlerinin çalışması Nash dengesinin evrenselliğini bozdu: stratejik ajanların etkileşiminin her zaman Nash dengesine ulaşmasını bekleyemeyiz, çünkü bu ajanlar zor hesaplamalar yapamazlar. Pratik bir perspektiften, Nash dengesi her zaman mevcut değildir.
Nash dengesi her zaman var olmasına rağmen, bu dengeyi gerçek bir hesaplama perspektifinden elde etmek mümkün olmayabilir. | Resim kaynağı: ICM
Bu çalışma aynı zamanda Nash denge problemi için etkili bir algoritmanın neden bu kadar zor olduğunu ortaya koyuyor. Nash dengesini hesaplamak için insanların geliştirdiği algoritmanın iç yapısını incelersek, PPAD benzeri sembol yapısının arka planda gizli olduğunu göreceğiz. Daskalakis ve arkadaşlarının çalışması, bu yapının kaçınılmaz olduğunu göstermektedir. Çalışmaları, yeni kavramlar ve teknolojiler hakkında içgörü sağlamanın yanı sıra, önemli oyun alt kategorileri için denge hesaplaması için verimli ve pratik algoritmalara çok ihtiyaç olduğunu vurgulamaktadır. Sonraki çalışmasında Daskalakis, Nash dengesine yaklaşmada dikkate değer sonuçlar yarattı ve bu da diğer araştırmacıların derinlemesine gelişimi için ilham kaynağı oldu.
Açık artırma mekanizması tasarım sorunları
Daskalakis'in olağanüstü katkılarda bulunduğu ikinci büyük alan ve ekonomiden biri denir Mekanizma tasarımı (Mekanizma tasarımı) dalı ile ilgili. Buradaki "mekanizma", özneyi belirli bir şekilde hareket etmeye yönlendirmek için bir dizi teşvik mekanizması sağlamayı ifade eder. Bir anlamda mekanizma tasarımı, oyun teorisinin tam tersidir, çünkü oyun teorisi oyundaki konuların nasıl davranacağını analiz etmeye çalışır ve Mekanizma tasarımının amacı, konunun istenen sonuca ulaşması için doğru teşvikleri sağlayacak bir oyun tasarlamaktır. .
Mekanizmanın en temel modeli açık arttırma , Ve en basit örnek, yalnızca bir öğe satan bir açık artırmadır. Kârı maksimize etmek için açık artırma kuralları nasıl tasarlanır? 1981'de ekonomist Roger Myerson Tek bir ürün müzayedesi sorusuna ve her teklif sahibinin sonuç tercihinin tek bir sayı olarak özetlenebileceği diğer açık artırma ayarlarına eksiksiz ve zarif bir cevap sağlar. Böyle bir açık artırma kurulumuna " Tek boyut ".
Myerson'ın çalışması ekonomi üzerinde büyük bir etkiye sahipti ve birçok takip araştırmasına ilham verdi. Öngörüleri, sondaj hakları açık artırmaları, telekom spektrum müzayedeleri ve çevrimiçi müzayedeler gibi birçok şirkete uygulanır. 2007'de Nobel Ekonomi Ödülü, mekanizma tasarımı alanında üç bilim insanına verildi Myerson , Leonid Hurwicz ile Eric Maskin .
Birden fazla ürünün satışa sunulduğu ve ürünlerin satış için paketlenebileceği ve teklif verenin paketlenmiş ürünlere ilişkin değerlemesinin tek bir numara ile temsil edilemeyeceği başka açık artırma ayarları türleri de vardır. Tek boyutlu müzayedeler konusundaki tam anlayışımızın aksine, bu tür çok boyutlu müzayedeler hakkında çok az şey biliyoruz.
Biri bir resim satın almak istiyor ve biri başka bir resim almak istiyor. Paket satışları, farklı alıcıların rekabeti tetikleyecek, böylece satışları teşvik edecek ve karı artıracaktır. | Resim kaynağı: ICM
Aslında, bir alıcıya iki ürünün nasıl satılacağına dair en iyi stratejiyi bile bilmiyoruz. Alıcıların ve ürünlerin sayısı arttıkça, olası açık artırma tasarımlarının sayısı hızla son derece karmaşık bir koleksiyona dönüşür. En iyi tasarım bulunsa bile, genellikle karşı-sezgisel özellikler gösterir ve teklif sahiplerinin tercih ettiği ayrıntılara karşı oldukça hassastır.
Yaklaşık 2011'den itibaren Daskalakis bu göz korkutucu ve karmaşık problemi araştırmaya başladı. En büyük zorluklardan biri, tüm olası açık artırma tasarımlarının koleksiyonuna ilişkin bir içgörü geliştirmektir. Daskalakis ve o sırada öğrencileri Yang Cai karşı Matt Weinberg Birlikte ustaca bir yöntem geliştirdi Bu koleksiyondaki yapıyı ortaya çıkarmak için doğrusal programlamayı kullanın .
Bu yapıyı kullanarak bir yöntem geliştirdiler, Mekanizma tasarım problemlerini algoritma tasarım problemlerine dönüştürün . Ardından, en iyi mekanizmayı oluşturmak için hesaplama açısından verimli algoritmalar oluşturabilirler. Bu çalışma ile elde edilen yapı ve hesaplama arasındaki dengenin önemli olduğu kanıtlanmıştır.
Bu çalışmada geliştirilen yeni anlayışlar Daskalakis'i teşvik etti, Alan Deckelbaum ile Christos Tzamos Daha fazla ilerleme. Matematikte bunlardan birine denir Optimal taşıma teorisi Alanında yeni sonuçlar elde edilir ve bu sonuçları tek bir alıcı ortamında çok maddeli mekanizmanın optimal yapısını matematiksel olarak tanımlamak için kullanır.
Daskalakis'in mekanizma tasarımı üzerindeki çalışmasının en değerli yönü, daha önce çözülmesi zor olduğu düşünülen bir sorunu çözmektir. Güçlü teorik yapıları nedeniyle, bu sonuçların doğrudan belirli problemlere uygulanmadan önce basitleştirilmesi gerekir. Daskalakis de dahil olmak üzere bazı araştırmacılar, basitlik ve sağlamlık karşılığında biraz iyimserlik pahasına, yapısını ve algoritmasını ayarlamanın sonuçlarını keşfetmeye başladılar.
Nash denge problemleri ve mekanizma tasarımı konusundaki çalışmalarına ek olarak Daskalakis ayrıca makine öğrenimi, istatistik ve olasılık teorisi ve hesaplamalı biyoloji alanlarına da katkıda bulunmuştur. Hesaplamalı biyoloji alanında, ana görevlerden biri moleküler verilerden yeniden yapılandırmaktır. Filogenetik ağaç (Filogenetik ağaç). 2011 yılında Daskalakis ve Elchanan Mossel , Sebastien Roch Aynı zamanda, matematiksel filogenide temel bir varsayımın bir kanıtını yayınladı, bu varsayım, evrim ağacının yeniden inşa edilebileceği belirli koşullar hakkındadır. En son çalışmaları, yüksek boyutlu istatistik ve makine öğreniminin teorik temellerine odaklanıyor.
Bazen doğru soruları sorarsan keşif yoluna girersin. | Resim kaynağı: ICM
Constantinos Daskalakis'in çalışması zor, karmaşık ve uzun vadeli meselelerle başa çıkmada korkusuzluğu gösteriyor. Problemin belirli ayrıntılarını derinlemesine inceledi ve ondan edindiği sezgiyi, teorik ilerlemenin anahtarı haline gelen yapı ve teknolojiye ilişkin içgörüleri geliştirmek için kullandı.
Araştırmacı olarak yeteneği, aktif merakı ve bulaşıcı coşkusuyla birlikte, onu bu alanda doğal bir lider yaptı. Henüz 37 yaşında olan Daskalakis, önümüzdeki yıllarda da bu rolü oynamaya kesinlikle devam edecek.
Referans bağlantısı:
https://www.mathunion.org/imu-awards/rolf-nevanlinna-prize/rolf-nevanlinna-prize-2018
