How Should We Allocate Desks for PhD Students? A Simple Algorithm

Author

Zikai Li

Published

May 26, 2025

1 Motivation

In my department at UChicago, we have what we call the “desk problem” for PhD students. In a given academic year, we have a fixed number of desks (resources) to allocate to students (accounts) over multiple terms (periods). We always have more demand than supply, and students value desks differently depending on the term (e.g., the Winter Quarter seems to be the most popular). Students also have different levels of “entitlement” based on their year in the program: the department wants to prioritize desk access for students earlier in their program. Our current approach is a bit ad hoc: we guarantee desks for students in their first two years if they request them, and then allocate the remaining desks with a lottery. Students can specify the terms in which they want a desk, but it seems we don’t differentiate between terms in the allocation process or even between students that request desks in one vs. multiple terms.

The allocation process also doesn’t allow students to meaningfully express relative preferences across terms. Even if most people prefer a desk in Winter over Fall, some students’ preference can be stronger than others’ (e.g, some may have heavy course loads in Winter while others may just want to hang out with friends). The result, predictably, is that our administrative staff is subject to intense lobbying from students every summer when the re-allocation happens and they often have to make various manual adjustments.

This problem is an instance of a more general class of resource allocation problems where we have multiple periods with different resource utilization patterns and demands. We want to allocate fixed but renewable resources fairly and efficiently while respecting entitlements as much as possible. Different periods may have different effective values or costs for the resources due to demand fluctuations, operational constraints, or strategic considerations. In a private market, users may bid different prices for resources in different periods. Under central planning, we can mimic this by allowing users to reveal different “willingness to pay” or “value” for resources in different periods within the constraints of their overall entitlement.

2 Problem Statement

We manage \(N\) accounts over \(T\) periods with fixed resource capacities \(X_1, X_2, \ldots, X_T\). We assume capacities are known and fixed in advance and, for now, that they are divisible (fractional allocations allowed). Each account \(i\)

  • has some amount of currency \(\text{Cur}_i\) that determines its relative entitlement to the total resources and
  • requests resources \(r_{it}\) for period \(t \in \{1, 2, \ldots, T\}\).

Different periods may have different demand levels, utilization rates, and/or costs. To reflect varying effective value (or cost) of resources across periods, we can convert requests in period \(t\) into “reference period equivalent” units using weights \(w_t\).

By default, we can compute weights based on relative total demands for each period:

  • Find the period with minimum total demand: \(t^* = \arg\min_t \sum_i r_{it}\)
  • Set \(w_{t^*} = 1\) (reference period)
  • For other periods: \(w_t = \frac{\sum_i r_{it}}{\sum_i r_{it^*}}\)

We can also specify weights manually. The idea is that periods with higher demand/cost should get higher weights as resources in those periods are “scarcer.”

We can divide the allocation process into two steps: in the first step, we allocate as much as possible in a fair and efficient manner (as defined below); in the second step, if there is any leftover capacity in any period, we can distribute it to accounts with excess demand in proportion to their relative entitlements, and repeat this process until the amount of leftover capacity is smaller than a prespecified threshold.

Our objective in the first step is to allocate resources \(a_{it}\) to each account \(i\) in each period \(t\) to maximize total amount of resources we can allocate under the following “desirable” constraints:

  • Per-period capacity constraints
  • Each account’s entitlement derived from their currency
  • Requested amounts (we do not want to allocate more than requested unless we have excess capacity)
  • The relative preference structure of requests across periods (i.e., if an account requests more in one period than another, its allocations should reflect that ratio).

3 Variables and Constraints

Let total resource currency \(R = \sum_i \text{Cur}_i\). \(\text{Cur}_i\) can be any non-negative number (e.g., priority weight in our desk problem, historical revenue in a cloud computing context, etc.). Account \(i\)’s share is thus \(s_i = \frac{\text{Cur}_i}{R}\). Without cross-period coupling, entitlement for period \(t\) for account \(i\) would be \[E_{it} = s_i \cdot X_t\]

With differential pricing, form a combined weighted entitlement (in reference period equivalent units):

\[E^{(w)}_i = s_i \cdot \sum_{t=1}^{T} w_t \cdot X_t\]

Our decision variables are allocations \(a_{it}\) for account \(i\) in period \(t\). This comes from the requests \(r_{it}\) and and a fullfillment scalar. Define proportional fulfillment scalar \(\lambda_i\) (\(0 \leq \lambda_i \leq 1\)) such that:

\[a_{it} = \lambda_i \cdot r_{it} \quad \forall t \in \{1, 2, \ldots, T\}\]

