Dlaczego ekonomiści powinni dbać o złożoność obliczeniową

17

Czy próbując przekonać ekonomistów o znaczeniu teorii złożoności w druku, istnieje standardowe odniesienie do cytowania? Znam post na blogu Noama Nisana , ankietę Tima Roughgarden i rozdział 11 eseju Scotta Aaronsona . Te posty są dostępne dla informatyków, ale nie używają języka ekonomistów i nie są publikowane w miejscach zwykle przez nich czytanych. Czy istnieją dobre argumenty przemawiające za znaczeniem złożoności równowagi itp. Skierowanej do ekonomistów? Czy istnieje dobry historyczny przegląd reakcji ekonomistów na presję ze strony informatyków?

Można argumentować, że ekonomia neoklasyczna jest po prostu zamknięta i dlatego takie dokumenty nie mogą istnieć, ale istnieją nieco heterodoksyjne dziedziny, takie jak ekonomia ewolucyjna i ekonomia złożoności (w sensie SFI), które uzasadniają się w języku znanym ekonomistom. Te pola również powodują podobne krytyki, jak podejście oparte na złożoności obliczeniowej (takie jak odejście od założeń równowagi), ale nie uzasadniają ich tak rygorystycznie jak CS.


Powiązane pytania

Artem Kaznatcheev
źródło
2
Spróbuj tego, rynki są wydajne wtedy i tylko wtedy, gdy P = NP; arxiv.org/pdf/1002.2284.pdf
Mohammad Al-Turkistany
2
@ MohammadAl-Turkistany: Rzuciłem na to okiem i problem decyzyjny „Czy istnieje strategia, która statystycznie znacząco (po uwzględnieniu ewentualnego eksploracji danych) przynosi pieniądze (po uwzględnieniu kosztów transakcji)?” jest słabo zdefiniowane (w szczególności definicja „strategii” i „statystycznie istotnego”), a dowód jest daleki od bycia „matematycznym” (standardowa redukcja z problemu NP-zupełnego)
Marzio De Biasi
jeden obszar powstających tam, gdzie jest dużo pokrywają między CS & ECON aukcje
vzn
2
@vzn to byłaby zbyt długa lista, ponieważ AGT jest obecnie standardową częścią informatyki. W przypadku bardziej ograniczonych list istnieją już pytania (o których wspomniałem w treści tego postu), np. Dotyczące finansów ilościowych i wyników CS, które wywarły bezpośredni wpływ i zmieniły istniejące teorie / paradygmaty w naukach społecznych . Chociaż doceniam twój entuzjazm, wolę zadawać ukierunkowane pytania i doceniam ukierunkowane odpowiedzi, takie jak te, które otrzymali Marzio De Biasi, usul i Aaron Roth.
Artem Kaznatcheev

Odpowiedzi:

13

Widzę dwa oddzielne kierunki, aby odpowiedzieć na twoje pytanie. Jednym z nich jest W jaki sposób filozofia informatyki i myślenie obliczeniowe wpłynęły na dziedzinę ekonomii i dlaczego ekonomiści powinni dbać o podejście informatyczne ? To naprawdę fajne, ale naprawdę szerokie pytanie, którego uniknę próbować odpowiedzieć.

Drugi jest bardziej szczegółowy: skoro informatycy wiedzą, że wiele problemów w teorii gier jest trudnych, jak przekonać ekonomistów, że są to ważne problemy lub zastrzeżenia do ich pracy? Być może nie o to ci chodziło, ale wydaje się, że jest to interpretacja tego, co napisałeś, więc chcę się tym zająć, ponieważ uważam, że jest to trochę problematyczne i uważam, że istnieją powody, aby nie pisać eseju na ten temat ( co może tłumaczyć brak odpowiedzi).

