Правило гамильтона не работает

Истоки альтруизма: почему Гамильтон до сих пор правит 50 лет

Пятьдесят лет назад в этом месяце биолог-эволюционист Уильям Дональд Гамильтон опубликовал решение одной из самых устойчивых загадок биологии: почему существует альтруизм?

Альтруистическое поведение — это то, где человек помогает другим за свой счет. Альтруизм повсюду вокруг нас, и все же биологи, начиная с Чарльза Дарвина, рассказали о том, как такое поведение может развиваться в мире естественного отбора.

Гамильтон придумал ответ на этот вопрос, элегантно изложенный в математической формуле, известной теперь как правило Гамильтона.

Так что сейчас, кажется, самое время спросить: чему мы на самом деле научились у Гамильтона, и актуальны ли его идеи об альтруизме еще полвека назад?

Беда с социальными насекомыми

Самые крайние примеры альтруизма в природе происходят от социальных насекомых, таких как пчелы и муравьи, в которых рабочие бесконечно трудятся для своей колонии, но не размножаются.

Их существование давно озадачило биологов. Дарвин считал социальных насекомых потенциально «непреодолимой трудностью» для своей теории естественного отбора. В конце концов, как может работать отбор у стерильных людей?

До Гамильтона объяснения эволюции альтруизма и сотрудничества возвращались к аргументам, что это принесло пользу виду. Эта линия до сих пор используется в документальных фильмах о природе, и это заставляет эволюционных биологов съеживаться. Каждый раз.

Сотрудничество вполне может принести пользу видам или даже группе, но английский биолог Рональд Фишер в 30-х годах показал, что естественный отбор не работает таким образом. Когда то, что хорошо для группы, противоречит тому, что лучше для человека, интересы человека почти всегда побеждают.

Тем не менее, в 1960-х годах идеи о групповом отборе снова появлялись, перечитывая все старые ошибки.

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

Гамильтон придумал термин «инклюзивная физическая форма», который он определил своим общеизвестно непрозрачным образом:

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

Другими словами, рабочий муравей, возможно, не имеет сыновей или дочерей, но все же может родить тысячи братьев и сестер. И с точки зрения Дарвина, это так же хорошо, как и даже лучше, чем личное воспроизведение.

Род выбор

Идеи Гамильтона и их последующие украшения теперь часто называют «отбором родственников», термин, придуманный не Гамильтоном, а британским биологом-эволюционистом Джоном Мейнардом Смитом в 1964 году.

Мейнард Смит назвал британского биолога Дж.Б.С. Холдейна первым, кто придумал идею отбора родственников. Согласно слухам, Холдейн заявил в пабе: «Я бы положил свою жизнь на двоих братьев или восемь двоюродных братьев», ссылаясь на тот факт, что наши братья и сестры в среднем разделяют 50% наших генов, а кузены — 12, 5%.

Гамильтон оспаривал хитрость Холдейна. Фактически, одним из мотивов работы Гамильтона по инклюзивному фитнесу было то, что в работе Холдейна не удалось извлечь альтруизм из группового отбора.

К сожалению, отношения между Гамильтоном и Мейнардом Смитом — двумя наиболее влиятельными эволюционными биологами 20-го века — оставались напряженными до безвременной кончины Гамильтона в марте 2000 года.

Так что же такое правило Гамильтона?

Правило Гамильтона определяет условия, при которых ген, вызывающий альтруизм, может пользоваться всеобъемлющим преимуществом в фитнесе. Это происходит, когда выгоды, b, для связанного человека превышают затраты, c для альтруиста, обесцененные родством r между двумя:

Эволюционные биологи считают это уравнение столь же важным, как уравнение эквивалентности массы и энергии Эйнштейна (E = mc 2).

Гамильтон использовал в качестве примера эволюцию тревожных звонков у птиц. Птица, которая зовет в ответ на опасность, рискует привлечь внимание и, таким образом, потерять свою жизнь, в отличие от птицы, которая остается тихой.

