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);

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

  # eudists(x) contains the Euclidean distances between x and each vote.
  eudists = @(x) sqrt(sum((x-Xtn).^2, 1));

  # eudist(x) is the sum of all Euclidean distances between x and each vote.
  eudist = @(x) sum(eudists(x), 2);

  # eudist_grad(x) is the gradient of eudist(x) as a column vector,
  # used to aid optimization.
  eudist_grad = @(x) sum((x-Xtn) ./ eudists(x), 2);

  # The geometric median minimizes the sum of all Euclidean distances:
  g = sqp(mean(Xtn, 2), {eudist, eudist_grad});

  # mandist(x) contains the Manhattan distances between x and each vote
  # plus a tie-breaker (weighted 1/2) in favor of the geometric median.
  mandist = @(x) sum(sum(abs(x-Xtn), 1), 2) + sum(abs(x-g), 1)/2;

  # mandist_grad(x) is the gradient of mandist(x) as a column vector,
  # used to aid optimization.
  mandist_grad = @(x) sum(sign(x-Xtn), 2) + sign(x-g)/2;

  # excess(x) is the sum of the candidates' budgets minus 1.
  excess = @(x) sum(x, 1) - 1;

  # excess_grad_t(x) is the gradient of excess(x) as a row vector,
  # used to aid optimization.
  excess_grad_t = @(x) ones(1, rows(x));

  # The solution minimizes the Manhattan distance (including the tie-breaker)
  # under the condition that the sum of the candidates' budgets is 1.
  w = sqp(g, {mandist, mandist_grad}, {excess, excess_grad_t});
end
