Почему экономисты должны заботиться о вычислительной сложности

17

При попытке убедить экономистов в актуальности теории сложности в печати, есть ли стандартная ссылка для цитирования? Я знаком с постом в блоге Ноама Нисана , опросом Тима Раугардена и 11-й статьей эссе Скотта Ааронсона . Эти посты доступны для компьютерных ученых, но не используют язык экономистов и не публикуются в местах, которые они обычно читают. Есть ли веские аргументы в пользу важности сложности равновесия и т. Д. Для экономистов? Есть ли хороший исторический обзор того, как экономисты отреагировали на давление со стороны ученых-компьютерщиков?

Можно утверждать, что неоклассическая экономика просто закрыта, и, следовательно, такие документы не могут существовать, но есть немного неортодоксальные области, такие как эволюционная экономика и экономика сложности (в смысле SFI), которые оправдывают себя на языке, знакомом экономистам. Эти поля также дают критические оценки, такие как подход к сложности вычислений (например, отход от предположений о равновесиях), но не оправдывают их так строго, как CS.


Смежные вопросы

Артем Казнатчеев
источник
2
Попробуйте это, рынки эффективны тогда и только тогда, когда P = NP; arxiv.org/pdf/1002.2284.pdf
Мухаммед Аль-Туркистани,
2
@ MohammadAl-Turkistany: я быстро взглянул на это, и проблема решения «Существует ли стратегия, которая статистически значимо (после учета возможного извлечения данных) зарабатывает деньги (после учета затрат по сделке)?» плохо определено (в частности, определение «стратегия» и «статистически значимый»), и доказательство далеко не «математическое» (стандартное сокращение от NP-полной задачи)
Марцио Де Биаси
Одной из новых областей, где существует много
общего
2
@vzn, это был бы слишком длинный список, так как AGT теперь является стандартной частью информатики. Для более ограниченных списков уже есть вопросы (которые я упоминал в основной части этого поста), например, вопросы о количественных финансах и результатах КС, которые оказали прямое влияние и изменили существующие теории / парадигмы в социальных науках . Хотя я ценю ваш энтузиазм, я предпочитаю задавать сфокусированные вопросы и ценю сфокусированные ответы, такие как ответы Марцио Де Биаси, Усула и Аарона Рота.
Артем Казнатчеев

Ответы:

13

Я вижу два отдельных направления, чтобы ответить на ваш вопрос. Один из них: Как философия информатики и компьютерное мышление повлияли на экономическую область и почему экономисты должны заботиться о подходе информатики ? Это действительно крутой, но очень широкий вопрос, на который я не буду пытаться ответить.

Второе более конкретно: теперь, когда компьютерные специалисты знают, что многие проблемы в теории игр трудны, как мы можем убедить экономистов в том, что это важные проблемы или возражения против их работы? Возможно, это не то, что вы имели в виду, но, похоже, это интерпретация того, что вы написали, поэтому я хочу обратиться к нему, потому что я думаю, что это немного проблематично, и я думаю, что есть причины не писать эссе, приводящее этот пункт что может объяснить отсутствие ответов).

Во-первых, микроэкономисты часто являются теоретиками, и они могут быть более заинтересованы в понимании проблемы в своей модели, чем в нашей. Нет априорной причины, что один подход лучше другого. Как аналогия, многие теоретические компьютерные ученые рады разработать алгоритмы, которые работают над действительными числами, даже если это может потребовать неразрешимых операций. Точно так же для экономиста сложность может быть деталью, которая затуманивает понимание того, что важно в их модели, а не является ключевым фактором. Это кажется больше вопросом предпочтений или философии, чем правильным или неправильным.

Во-вторых, не ясно, что информатика еще может убедительно утверждать, что наши модели соответствуют реальному миру лучше их, пока у нас нет экспериментальных данных, подтверждающих это. (В конце концов, это может быть, например, то, что рынки часто быстро находят равновесия на практике, поэтому сложность вычислений не имеет отношения к приложениям реального мира.) Без данных разногласия философские, и трудно утверждать, что есть правильная или неправильная сторона , Я не знаю, что у нас еще достаточно данных, чтобы делать какие-то конкретные заявления.

В- третьих, я думаю , что многие экономисты, кому эти вопросы , которые актуальны уже принимает уведомление. Например, в таких областях, как сопоставление (тема прошлогоднего Нобеля!), Сложность вычислений и алгоритмический подход важны, поскольку они пытаются реализовать решения в больших масштабах. Так что, если экономист утверждает, что сложность не имеет отношения к ее интересам, она может быть права; но есть и другие, которые обращают на это внимание.

Таким образом, в целом, хотя кажется, что стоит сделать ставку на то, чтобы помочь экономистам осознать результаты, касающиеся сложности в экономике (особенно когда некоторые проявляют интерес), я не уверен, что мы можем утверждать, что им следует уделять много внимания или изменить свой подход; и я думаю, что сильный научный аргумент потребует больше данных, чем просто философии.