Но, согласно правилу Гамильтона, такое самоотверженное поведение может развиваться, если выгоды для родственников, которые слышат крик и получают заблаговременное предупреждение (суммируются по количеству родственников и их тесной связи с квакером), перевешивают риски для сквокера.,

В последние 50 лет правило Гамильтона использовалось для объяснения множества странных в поведении животных и людей:

• почему мы заботимся о наших детях?
• почему львы образуют коалиции со своими братьями?
• почему молодые птицы висят вокруг гнездящихся братьев и сестер, а не размножаются?

Но выбор родства все еще держится?

В 2010 году в газете Nature, написанной Мартином Новаком, Кориной Тарнитой и Эдвардом О. Уилсоном — последним, когда-то верным сторонником отбора родственников и наставником для Гамильтона, — было прямо отказано в отборе родственников.

Новак и его соавторы утверждали, что родственный отбор был просто ненужной переформулировкой естественного отбора. Они утверждали, что альтруистические гены могут увеличиваться по частоте, даже если дающие и получающие альтруизм не связаны, просто потому, что люди, несущие гены альтруизма, преимущественно взаимодействуют друг с другом.

Однако они не отметили, что их «альтернативный» механизм развития альтруизма уже был определен Гамильтоном и увековечен Ричардом Докинзом как «эффект зеленой бороды».

Вообразите ген, который заставляет его носителя отрастить зеленую бороду. Такой ген будет распространяться, если те, кто его несут, преимущественно демонстрируют альтруизм другим людям с зеленой бородой.

Атака Новака, Тарниты и Уилсона на Гамильтона была почти повсеместно отклонена биологами-эволюционистами. В 2011 году более 100 выдающихся ученых подписали письмо с указанием концептуальных ошибок в документе и документированием необычайной прогностической силы парадигмы выбора рода.

Более хороший мир

Родственный отбор предоставляет одну из двух сильных сил, которые связывают все кооперативные предприятия. Другое взаимность. Думайте о первом как о «кровь гуще воды», а о втором как «вы поцарапаете мою спину, а я поцарапал вашу».

Мы очень полагаемся на взаимность в современном обществе, когда взаимность ликвидируется деньгами и другими валютами. Но родственный выбор по-прежнему придает общественной жизни большую форму.

Генетическое родство проникает в человеческие дела до самого их корня. От заботы о детях до непотистической коррупции, когда все остальное равно, мы отдаем предпочтение нашим родственникам по сравнению с теми, кто более отдаленно связан.

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

Наиболее убедительной иллюстрацией выбора родственных людей является работа канадских психологов-эволюционистов Мартина Дэйли и Марго Уилсона, обобщенная в их книге «Правда о Золушке: дарвинистский взгляд на родительскую любовь».

Подобно тому, как сказки предупреждали детей об опасности мачехи, так и современные данные о безнадзорности и насилии в детстве предполагают, что новый партнер родителей представляет высокий риск для ребенка. Это трудные факты, чтобы признать, потому что подавляющее большинство приемных родителей предоставляют чудесно поддерживающие дома детям.

Но ключ здесь в том, что родство делает с родителями. Генетическое родство чаще побуждает родителей продолжать усердную работу по воспитанию детей, не позволяет им бросать своих детей и защищает их от насильственных чрезмерных реакций.

Корни всех этих идей были впервые предложены 50 лет назад Гамильтоном, чья работа продолжает освещать происхождение нашего собственного поведения.

Источник

Молчание — золото: доказательство существования Гамильтонова цикла в графе

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

Заменив такую сложную конструкцию плоским графом, изоморфным исходному, получим задачу, которую далее рассмотрим в системе протоколов с нулевым разглашением.

Доказательство с нулевым разглашением

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

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

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

Доказательства с нулевым разглашением не являются доказательствами в математическом смысле этого термина, потому что есть некоторая небольшая вероятность, что обманом доказывающий сможет убедить проверяющего в ложном утверждении, хотя она и будет приближаться к 0 по мере увеличения числа этапов взаимодействия. С другой стороны, протокол абсолютно — а не только вероятно — гарантирует доказывающему, что проверяющему не разглашается ни намека на доказательство.