Po pierwsze, mikroekonomiści są często teoretykami i mogą być bardziej zainteresowani zrozumieniem problemu w swoim modelu niż w naszym. Nie ma a priori powodu, że jedno podejście jest lepsze od drugiego. Analogicznie wielu teoretycznych informatyków chętnie opracowuje algorytmy działające na liczbach rzeczywistych, nawet jeśli może to wymagać nierozstrzygalnych operacji. Podobnie dla ekonomisty złożoność może być szczegółem, który zaciemnia zrozumienie tego, co jest ważne w ich modelu, a nie kluczową kwestią. Wydaje się, że jest to raczej kwestia preferencji lub filozofii niż dobra lub zła.

Po drugie, nie jest jasne, czy informatyka jest w stanie przekonująco argumentować, że nasze modele pasują do realnego świata lepiej niż ich, dopóki nie uzyskamy danych eksperymentalnych na poparcie tego. (W końcu może się zdarzyć, że rynki często szybko znajdą równowagę w praktyce, więc twardość obliczeń nie ma znaczenia dla rzeczywistych aplikacji). Bez danych spór jest filozoficzny i trudno jest twierdzić, że istnieje dobra lub zła strona . Nie wiem, czy mamy jeszcze wystarczająco dużo danych, aby wysunąć jakieś konkretne roszczenia.

Po trzecie, myślę, że wielu ekonomistów, do których te kwestie istotne nie zostały zwracając uwagi. Na przykład w takich obszarach jak dopasowanie (temat zeszłorocznego Nobla!) Złożoność obliczeniowa i podejście algorytmiczne są ważne, gdy próbują wdrażać rozwiązania na dużą skalę. Więc jeśli ekonomistka twierdzi, że złożoność nie ma związku z jej interesami, może mieć rację; ale są też inni, którzy to zauważają.

Podsumowując, chociaż wydaje się, że warto pomóc uświadomić ekonomistom wyniki dotyczące złożoności ekonomii (zwłaszcza, że ​​niektórzy się tym interesują), nie jestem pewien, czy możemy argumentować, że powinni zwrócić szczególną uwagę lub zmienić swoje podejście; i uważam, że silny argument naukowy wymagałby więcej danych niż tylko filozofii.

usul
źródło
Świetna odpowiedź! Podoba mi się twoja druga interpretacja, myślę, że jest zgodna z tym, co miałem na myśli. Podoba mi się również twoja pierwsza interpretacja, szkoda, że ​​zdecydowałeś się jej nie zajmować. Pozostawię pytanie otwarte dłużej, ponieważ myślę, że są takie ankiety, w komentarzach jest co najmniej jeden dobry, który jest moim dzisiejszym czytaniem przed snem.
Artem Kaznatcheev
8

Myślę, że główni teoretycy gier strumieniowych stają się znacznie bardziej otwarci na współczesną pracę w środowisku informatyki, więc może być mniej konieczne „uzasadnianie” teorią gier algorytmicznych niż w przeszłości.

Jednym z tekstów, które znam na ten temat, jest najbardziej dostępny dla teoretyków aukcji z wykształceniem ekonomicznym, to „ Przybliżenie projektu ekonomicznego ” Jasona Hartline'a . W szczególności rozdział 1 próbuje uzasadnić algorytmy aproksymacyjne, jeśli nie specjalnie ze względu na znaczenie złożoności obliczeniowej.

Aaron Roth
źródło
-1

Oto inny kąt oparty na dalszych poszukiwaniach. Zasadniczym historycznym / powstającym ogniwem / przecięciem ekonomii z informatyką / teorią złożoności jest obliczanie równowagi Nasha, które są kluczowe dla różnych modeli ekonomicznych, gdzie Daskalakis (współpracujący z Papadimitriou) jest postacią wiodącą. [1] [2] [5]

to nakładanie się występuje na ogół w dziedzinie teorii gier, gdzie [3] jest ankietą opublikowaną w ACM i służy jako kolejny kluczowy pomost między polami. Shoham cytuje [4] jako badanie koncentrujące się na równowadze Nasha i „Przeznaczone głównie dla ekonomistów, zawiera obszerny materiał źródłowy na temat odpowiednich pojęć z teorii złożoności”.