This enforces within-account relative preferences over periods by keeping constant the ratio between allocations between any two periods:

\[(a_{i1} : a_{i2} : \cdots : a_{iT}) = (r_{i1} : r_{i2} : \cdots : r_{iT})\]

We can then write the consumption of entitlement by account \(i\) as: \[ C^{(w)}_i = \sum_{t=1}^{T} w_t \cdot a_{it} = \lambda_i \sum_{t=1}^{T} w_t \cdot r_{it}, \] which is subject to the following constraint in the first step of our allocation: \[ \lambda_i \sum_{t=1}^{T} w_t \cdot r_{it} \leq s_i \sum_{t=1}^{T} w_t \cdot X_t. \] This says that an account’s allocation, priced by weights for each period, should not exceed its entitlement expressed in terms of the same weights.

This gives us an upper bound on \(\lambda_i\) from entitlement:

\[ \lambda_i \le \min\left(1,\; \frac{s_i \sum_{t=1}^{T} w_t X_t}{\sum_{t=1}^{T} w_t r_{it}}\right) \quad \text{if } \sum_{t=1}^{T} w_t r_{it} > 0;\; \text{else } \lambda_i = 0 \]

We are also subject to per-period capacity constraints:

\[\sum_i a_{it} = \sum_i \lambda_i r_{it} \leq X_t \quad \forall t \in \{1, 2, \ldots, T\}\]

Additionally, to ensure fairness, we enforce that accounts with identical entitlements and identical requests receive identical treatment:

\[ \lambda_i = \lambda_j \quad \text{if } \text{Cur}_i = \text{Cur}_j \text{ and } r_{it} = r_{jt} \; \forall t \in \{1, 2, \ldots, T\} \]

When there are accounts with identical entitlements and requests, the linear programming solver may have multiple optimal solutions and will choose one somewhat arbitrarily. The fairness constraint prevents it from choosing different allocation ratios for identical accounts when multiple optimal solutions exist.

4 Objective in the First Step

Our objective in the first step is simple: we want to maximize total allocated resources in reference period equivalent units. This is equivalent to maximizing total fulfilled requests weighted by their respective weights:

\[ \text{Maximize} \quad \sum_i \sum_{t=1}^{T} w_t \cdot r_{it} \cdot \lambda_i = \sum_i \lambda_i \sum_{t=1}^{T} w_t \cdot r_{it} \]

This is a linear program with \(N\) variables \(\lambda_i\) and \(T\) global capacity constraints plus individual upper bounds.

5 Allocation of Leftover Capacity in the Second Step

If there is any leftover capacity in any period after the first step, we can distribute it to accounts with excess demand in proportion to their relative entitlements. We thus relax the ratio constraint for accounts that have excessive demand in a period that is under-subscribed overall. We repeat this process until convergence.

Let \(a^{(1)}_{it}\) denote the allocation to account \(i\) in period \(t\) from the first step. We define the set of under-subscribed periods as:

\[ T_{\text{leftover}} = \left\{t \mid \sum_i a^{(1)}_{it} < X_t\right\} \]

In each iteration \(k\) of the second step, we solve an allocation problem for the remaining capacity. Let \(b^{(k)}_{it}\) be the additional allocation in iteration \(k\). The total final allocation becomes \(a^{(1)}_{it} + \sum_k b^{(k)}_{it}\).

Our objective in each iteration of the second step is to maximize total weighted additional allocation in under-subscribed periods:

\[ \text{Maximize} \quad \sum_{i} \sum_{t \in T_{\text{leftover}}^{(k)}} w_t \cdot b^{(k)}_{it} \]

This is subject to the following constraints:

  • remaining capacity: Additional allocations cannot exceed remaining capacity \[ \sum_i b^{(k)}_{it} \leq X_t - \sum_i \left(a^{(1)}_{it} + \sum_{j=1}^{k-1} b^{(j)}_{it}\right) \quad \forall t \in T_{\text{leftover}}^{(k)} \]

  • request amounts: Total allocation cannot exceed original request \[ a^{(1)}_{it} + \sum_{j=1}^{k} b^{(j)}_{it} \leq r_{it} \quad \forall i, t \in T_{\text{leftover}}^{(k)} \]

  • entitlement to remaining capacity: Additional weighted allocation should “respect” each account’s entitlement to the remaining capacity \[ \sum_{t \in T_{\text{leftover}}^{(k)}} w_t \cdot b^{(k)}_{it} \leq s_i \sum_{t \in T_{\text{leftover}}^{(k)}} w_t \cdot \left(X_t - \sum_j \left(a^{(1)}_{jt} + \sum_{l=1}^{k-1} b^{(l)}_{jt}\right)\right) \quad \forall i \]

