Chapter 4: Algorithmic Mechanism Design - The Trilemma - Algorithimic Game Theory with Python

We have a new challenge. Suppose you are selling Cloud Storage on a server.

Total Capacity: 100 GB ( $W$ )
Bidders: $n$ companies. Each wants a specific amount of space ( $w_i$ ) and has a private value ( $v_i$ ) for it.

This is the famous Knapsack Problem. We want to fit the most valuable combination of files into the limited space.

The Impossible Triangle (The Trilemma)¶

We want an auction that is:

DSIC (Truthful): People tell the truth about their value.
Optimal: We get the absolute maximum total value possible.
Polynomial Time (Fast): It runs quickly, even with thousands of bidders.

Bad News: We can’t have all three. The Knapsack Problem is NP-Hard. Solving it perfectly takes too long (exponential time).

The Solution: Approximation¶

Since we can’t be perfect and fast, we compromise. We design an algorithm that is fast and “pretty good” (Approximate).

The Greedy Heuristic: Instead of checking every combination, we look at the “Bang for the Buck” (Value per GB).

Calculate density $d_i = \frac{v_i}{w_i}$ for everyone.
Sort bidders from highest density to lowest.
Let them in one by one until the server is full.

Does this work? Let’s race the “Perfect” algorithm against the “Greedy” one.

import time

# --- SETUP ---
# Capacity of our Server (e.g., 50 GB)
CAPACITY = 50

# Bidders: (Name, Value $, Size GB)
# Notice: 'C' has high value ($60) but is huge (50GB). 
# 'A' and 'B' are smaller but have good value density.
bidders = [
    {'name': 'A', 'value': 30, 'size': 10},
    {'name': 'B', 'value': 20, 'size': 10},
    {'name': 'C', 'value': 60, 'size': 50},  # Big, valuable item
    {'name': 'D', 'value': 40, 'size': 20},
    {'name': 'E', 'value': 15, 'size': 15},
]

# --- ALGORITHM 1: THE OPTIMAL (SLOW) WAY ---
# This checks every possible subset (Recursive/DP)
def get_optimal_value(capacity, items, n):
    if n == 0 or capacity == 0:
        return 0
    
    # If item is too big, skip it
    if items[n-1]['size'] > capacity:
        return get_optimal_value(capacity, items, n-1)
    
    else:
        # Return max of: 
        # (1) Including the item
        # (2) Excluding the item
        include = items[n-1]['value'] + get_optimal_value(capacity - items[n-1]['size'], items, n-1)
        exclude = get_optimal_value(capacity, items, n-1)
        return max(include, exclude)

# --- ALGORITHM 2: THE GREEDY (FAST) WAY ---
# Sorts by Value/Size ratio
def run_greedy_auction(capacity, items):
    # 1. Calculate Density (Value / Size)
    for item in items:
        item['density'] = item['value'] / item['size']
    
    # 2. Sort by Density (High to Low)
    sorted_items = sorted(items, key=lambda x: x['density'], reverse=True)
    
    current_weight = 0
    total_value = 0
    winners = []
    
    for item in sorted_items:
        if current_weight + item['size'] <= capacity:
            winners.append(item['name'])
            current_weight += item['size']
            total_value += item['value']
            
    return total_value, winners

# --- RUN COMPARISON ---

print("--- Knapsack Auction Simulation ---")
print(f"Server Capacity: {CAPACITY} GB")

# Run Optimal
start_opt = time.time()
opt_val = get_optimal_value(CAPACITY, bidders, len(bidders))
end_opt = time.time()
print(f"\n[Optimal Algo]: Max Possible Value = ${opt_val} (Time: {end_opt - start_opt:.5f}s)")

# Run Greedy
start_greedy = time.time()
greedy_val, greedy_winners = run_greedy_auction(CAPACITY, bidders)
end_greedy = time.time()

print(f"\n[Greedy Algo]: Value Found = ${greedy_val} (Time: {end_greedy - start_greedy:.5f}s)")
print(f"Winners: {greedy_winners}")
print(f"Performance: {(greedy_val/opt_val)*100:.1f}% of Optimal")

--- Knapsack Auction Simulation ---
Server Capacity: 50 GB

[Optimal Algo]: Max Possible Value = $90 (Time: 0.00023s)

[Greedy Algo]: Value Found = $90 (Time: 0.00008s)
Winners: ['A', 'B', 'D']
Performance: 100.0% of Optimal

Analysis: The “Price” of Simplicity¶

In the simulation above, you might see that the Greedy Algorithm didn’t find the perfect $60 solution (Item C). Instead, it might have filled the knapsack with smaller items (A, B, D) for a total of $90. Wait... actually, in this specific case, Greedy often wins!

But consider a case where Greedy fails:

Item A: Value 2, Size 1 (Density 2)
Item B: Value 50, Size 50 (Density 1)
Capacity: 50

Greedy picks A (density 2). Now capacity is 49. Item B doesn’t fit. Total value: $2. Optimal picks B. Total value: $50.

The Fix: To prevent catastrophic failures, our Greedy Mechanism has a final check:

Run the Greedy sort.
Compare that result against just picking the single most valuable item that fits.
[cite_start]Return the better of the two[cite: 234].

[cite_start]Theorem: This modified Greedy algorithm guarantees at least 50% of the optimal value[cite: 243].

Why do we care? Because the Greedy algorithm is Monotone (getting a higher value or smaller size never hurts your chances). [cite_start]Because it is monotone, Myerson’s Lemma applies, and we can calculate payments that make this truthful[cite: 255]. We traded perfection for speed, but we kept truthfulness!