Минимизируйте транзакционные издержки для урегулирования долгов в пуле

Question

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

Например, предположим, что 3 человека, A, B и C.

• Человек A должен заплатить 100
• Человек B должен получить 50 * 1008 $.*
• Лицо C должно получить $ 50

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

С учетом этих расходов оптимальным решением будет

• Лицо А переводит 100 долларов США Лицу B
• Лицо Б переводит50 долларов США на человека C

Это позволяет погасить все долги с транзакционными издержками, равными 2. Как я могу обобщить это?

Все, что я смог найти в поиске, - это упрощение цепных долгов (лицо, которое должночеловек B, который должен человеку C, поэтому человек Aдолжен человек C).

Ближайшее, что я нашел, это это , но оно не требует затрат для транзакций.

Backstory (если кто-либозаинтересован):

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

Answer 1

Я нашел другое, более простое решение.Мы все еще говорим о стоимости перевода, которая пропорциональна сумме перевода.Вы можете построить простой граф с таким же количеством узлов, как и у людей, и запустить сетевой симплексный алгоритм.Пример Python:

import networkx as nx

G = nx.DiGraph()
G.add_node('A', demand=-100) # A has to send 100
G.add_node('B', demand=50) # B will receive 50
G.add_node('C', demand=50) # C will receive 50

G.add_edge('A', 'B', weight=1)
G.add_edge('A', 'C', weight=5)
G.add_edge('B', 'A', weight=1)
G.add_edge('B', 'C', weight=1)
G.add_edge('C', 'A', weight=2)
G.add_edge('C', 'B', weight=2)

print nx.network_simplex(G)

вывод (150, {'A': {'C': 0, 'B': 100}, 'C': {'A': 0, 'B': 0}, 'B': {'A': 0, 'C': 50}})

Answer 2

После того, как @j_random_hacker объяснил эту проблему в комментариях np-hard, я потерял всякую надежду найти красивое решение и решил сделать то, что работает.

Следуя предложению @ user3386109, также в комментарияхЯ решил использовать minpath для решения проблемы.Поэтому я начал с использования [алгоритма Флойда-Варшалла], чтобы найти минимальные затраты на получение денег от человека к другому за каждую пару.Это дает матрицу минимальной стоимости перевода денег от человека в строке к человеку в столбце.Я также применил модификацию (она доступна в статье Википедии в разделе «Восстановление пути»), чтобы получить матрицу, которая приводит к следующему узлу (следующему прыжку, фактическому человеку, которому вы должны отправить свои деньги, если хотите связаться с человеком в столбце с помощьюминимальные затраты) для человека в строке, чтобы перевести деньги этому человеку в столбце.

Пример инициализированных матриц и результат после запуска алгоритма (важные элементы, которые изменились, отмечены красной точкой):

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

Затем мы выбираем кого-то, кто должен деньги в списке долгов, и для каждого человека, который должен получить деньги, мы создаем копии списка долгов и матрицы транзакций и моделируем транзакциюмаксимальная сумма денег между этими двумя людьми (если А должен заплатить 100, а С должен получить только 50, то максимальная - 50).Матрица транзакций изменяется путем увеличения всех транзакций в minpath для этих двух человек на сумму перевода.Стоимость увеличивается, если мы увеличили элемент, который ранее был нулевым.Затем мы называем рекурсию.Если список долгов достигает 0, решение найдено, глобальная минимальная стоимость обновляется, а возвращаемая стоимость равна 0.

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

Этот алгоритм казался правильным, но проблема все еще была!

В следующем примере:

• Лицо А должно заплатить 40 $
• Человек B должен заплатить 40 $
• Человек C должен заплатить 20 $
• Человек D должен получить 100 $

Алгоритм, как сейчас, делает A, B, C каждый делает перевод в D. Фактически лучшим способом было бы выбрать один из A, B или C, чтобы перевести все деньги в D только одним платежом.

В этом примереЛица A, B и C имеют одинаково высокую стоимость перевода в D, и следующий шаг для получения денег для всех - это перейти непосредственно в D. Однако оптимальным решением было бы сделать перевод каждоговсе свои деньги одному человеку и переведите их D сразу.Алгоритм не может распознать, что, поскольку кто-то уже сделал перевод человеку D, стоимость этой транзакции равна 0, и поэтому мы должны использовать этот новый путь.Чтобы решить эту проблему, я включил в рекурсию матрицу затрат и матрицу путей, в начале рекурсии мы установили все затраты на переводы, которые уже были сделаны в этой ветви рекурсии, равными 0, и запустили алгоритм Флойда-Варшалла.снова.Рекурсия использует эти матрицы вместо глобальных и передает их.Конечно, это означает умножение сложности на V ^ 3, но я нашел единственный способ решить эту проблему.

Кажется, что алгоритм работает сейчас, но я, вероятно, буду продолжать пытаться улучшить его, особенно в области читабельности кода.Полный код доступен по адресу: Мой проект gitlab, внутри папки с вычислениями

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

Answer 3

В случае, если банк взимает процент с переведенной суммы, ваша задача - найти минимальный максимальный расход .

В вашем графике должно быть 5 слоев.

(direction)
    |    Source layer:               S
    |                            /   |    \
    |    Exchange:           A  ---  B  ---  C  (complete graph)
    |                            \   |    / 
    V    Sink           :            T 

Источник подключен к узлам A, B, C ... Емкость S -> A - это то, сколько A должен заплатить, и 0, если A не владеет деньгами.Стоимость ребра равна 0.

В обменном слое A, B, C ... все связаны друг с другом (полный график).

Емкость A -> B бесконечна, и стоимость - это то, сколько вы должны заплатить после перевода 1 доллара из A в B (одинаково для всех пар).

Узлы подключены краковина.Емкость A -> Sink - это то, сколько A получит, и 0, если A не получит деньги.Стоимость фронта равна 0.

Запустите алгоритм максимального потока с минимальными затратами на приведенном выше графике от корневого источника к корневому стоку, такой как Edmonds-Karp + отмена цикла.Возможно, вам лучше найти библиотеку (например, Boost Graph Library для C ++), а не реализовывать алгоритмы самостоятельно.