We repeat this process until convergence, which occurs when either (1) leftover capacity is smaller than a prespecified threshold (e.g., 1% of total capacity) in all periods, or (2) no accounts have excess demand in periods with significant leftover capacity.

6 Algorithm Outline

  1. Inputs: account IDs, currency amounts, requests matrix, capacities, weights, convergence threshold
  2. Step 1 - Proportional Allocation:
    • Compute revenue shares and entitlement caps
    • Solve LP to maximize weighted allocation subject to proportionality and entitlement constraints
    • Record allocations and identify periods with leftover capacity
  3. Step 2 - Iterative Leftover Allocation (if applicable):
    • While leftover capacity > threshold × capacity and excess demand exists in leftover periods:
      • Identify current leftover periods and remaining capacities
      • Check for accounts with unmet demand in those periods
      • If both conditions met: solve LP to allocate remaining capacity respecting Step 2 entitlements
      • Update allocations and repeat
    • Stopping when leftover capacity falls below threshold or no excess demand remains
  4. Output: Combined allocations in detailed and summary formats with iteration tracking

7 Implementation

The implementation uses PuLP, and the code is available here.

from allocation_alg import *

First, let’s look at a case with four periods and four accounts, each with different entitlements but equal requests.

print("\n" + "="*60)

account_ids_test1 = ["A", "B", "C", "D"]
cur_test1 = [400, 300, 200, 100]  # varying entitlements
# equal requests across all periods for all accounts
requests_test1 = [
    [50, 50, 50, 50],  # Account A
    [50, 50, 50, 50],  # Account B
    [50, 50, 50, 50],  # Account C
    [50, 50, 50, 50],  # Account D
]
capacities_test1 = [120, 120, 120, 120]

result_test1 = allocate_resource(
    account_ids_test1, cur_test1, requests_test1, capacities_test1)

print("======== summary ==========")

print("Entitlement shares:")
for s in result_test1.allocations_summary['entitlement_share']:
    print(f"  {s:.3f}")

print("Weights:")
print("  " + ", ".join(f"{w}" for w in result_test1.weights))

print("Final capacity used:")
print("  " + ", ".join(f"{u:.1f}" for u in result_test1.capacity_used))

print("Final utilization:")
print("  " + ", ".join(f"{u:.1%}" for u in result_test1.utilization))

print(f"Step 1 allocation: {result_test1.step1_allocated:.2f}")
print(f"Step 2 allocation: {result_test1.step2_allocated:.2f}")

print("\nFinal allocations by account and period:")
for i, account in enumerate(account_ids_test1):
    allocations = [
        result_test1.allocations_summary.iloc[i][f'alloc_period_{t+1}']
        for t in range(4)
    ]
    allocations_str = ", ".join(f"{a:.1f}" for a in allocations)
    print(
        f"  Account {account}: [{allocations_str}] "
        f"(requested: [50.0, 50.0, 50.0, 50.0])"
    )

============================================================
========== step 1 ==========
Step 1 capacity used: ['120.0', '120.0', '120.0', '120.0']
========== step 2 ==========
Iteration 1:
Leftover capacity is less than 1.0% in all periods. Step 2 completed
Step 2 completed after 1 iterations.
======== summary ==========
Entitlement shares:
  0.400
  0.300
  0.200
  0.100
Weights:
  1.0, 1.0, 1.0, 1.0
Final capacity used:
  120.0, 120.0, 120.0, 120.0
Final utilization:
  100.0%, 100.0%, 100.0%, 100.0%
Step 1 allocation: 480.00
Step 2 allocation: 0.00

Final allocations by account and period:
  Account A: [48.0, 48.0, 48.0, 48.0] (requested: [50.0, 50.0, 50.0, 50.0])
  Account B: [36.0, 36.0, 36.0, 36.0] (requested: [50.0, 50.0, 50.0, 50.0])
  Account C: [24.0, 24.0, 24.0, 24.0] (requested: [50.0, 50.0, 50.0, 50.0])
  Account D: [12.0, 12.0, 12.0, 12.0] (requested: [50.0, 50.0, 50.0, 50.0])

Next, let’s see what happens with different capacities and different requests.

account_ids = ["A","B","C"]
cur = [120, 80, 100]
# 4 periods, different capacities and weights
requests_4p = [
    [40, 60, 50, 70],  # Account A
    [70, 50, 80, 40],  # Account B  
    [30, 90, 45, 60],  # Account C
]
capacities_4p = [120, 120, 100, 110]  # dif capacity each period

