function w = budget_voting(X)

  # usage: budget_voting(X)
  #
  # X is a matrix with voters as rows and candidates as columns; each entry
  # reflects a relative budget assigned by the voter to the candidate.
  #
  # The function returns a column vector of relative budget assignments for
  # each candidate such that the Manhattan distance is minimized and the
  # total budget is spent. The geometric median and, as a fallback, the
  # 1-dimensional median are used as tie-breaker.

  # Xt is X transposed, i.e. candidates as rows and voters as columns.
  Xt = transpose(X);

  # Xtn is Xn normalized such that each voter assigns a total budget of 1.
  Xtn = Xt ./ sum(Xt, 1);

  # d is the number of candidates.
  d = rows(Xtn);

  # avg is the arithmetic mean of all ballots.
  avg = mean(Xtn, 2);

  # Handle the 1-dimensional case:
  if rank(Xtn - avg) <= 1
    w = median(Xtn, 2);
    return
  endif

  # lb is the lower bound and ub is the upper bound for optimization.
  lb = zeros(d, 1);
  ub = ones(d, 1);

  # We use d^2 as delta (assuming this is high enough).
  delta = d.^2;

  # phi(x) is the function to minimize.
  phi = @(x) sum(delta.*sum(abs(x-Xtn), 1) + sqrt(sum((x-Xtn).^2, 1)), 2);

  # g(x) is zero when the total budget is spent.
  g = @(x) sum(x) - 1;

  # g_grad_t is the gradient of g as a row vector.
  g_grad_t = @(x) ones(1, d);

  # maxiter is the maximum number of iterations for calculation.
  maxiter = 1000;

  # Minimize phi(x) under condition g(x) = 0:
  w = sqp(avg, phi, {g, g_grad_t}, [], lb, ub, maxiter);
end
