Auction algorithm in Python
Solves the assignment problem by simulating bidding among persons for objects with epsilon-scaled prices.
- File
auction_algorithm.py, 72 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/auction-algorithm/. The authors are listed in prov/YB4A74.jsonl.
from collections import deque
from typing import Callable, NamedTuple, Optional
class Auction(NamedTuple):
assignment: Optional[list[int]] # assignment[i] = object of person i, None if infeasible
value: Optional[int] # total benefit, None if infeasible
prices: list[int] # final prices, in units of benefit / (n + 1)
bids: int # number of bids made
def auction(
benefit: list[list[Optional[int]]],
on_bid: Optional[Callable[[int, int, int, Optional[int]], None]] = None,
) -> Auction:
"""Maximum-benefit assignment by Bertsekas' auction algorithm.
benefit is an n by n matrix: person i values object j at benefit[i][j], an
integer, or None if person i may not take object j. The graph is bipartite
and weighted: persons on one side, objects on the other. Benefits are
multiplied by n + 1 and the bid increment is epsilon = 1, so the result is
optimal, not only within n * epsilon. Forbidden pairs get a benefit so low
that an optimal assignment uses one only if no feasible assignment exists;
then assignment and value are None. For minimum cost, negate the costs.
on_bid(person, object, new price, outbid person or None) is called per bid.
With C the largest difference between two finite benefits: O(n^2 C + n^2)
bids without forbidden pairs, O(n) time each; O(n^2) space.
"""
n = len(benefit)
if any(len(row) != n for row in benefit):
raise ValueError("benefit must be a square matrix")
finite = [a for row in benefit for a in row if a is not None]
low = min(finite, default=0)
high = max(finite, default=0)
forbidden = low - n * (high - low) - 1 # worse than any feasible assignment
price = [0] * n # @line L1
owner = [-1] * n
assigned = [-1] * n
scaled = [ # @line L2
[(n + 1) * (forbidden if a is None else a) for a in row] for row in benefit
]
queue = deque(range(n)) # @line L3
bids = 0
while queue: # @line L4
i = queue.popleft()
row = scaled[i]
best_j = 0 # @line L5
best = row[0] - price[0]
for j in range(1, n):
if row[j] - price[j] > best:
best_j, best = j, row[j] - price[j]
second = best # @line L6
if n > 1:
second = max(row[j] - price[j] for j in range(n) if j != best_j)
price[best_j] += best - second + 1 # @line L7
loser = owner[best_j]
if loser >= 0: # @line L8
assigned[loser] = -1
queue.append(loser)
owner[best_j] = i # @line L9
assigned[i] = best_j
bids += 1
if on_bid is not None:
on_bid(i, best_j, price[best_j], loser if loser >= 0 else None)
if any(benefit[i][assigned[i]] is None for i in range(n)): # @line L10
return Auction(None, None, price, bids)
value = sum(benefit[i][assigned[i]] for i in range(n)) # type: ignore[misc]
return Auction(assigned, value, price, bids)
test_auction_algorithm.py 112 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/auction-algorithm/. The authors are listed in prov/YB4A74.jsonl.
import itertools
import random
import unittest
from fractions import Fraction
from typing import Optional
from auction_algorithm import auction
def brute(benefit: list[list[Optional[int]]]) -> Optional[int]:
"""Largest total benefit over all feasible permutations, None if there is none."""
n = len(benefit)
best: Optional[int] = None
for perm in itertools.permutations(range(n)):
if any(benefit[i][perm[i]] is None for i in range(n)):
continue
total = sum(benefit[i][perm[i]] for i in range(n)) # type: ignore[misc]
if best is None or total > best:
best = total
return best
def check(test: unittest.TestCase, benefit: list[list[Optional[int]]]) -> None:
n = len(benefit)
result = auction(benefit)
want = brute(benefit)
test.assertEqual(result.value, want)
if want is None:
test.assertIsNone(result.assignment)
return
a = result.assignment
assert a is not None
test.assertEqual(sorted(a), list(range(n)))
test.assertEqual(sum(benefit[i][a[i]] for i in range(n)), want) # type: ignore[misc]
# 1-complementary slackness in scaled units: each person is within 1 of its best.
for i in range(n):
scaled = [
None if x is None else (n + 1) * x for x in benefit[i]
]
got = scaled[a[i]] - result.prices[a[i]] # type: ignore[operator]
for j in range(n):
if scaled[j] is not None:
test.assertGreaterEqual(got, scaled[j] - result.prices[j] - 1)
class TestAuction(unittest.TestCase):
def test_worked_example(self) -> None:
trace: list[tuple[int, int, int, Optional[int]]] = []
r = auction([[10, 5, 8], [9, 2, 3], [7, 6, 4]], lambda *b: trace.append(b))
self.assertEqual(r.assignment, [2, 0, 1])
self.assertEqual(r.value, 23)
self.assertEqual(r.prices, [25, 9, 18])
self.assertEqual(trace, [(0, 0, 9, None), (1, 0, 25, 0), (2, 1, 9, None), (0, 2, 18, None)])
# Dual value sum of prices plus profits, in original units, is within 1 of the primal.
n = 3
p = [Fraction(x, n + 1) for x in r.prices]
b = [[10, 5, 8], [9, 2, 3], [7, 6, 4]]
dual = sum(p) + sum(max(b[i][j] - p[j] for j in range(n)) for i in range(n))
self.assertEqual(dual, Fraction(93, 4))
def test_empty(self) -> None:
r = auction([])
self.assertEqual((r.assignment, r.value, r.bids), ([], 0, 0))
def test_single(self) -> None:
self.assertEqual(auction([[-7]]).assignment, [0])
self.assertEqual(auction([[-7]]).value, -7)
def test_no_perfect_matching(self) -> None:
# Both persons may take only object 0: Hall's condition fails.
r = auction([[5, None], [7, None]])
self.assertIsNone(r.assignment)
self.assertIsNone(r.value)
self.assertIsNone(auction([[None]]).assignment)
def test_forbidden_but_feasible(self) -> None:
r = auction([[100, None, None], [1, 1, None], [1, 1, 1]])
self.assertEqual(r.assignment, [0, 1, 2])
self.assertEqual(r.value, 102)
def test_ties_and_negative(self) -> None:
check(self, [[0, 0, 0], [0, 0, 0], [0, 0, 0]])
check(self, [[-5, -1], [-2, -9]])
def test_minimum_cost_by_negation(self) -> None:
cost = [[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 9, 4]]
r = auction([[-c for c in row] for row in cost])
self.assertEqual(r.value, -13)
self.assertEqual(r.assignment, [1, 0, 2, 3])
def test_not_square(self) -> None:
with self.assertRaises(ValueError):
auction([[1, 2]])
def test_random(self) -> None:
rng = random.Random(1988)
for _ in range(700):
n = rng.randint(0, 6)
hi = rng.choice([1, 3, 10, 1000])
density = rng.choice([0.0, 0.0, 0.2, 0.5])
benefit = [
[None if rng.random() < density else rng.randint(-hi, hi) for _ in range(n)]
for _ in range(n)
]
check(self, benefit)
if __name__ == "__main__":
unittest.main()
What the next level needs
- the tests did not run in this build