result_4p = allocate_resource(account_ids, cur, requests_4p, capacities_4p)
print("======== summary ==========")
print(f"Weights: {result_4p.weights}")
print(f"Capacities: {result_4p.capacities}")
print(f"Final capacity used: {[f'{u:.1f}' for u in result_4p.capacity_used]}")
print(f"Final utilization: {[f'{u:.1%}' for u in result_4p.utilization]}")
print(f"Step 1 allocation: {result_4p.step1_allocated:.2f}")
print(f"Step 2 allocation: {result_4p.step2_allocated:.2f}")

print("\nAllocations:")
result_4p.allocations_summary[[
    'account_id', 'entitlement_share', 'lambda', 'req_period_1', 'alloc_period_1',
    'req_period_2', 'alloc_period_2', 'req_period_3', 'alloc_period_3', 
    'req_period_4', 'alloc_period_4']]
========== step 1 ==========
Step 1 capacity used: ['79.3', '120.0', '100.0', '107.1']
========== step 2 ==========
Iteration 1:
Accounts with (nontrivial) excess demand: [0, 1, 2]
Iteration 2:
Accounts with (nontrivial) excess demand: [1]
Iteration 3:
Leftover capacity is less than 1.0% in all periods. Step 2 completed
Step 2 completed after 3 iterations.
======== summary ==========
Weights: [1.0, 1.4285714285714286, 1.25, 1.2142857142857142]
Capacities: [120, 120, 100, 110]
Final capacity used: ['120.0', '120.0', '100.0', '110.0']
Final utilization: ['100.0%', '100.0%', '100.0%', '100.0%']
Step 1 allocation: 505.70
Step 2 allocation: 44.30

Allocations:
account_id entitlement_share lambda req_period_1 alloc_period_1 req_period_2 alloc_period_2 req_period_3 alloc_period_3 req_period_4 alloc_period_4
0 A 0.400000 0.805229 40 40.0 60 48.313726 50 40.261438 70 58.141834
1 B 0.266667 0.434462 70 50.0 50 21.723114 80 34.756982 40 17.378491
2 C 0.333333 0.555146 30 30.0 90 49.963161 45 24.981580 60 34.479675

Here account B has less “currency” to compete with others for resources, but it still gets allocated quite a bit in absolute amounts. That’s because it indicates it has a strong preference for resources in period 1, a period with the least total demand. This is the kind of outcome we’d like to see happen more with differential pricing.

Now let’s try using this algorithm to allocate desks for PhD students. Desks are indivisible, but we can still treat them as continuous. When someone’s allocated more than one desk, we will of course only given them one. When it’s a fractional number smaller than 1, we can use that as the probability in a non-uniform lottery.

# 20 accounts with specific entitlements: 
# 10 accounts with cur=3, 10 accounts with cur=6
np.random.seed(60637) # there shouldn't be randomness but just in case
account_ids_test2 = [f"User{i+1:02d}" for i in range(20)]
cur_test2 = [3] * 10 + [6] * 10  # first 10 accounts get 3, next 10 get 6

# generate requests where accounts spend all their currency
# w/ clustering in period 2 (higher demand in period 2)
requests_test2 = []
for i in range(20):
    total_budget = cur_test2[i]
    
    # clustering in period 2: more accounts prefer period 2
    # use different allocation patterns based on account preferences
    if i < 5:  # first 5 accounts prefer period 1
        period_weights = [0.7, 0.2, 0.1]
    elif i < 15:  # next 10 accounts prefer period 2 (clustering)
        period_weights = [0.15, 0.7, 0.15]
    else:  # last 5 accounts prefer period 3
        period_weights = [0.1, 0.2, 0.7]
    
    requests = [total_budget * w for w in period_weights]
    
    requests_test2.append(requests)

capacities_test2 = [5, 5, 5] 

result_test2 = allocate_resource(
    account_ids_test2, cur_test2, requests_test2, capacities_test2)

print("\nAccounts with cur=3 (Users 01-10):")
low_entitlement = result_test2.allocations_summary.iloc[:10]
for _, row in low_entitlement.iterrows():
    account = row['account_id']
    lambda_val = row['lambda']
    total_req = sum(row[f'req_period_{t+1}'] for t in range(3))
    total_alloc = sum(row[f'alloc_period_{t+1}'] for t in range(3))
    period_reqs = [row[f'req_period_{t+1}'] for t in range(3)]
    period_allocs = [row[f'alloc_period_{t+1}'] for t in range(3)]
    print(f"  {account}: λ={lambda_val:.3f}, "
          f"req={[f'{r:.1f}' for r in period_reqs]}, "
          f"alloc={[f'{a:.1f}' for a in period_allocs]}")