усул
источник
Отличный ответ! Мне нравится ваша вторая интерпретация, я думаю, что она соответствует тому, что я имел в виду. Мне также нравится ваша первая интерпретация, обидно, что вы решили не обращать на это внимание. Я буду держать вопрос открытым дольше, потому что я думаю, что есть такие опросы, в комментариях есть по крайней мере один хороший, который я читал перед сном сегодня вечером.
Артем Казнатчеев
8

Теоретики основных потоковых игр, я думаю, становятся все более открытыми для современной работы в сообществе компьютерных наук, поэтому может быть меньше необходимости «обосновывать» теорию алгоритмических игр, чем это было в прошлом.

Один из известных мне текстов, наиболее доступных для теоретиков аукционов с экономическим прошлым, - « Приближение экономического дизайна » Джейсона Хартлайна . В частности, в главе 1 делается попытка обосновать алгоритмы аппроксимации, если не конкретно важность вычислительных сложностей.

Аарон Рот
источник
-1

вот другой угол, основанный на еще нескольких поисках. Принцип исторической / формирующейся связи / пересечения между экономикой и теорией информатики / сложности заключается в вычислении равновесий Нэша, которые являются центральными для различных моделей экономики, где Даскалакис (в сотрудничестве с Пападимитриу) является ведущей фигурой. [1] [2] [5]

это наложение обычно происходит в области теории игр, где [3] представляет собой опрос, опубликованный в ACM и служащий еще одним ключевым мостом между полями. также Шохам цитирует [4] исследование, посвященное равновесиям Нэша, и «ориентированное в основном на экономистов, оно включает в себя достаточно справочных материалов по соответствующим концепциям из теории сложности».

[1] Сложность вычисления равновесия по Нэшу Константинос Даскалакис, Пол В. Голдберг, Христос Х. Пападимитриу

[2] Чему информатика может научить экономику MIT News?

[3] Информатика и теория игр Шохам

[4] Т. Роугарден. Вычислительные равновесия: перспектива вычислительной сложности. Экономическая теория, 2008

[5] Равновесия по Нэшу: сложность, симметрии и приближение Даскалакиса.

ВЗН
источник
К сожалению, второй взгляд, ссылка на Roughgarden аналогична цитируемой AK, за исключением опубликованной версии журнала. но это показывает / подчеркивает, что интерфейс в основном через равновесия Нэша, не указанные в вопросе.
октября
-2

Остерегайтесь, что это не только эконометристы, но даже математики, чье образование все еще кажется совершенно несоответствующим определению NPC = PET:

С 2011 по половину 2013 года http://www.proofwiki.org/wiki/Definition:NP-Complete по- прежнему путает значение NP-полной проблемы с проблемой NP-трудной проблемы, которая может быть в Co-NP или даже за ее пределами и без недетерминированности с постоянной степенью полиномиально ограниченной.

Вероятно, лучше всего мотивировать экономистов, указав на доказательство NP-полноты свободных рынков П. Маймином в http://arxiv.org/pdf/1002.2284, и спросить их об их мудрости для разработки социально-эволюционно-информационных алгоритмов.

DerComputer
источник
-4

это явно очень развивающаяся область, поэтому будет сложно найти обзоры и достоверную литературу. также теория сложности может быть немного более абстрактной для этого. однако убедительная / естественная область на подъеме / пересечении между CS / econ: попробуйте недавнее исследование аукционов, которое особенно важно, учитывая, что реклама Google Adsense в значительной степени финансирует рост компании за последнее десятилетие, а также их уникальное IPO на основе аукциона. Также обратите внимание, что масштабные колебания цен в экономике и динамика покупателя / продавца могут быть несколько смоделированы как аукционная система.

Еще одна схожая область, в которой применяются некоторые очень продвинутые / существенные КС, - это высокоскоростная торговля, сложная / развивающаяся наука, но, к сожалению, это не является опубликованным исследованием из-за его высокой секретности.

[1] Аукционы и торги: руководство Parsons для программистов

[2] Информатика решает 30-летнюю проблему экономики - исследователи Массачусетского технологического института обобщают работу Нобелевского лауреата по аукционам с одним предметом на аукционы с участием нескольких предметов.

[3] Размер меню сложности аукционов Серджиу Харт, Ноам Нисан

ВЗН
источник
3
Это не ответ на вопрос. Я не спрашивал, что является пересечением CS / Econ, я уже знаю об этом, и есть другие вопросы (в разделе связанных вопросов), которые уже имеют дело с этим. Мой вопрос не о результатах сложности, а о том, как объяснить вычислительную сложность экономистам.
Артем Казнатчеев
без разницы! удачи! это ответ на вопрос «почему экономисты должны заботиться о сложности вычислений» ... может быть, отсутствие сильных реферирующих индикаторов - это показатель, который, возможно, им не стоит! Ваши вопросы иногда слишком узки, чтобы требовать ответного заколки.
vzn