TL;DR
This paper introduces a fast primal-dual heuristic for "fair" combinatorial optimization, using the Generalized Gini Index (GGI) to ensure balanced outcomes across different agents or criteria. By leveraging Lagrangian decomposition, the authors' algorithm achieves near-optimal results (within 0.3% of the true optimum) while running orders of magnitude faster than commercial integer programming solvers.
What Problem Does This Paper Address?
In classic combinatorial optimization—think of the Traveling Salesman Problem or finding a perfect matching in a graph—we typically aim to maximize the sum of weights. However, the sum is a "blind" aggregator: it doesn't care if one agent gets a massive utility while everyone else gets zero. In multi-agent systems or multi-criteria decision-making, this lack of "fairness" is a dealbreaker.
To fix this, researchers use inequality measures like the Generalized Gini Index (GGI). GGI rewards "balanced" distributions where resources are spread more equitably. The catch? GGI is non-linear. While you can use mathematical tricks to turn a GGI-based problem into a linear integer program (IP), standard solvers like CPLEX or Gurobi struggle as the problem size grows, often taking hours to solve even relatively small instances. The authors address this computational bottleneck.
Methods
The authors propose a heuristic called AlterOpt, based on a primal-dual approach using Lagrangian decomposition.
- Linearization: They start with a known technique to linearize the GGI objective using "Lorenz components," which represent the cumulative values of the $k$ smallest utilities.
- Lagrangian Relaxation: They relax the difficult fairness constraints, moving them into the objective function with Lagrangian multipliers ($\lambda$).
- The Iterative Loop: The algorithm alternates between two steps:
- Primal Step: For a fixed set of multipliers, the problem simplifies into a standard weighted version of the original combinatorial problem (e.g., a standard maximum weight matching). This can often be solved very efficiently using specialized algorithms like the Blossom algorithm.
- Dual Step: They update the multipliers using a projected sub-gradient method. A key innovation here is an efficient $O(n^3)$ method for projecting these multipliers onto "capped simplices," which keeps the search space constrained and computationally tractable.
Datasets
The authors evaluated their algorithm on two primary types of problems:
- Fair Assignment: Bipartite matching problems where $n$ tasks are assigned to $n$ agents.
- Fair General Matching: Matching problems on complete graphs.
They generated "hard" random instances for these problems. In these instances, agents' preferences are positively correlated (meaning many agents want the same items), which makes finding a "fair" solution significantly more difficult than in uncorrelated cases.
Key Insights and Ideas
- Weights as Fairness Adjusters: The algorithm essentially treats the dual variables as "modified weights." By iteratively adjusting these weights, the algorithm "nudges" the standard solver to pick edges that contribute to a fairer global distribution.
- Efficiency through Structure: Instead of treating the fair optimization as a generic black-box IP, the authors exploit the fact that the underlying combinatorial problem (like matching) has a structure that is easy to solve once the fairness constraints are relaxed.
- Theoretical Guarantees: The paper provides an optimality condition (Theorem 1) and a theoretical approximation ratio (Theorem 2) that bounds how far the standard "max-sum" solution can be from the "fair" optimal solution.
Key Results
The numerical results demonstrate a massive disparity in performance between the proposed heuristic and exact solvers:
- Speed: For a matching problem with 100 vertices (
v10-50), CPLEX took nearly 30,000 seconds (over 8 hours) to find the optimum. TheAlterOptheuristic found a solution in just 2.48 seconds. - Quality: Despite being a heuristic, the "optimality gap" (the distance from the true optimal value) was remarkably small—typically less than 0.3% for assignment problems and less than 0.1% for general matching.
- Scalability: While CPLEX's runtime increased exponentially with problem size, the authors' method scaled much more gracefully, appearing to increase roughly linearly.
Limitations and Future Work
The current study focuses on base problems that are solvable in polynomial time (like matching). However, many combinatorial problems are NP-hard even in their standard "max-sum" versions (like the Traveling Salesman Problem). The authors acknowledge that integrating their heuristic with approximation algorithms for these NP-hard problems is a necessary next step.
Additionally, they suggest exploring other linearization techniques and different update rules for the Lagrangian multipliers to further tighten the theoretical bounds and improve performance on even more complex constraints.
Summary updated