print("\nAccounts with cur=6 (Users 11-20):")
high_entitlement = result_test2.allocations_summary.iloc[10:]
for _, row in high_entitlement.iterrows():
    account = row['account_id']
    lambda_val = row['lambda']
    total_req = sum(row[f'req_period_{t+1}'] for t in range(3))
    total_alloc = sum(row[f'alloc_period_{t+1}'] for t in range(3))
    period_reqs = [row[f'req_period_{t+1}'] for t in range(3)]
    period_allocs = [row[f'alloc_period_{t+1}'] for t in range(3)]
    print(f"  {account}: λ={lambda_val:.3f}, req={[f'{r:.1f}' for r in period_reqs]}, "
          f"alloc={[f'{a:.1f}' for a in period_allocs]}")

print(f"\nPeriod 2 clustering:")
period2_requests = [req[1] for req in requests_test2]
period2_total = sum(period2_requests)
print(f"  Period 2 total demand: {period2_total:.1f}, "
      f"(vs Period 1: {sum(req[0] for req in requests_test2):.1f}, "
      f"Period 3: {sum(req[2] for req in requests_test2):.1f})")
========== step 1 ==========
Step 1 capacity used: ['3.3', '5.0', '4.5']
========== step 2 ==========
Iteration 1:
Accounts with (nontrivial) excess demand: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
Iteration 2:
Leftover capacity is less than 1.0% in all periods. Step 2 completed
Step 2 completed after 2 iterations.

Accounts with cur=3 (Users 01-10):
  User01: λ=0.198, req=['2.1', '0.6', '0.3'], alloc=['0.4', '0.1', '0.1']
  User02: λ=0.198, req=['2.1', '0.6', '0.3'], alloc=['0.4', '0.1', '0.1']
  User03: λ=0.198, req=['2.1', '0.6', '0.3'], alloc=['0.4', '0.1', '0.1']
  User04: λ=0.198, req=['2.1', '0.6', '0.3'], alloc=['0.4', '0.1', '0.1']
  User05: λ=0.198, req=['2.1', '0.6', '0.3'], alloc=['0.4', '0.1', '0.1']
  User06: λ=0.140, req=['0.4', '2.1', '0.4'], alloc=['0.1', '0.3', '0.1']
  User07: λ=0.140, req=['0.4', '2.1', '0.4'], alloc=['0.1', '0.3', '0.1']
  User08: λ=0.140, req=['0.4', '2.1', '0.4'], alloc=['0.1', '0.3', '0.1']
  User09: λ=0.140, req=['0.4', '2.1', '0.4'], alloc=['0.1', '0.3', '0.1']
  User10: λ=0.140, req=['0.4', '2.1', '0.4'], alloc=['0.1', '0.3', '0.1']

Accounts with cur=6 (Users 11-20):
  User11: λ=0.093, req=['0.9', '4.2', '0.9'], alloc=['0.2', '0.4', '0.1']
  User12: λ=0.093, req=['0.9', '4.2', '0.9'], alloc=['0.2', '0.4', '0.1']
  User13: λ=0.093, req=['0.9', '4.2', '0.9'], alloc=['0.2', '0.4', '0.1']
  User14: λ=0.093, req=['0.9', '4.2', '0.9'], alloc=['0.2', '0.4', '0.1']
  User15: λ=0.093, req=['0.9', '4.2', '0.9'], alloc=['0.2', '0.4', '0.1']
  User16: λ=0.163, req=['0.6', '1.2', '4.2'], alloc=['0.3', '0.2', '0.7']
  User17: λ=0.163, req=['0.6', '1.2', '4.2'], alloc=['0.3', '0.2', '0.7']
  User18: λ=0.163, req=['0.6', '1.2', '4.2'], alloc=['0.3', '0.2', '0.7']
  User19: λ=0.163, req=['0.6', '1.2', '4.2'], alloc=['0.3', '0.2', '0.7']
  User20: λ=0.163, req=['0.6', '1.2', '4.2'], alloc=['0.3', '0.2', '0.7']

Period 2 clustering:
  Period 2 total demand: 40.5, (vs Period 1: 20.2, Period 3: 29.2)

Looking at accounts with cur=6, we can see that those requesting desks in the third quarter have a higher total probability of having a desk in at least one quarter than those who put most of their eggs in the second quarter. This indicates that the algorithm is working as intended: the supply of desks, even though fixed in absolute terms, is scarcer in quarter 2 relative total demand, and we want to encourage those that can shift their demand to other quarters to do so, with the reward being a higher total probability of having a desk in at least one quarter.