Mengapa para ekonom harus peduli pada kompleksitas komputasi

Ketika mencoba meyakinkan para ekonom tentang relevansi teori kompleksitas dalam cetakan, adakah referensi standar untuk dikutip? Saya akrab dengan posting blog Noam Nisan , survei Tim Roughgarden , dan bab 11 esai Scott Aaronson . Posting-posting ini dapat diakses oleh para ilmuwan komputer, tetapi tidak menggunakan bahasa para ekonom dan tidak dipublikasikan di tempat-tempat yang biasanya dibaca oleh mereka. Adakah argumen yang bagus untuk pentingnya kompleksitas equilibiria, dll. Yang ditargetkan untuk para ekonom? Apakah ada tinjauan sejarah yang baik tentang bagaimana para ekonom merespons tekanan dari para ilmuwan komputer?

Dapat diperdebatkan bahwa ekonomi neoklasik hanya ditutup dan karenanya makalah semacam itu tidak dapat eksis, tetapi ada bidang yang sedikit heterodoks seperti ekonomi evolusioner dan kompleksitas (dalam pengertian SFI) ekonomi yang membenarkan diri mereka sendiri dalam bahasa yang akrab bagi para ekonom. Bidang-bidang ini juga membuat kritik yang serupa dengan pendekatan kompleksitas komputasi (seperti menjauh dari asumsi kesetimbangan), tetapi jangan membenarkannya seketat CS.

Pertanyaan-pertanyaan Terkait

• Lensa algoritmik dalam ilmu sosial

• Kompleksitas komputasi dalam keuangan kuantitatif

Saya melihat dua arah terpisah untuk menjawab pertanyaan Anda. Salah satunya adalah Bagaimana filsafat ilmu komputer dan pemikiran komputasi berdampak pada bidang ekonomi, dan mengapa para ekonom harus peduli dengan pendekatan ilmu komputer ? Ini adalah pertanyaan yang sangat keren tapi sangat luas yang saya akan hindari berusaha menjawab.

Yang kedua lebih spesifik: Sekarang para ilmuwan komputer tahu bahwa banyak masalah dalam teori permainan itu sulit, bagaimana kita meyakinkan ekonom bahwa ini adalah masalah penting dengan atau keberatan dengan pekerjaan mereka? Ini mungkin bukan apa yang ada dalam pikiran Anda, tetapi tampaknya merupakan interpretasi dari apa yang Anda tulis, jadi saya ingin mengatasinya karena saya pikir itu agak bermasalah dan saya pikir ada alasan untuk tidak menulis esai dengan alasan ini ( yang mungkin menjelaskan kurangnya jawaban).

Pertama, para ekonom mikro seringkali merupakan ahli teori dan mereka mungkin lebih tertarik untuk memahami masalah dalam model mereka daripada kita. Tidak ada alasan apriori satu pendekatan lebih baik dari yang lain. Sebagai analogi, banyak ilmuwan komputer teoretis senang untuk merancang algoritma yang bekerja di atas bilangan real meskipun ini mungkin memerlukan operasi yang tidak dapat dipastikan. Demikian pula, bagi seorang ekonom, kompleksitas mungkin merupakan detail yang mengaburkan pemahaman seseorang tentang apa yang penting dalam model mereka daripada pertimbangan utama. Ini tampaknya lebih merupakan masalah preferensi atau filosofi daripada benar atau salah.

Kedua, tidak jelas bahwa ilmu komputer masih dalam posisi untuk berdebat dengan meyakinkan bahwa model kita lebih cocok dengan dunia nyata daripada mereka, sampai kita memiliki data eksperimental untuk mendukungnya. (Lagi pula, mungkin misalnya bahwa pasar sering menemukan keseimbangan dengan cepat dalam praktiknya, sehingga kekerasan komputasi tidak relevan dengan aplikasi dunia nyata.) Tanpa data, ketidaksepakatan itu bersifat filosofis dan sulit untuk mengklaim ada sisi yang benar atau salah . Saya tidak tahu bahwa kami memiliki cukup data untuk membuat klaim spesifik.

Ketiga, saya pikir banyak ekonom yang relevan dengan masalah ini telah memperhatikan. Di bidang-bidang seperti pencocokan, misalnya (subjek Nobel tahun lalu!), Kompleksitas komputasi dan pendekatan algoritmik adalah penting karena mereka berupaya menerapkan solusi dalam skala besar. Jadi jika klaim ekonom bahwa kompleksitas tidak relevan dengan dirinya kepentingan, dia mungkin benar; tetapi ada orang lain yang memperhatikan.