Как убедить кого-то в существовании Гамильтонова цикла, не раскрывая сам цикл

Пусть обеим сторонам известен некоторый граф , вершины которого пронумерованы от до . Необходимо доказать проверяющему существование цикла в G, который посещает каждую вершину ровно один раз.

На вход системе с нулевым разглашением мы подаем, где — положительное целое число, которое играет роль параметра безопасности и является количеством последовательных взаимодействий между сторонами: чем больше , тем больше уверенность проверяющего в доказательстве.

Дальнейшие шаги будут выполняться раз.

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

Проще говоря, мы заменяем исходный граф на его изоморфную копию.

Приватное состояние матрицы, доступное только доказывающей стороне. Публичное состояние матрицы, известное обеим сторонам.

Проверяющая сторона получает скрытую матрицу и делает выбор:

Попросить доказывающую сторону открытьсетки, соответствующих ребрам цикла Гамильтона. Процесс раскрытия симметричен: если показана запись в матрице, доказывающая сторона должна также показать запись.

C другой стороны, можно попросить доказывающую сторону открыть граф целиком.

Результат для проверяющей стороны в первом случае будет выглядеть, например, так:

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

Если проверяющий имел бы возможность обращаться к доказывающему только с первой просьбой, последний мог бы его легко обмануть, и, не зная Гамильтонова цикла исходного графа G, мог бы подменить его на другой с тем же количеством вершин, в котором сам знал бы цикл. Короче говоря, проверяющий, прося показать весь граф целиком, хочет убедиться в том, что он действительно изоморфен исходному.

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

Если все в порядке, проверяющая сторона принимает доказательство.

Если же первом случае проверяющая сторона увидит в открытых квадратах 0, она поймет, что доказывающая сторона не владеет знанием о цикле Гамильтона. Аналогично, по описанной выше причине, проверяющая сторона во втором случае тоже может понять, что доказывающий пытается ее обмануть, и в итоге она отклонит доказательство.

Почему это — нулевое знание?

Докажем, что проверяющая сторона, благодаря разговору, не может получить никакой «лишней» информации.

Может показаться, что в первом случае проверяющему предоставляется знание, благодаря которому он способен самостоятельно полностью узнать доказательство.

Это было бы верно, если бы он знал перестановку вершин, переводящую шифрованный граф в исходный, но поскольку за один раунд можно обратиться только с одной просьбой, и каждый раз изоморфная копия G меняется, то найти перестановку – дело безнадёжное – это значило бы решить проблему изоморфизма графов.

С другой стороны, ответ доказывающей стороны во втором случае, очевидно, не даст проверяющему никакой информации, так как, он получает изоморфную копию графа G , но мог бы и самостоятельно построить их сколько угодно, переставляя вершины исходного графа.

Что и требовалось доказать.

Заключение

Рассмотрим задачу аутентификации субъекта. Она состоит в проверке подлинности одной стороны другой, например, при входе в операционную систему пользователь может доказывать свою лигитимность вводом пароля.

Если решать ее таким простым способом, то гарантия того, что он не попадет в руки злоумышленников, не очень велика.

Конечно, при таком условии нельзя быть абсолютно уверенным в том, что аутентификация субъекта будет стопроцентной. Но проверяющий каждый раз может запросить любую часть информации, причём несколько раз. К тому же, можно использовать при этом Гамильтоновы циклы, получая относительно надёжную систему доступа, ведь вероятность в каждом раунде успешно обманывать проверяющую сторону равна 1/2^k, где k – число взаимодействий сторон.

Материал подготовлен при использовании литературы:

Manuel Blum «How to Prove a Theorem So No One Else Can Claim It«

Шнайер Б. Прикладная криптография, 2-е издание: протоколы, алгоритмы, исходные тексты на языке Си //Под редакцией ПВ Семьянова. М., Триумф. – 2002.

Источник