[1] Złożoność obliczania równowagi Nasha Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou

[2] Czego informatyka może nauczyć ekonomii MIT News

[3] Informatyka i teoria gier Shoham

[4] T. Roughgarden. Równowagi obliczeniowe: perspektywa złożoności obliczeniowej. Teoria ekonomiczna, 2008

[5] Równowagi Nasha: złożoność, symetrie i przybliżenie Daskalakis

vzn
źródło
Ups, drugie spojrzenie, referencje do Roughgarden są takie same, jak cytowane przez AK, z wyjątkiem opublikowanej wersji czasopisma. ale pokazuje / podkreśla, że ​​interfejs odbywa się głównie poprzez równowagę Nasha, nie wskazaną w pytaniu.
vzn
-2

Uwaga, to nie tylko ekonometrzy, ale nawet matematyków, których wykształcenie wydaje się dość niesprawiedliwe dzięki definicji NPC = PET:

Począwszy od 2011 r. Do połowy 2013 r. Http://www.proofwiki.org/wiki/Definition:NP-Complete nadal myli znaczenie problemu NP-zupełnego ze znaczeniem problemu NP-trudnego, który może występować w Co-NP lub nawet poza i bez niedeterminizmu ze stałym krokiem wielomianowo ograniczonym.

Ekonomiści mogą być najlepiej zmotywowani poprzez wskazanie przez P Maymina na dowód kompletności NP na wolnym rynku w http://arxiv.org/pdf/1002.2284 i zapytanie o ich wiedzę na temat inżynierii algorytmów społeczno-ewolucyjno-informacyjnych.

DerComputer
źródło
-4

jest to z pewnością bardzo wschodząca dziedzina, dlatego trudno byłoby uzyskać ankiety i ugruntowaną literaturę. również teoria złożoności może być nieco bardziej abstrakcyjna. jednak atrakcyjny / naturalny obszar wzrostu / przecięcia między CS / econ: spróbuj najnowszych badań nad aukcjami, co jest szczególnie istotne, biorąc pod uwagę reklamy Google Adsense, które w dużej mierze finansują rozwój firmy w ciągu ostatniej dekady, a także ich wyjątkową ofertę publiczną opartą na aukcjach. należy również zauważyć, że wahania cen ekonomicznych na dużą skalę oraz dynamikę kupujących / sprzedających można nieco modelować jako system podobny do aukcji.

Innym, nieco podobnym obszarem, w którym stosuje się bardzo zaawansowane / znaczące CS, jest szybki handel, złożona / rozwijająca się nauka, ale niestety nie jest to otwarte badanie z powodu dużej tajemnicy.

[1] Aukcje i licytacja: przewodnik dla informatyków autorstwa Parsons

[2] Informatyka rozwiązuje 30-letni problem ekonomiczny - badacze z MIT uogólniają pracę zwycięzcy Nobla na aukcjach pojedynczych przedmiotów na aukcje obejmujące wiele przedmiotów.

[3] Złożoność menu pod względem wielkości aukcji Sergiu Hart, Noam Nisan

vzn
źródło
3
To nie jest odpowiedź na pytanie. Nie pytałem, jakie są skrzyżowania CS / Econ, już je znam i są inne pytania (w sekcji powiązanych pytań), które już sobie z tym poradzą. Moje pytanie nie dotyczy wyników złożoności, ale tego, jak wyjaśnić ekonomistom złożoność obliczeniową.
Artem Kaznatcheev
cokolwiek! powodzenia! jest to odpowiedź na pytanie „dlaczego ekonomiści powinni dbać o złożoność obliczeniową” ... może brak silnych referencji wskazuje, że może nie powinni! twoje pytania są czasem zbyt wąskie, aby wymagać odpowiedzi na rozszczepianie włosów.
vzn