Jadi singkatnya, walaupun sepertinya ini adalah tujuan yang berharga untuk membantu para ekonom mengetahui hasil mengenai kompleksitas dalam ekonomi (terutama karena beberapa memang tertarik), saya tidak yakin bahwa kita berada dalam posisi untuk berdebat bahwa mereka harus memperhatikan banyak hal. atau mengubah pendekatan mereka; dan saya pikir argumen ilmiah yang kuat akan membutuhkan lebih banyak data daripada hanya filsafat.

Para teoretikus aliran permainan utama, saya pikir, menjadi jauh lebih terbuka untuk pekerjaan kontemporer dalam komunitas ilmu komputer, sehingga mungkin kurang perlu untuk "membuat kasus" untuk teori permainan algoritmik daripada di masa lalu.

Salah satu teks yang saya tahu yang paling mudah diakses untuk melelang teori dengan latar belakang ekonomi adalah " Pendekatan dalam Desain Ekonomi " Jason Hartline . Bab 1 secara khusus mencoba membuat kasus untuk algoritma aproksimasi, jika tidak secara khusus untuk pentingnya kompleksitas komputasi.

ada sudut lain berdasarkan beberapa pencarian lagi. prinsip utama / nexus / persimpangan yang muncul antara ekonomi dan ilmu komputer / teori kompleksitas adalah menghitung Nash equilibria yang merupakan pusat berbagai model ekonomi, di mana Daskalakis (berkolaborasi dengan Papadimitriou) adalah tokoh terkemuka. [1] [2] [5]

tumpang tindih ini umumnya terjadi melalui bidang teori permainan di mana [3] adalah survei yang diterbitkan dalam ACM dan yang berfungsi sebagai jembatan utama antara bidang. juga Shoham mengutip [4] sebagai survei yang berfokus pada Nash equilibria dan "Sebagian besar diarahkan pada para ekonom, itu mencakup banyak bahan latar belakang tentang konsep-konsep yang relevan dari teori kompleksitas."

[1] Kompleksitas Menghitung Ekuilibrium Nash, Konstantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou

[2] Ilmu komputer apa yang bisa mengajarkan ekonomi Berita MIT

[3] Ilmu Komputer dan Teori Game Shoham

[4] T. Roughgarden. Computing equilibria: Perspektif kompleksitas komputasi. Teori Ekonomi, 2008

[5] Nash Equilibria: Kompleksitas, Simetri, dan Daskalakis Aproksimasi

Waspadai itu bukan hanya ahli ekonologi tetapi juga ahli matematika yang pendidikannya tampaknya masih belum dikonfirmasi dengan definisi NPC = PET:

Pada 2011 hingga setengah dari 2013 http://www.proofwiki.org/wiki/Definition:NP-Lengkap masih membingungkan arti masalah NP-lengkap dengan masalah NP-hard yang mungkin di Co-NP atau bahkan di luar dan tanpa nondeterminisme dengan steprate konstan terikat secara polinomi.

Para ekonom kemungkinan besar dapat termotivasi dengan diarahkan ke bukti kelengkapan NP pasar bebas oleh P Maymin di http://arxiv.org/pdf/1002.2284 dan ditanyai tentang kebijaksanaan mereka untuk rekayasa algoritma sosial-evolusioner-informatif.

ini jelas merupakan bidang yang sangat baru sehingga survei dan literatur yang mapan akan sulit didapat. juga teori kompleksitas mungkin sedikit lebih abstrak untuk ini. Namun area yang menarik / alami pada kenaikan / persimpangan antara CS / econ: coba penelitian terbaru ke dalam lelang yang sangat signifikan mengingat iklan Google Adsense sebagian besar mendanai kebangkitan perusahaan selama dekade terakhir dan juga IPO berbasis lelang tunggal mereka. juga perhatikan fluktuasi harga ekonomi skala besar dan dinamika pembeli / penjual dapat dimodelkan agak sebagai sistem seperti lelang.

bidang lain yang agak mirip di mana beberapa CS yang sangat maju / substansial diterapkan adalah perdagangan kecepatan tinggi, ilmu yang kompleks / maju, tetapi sayangnya itu tidak dipublikasikan secara terbuka karena kurangnya kerahasiaan.

[1] Pelelangan dan penawaran: Panduan untuk ilmuwan komputer oleh Parsons

[2] Ilmu komputer menangani masalah ekonomi berusia 30 tahun - peneliti MIT menggeneralisasi karya pemenang Nobel dalam lelang satu item ke lelang yang melibatkan banyak item.

[3] Kompleksitas ukuran menu lelang Sergiu Hart, Noam Nisan