Abstract: We consider ordinal approximation algorithms for a broad class of utility maximization problems for multi-agent systems. In these problems, agents have utilities for connecting to each other, and the goal is to compute a maximum-utility solution subject to a set of constraints. We represent these as a class of graph optimization problems, including matching, spanning tree problems, TSP, maximum weight planar subgraph, and many others. We study these problems in the ordinal setting: latent numerical utilities exist, but we only have access to ordinal preference information, i.e., every agent specifies an ordering over the other agents by preference. We prove that for the large class of graph problems we identify, ordinal information is enough to compute solutions which are close to optimal, thus demonstrating there is no need to know the underlying numerical utilities. For example, for problems in this class with bounded degree $b$ a simple ordinal greedy algorithm always produces a $(b + 1)$-approximation; we also quantify how the quality of ordinal approximation depends on the sparsity of the resulting graphs. In particular, our results imply that ordinal information is enough to obtain a 2-approximation for Maximum Spanning Tree; a 4-approximation for Max Weight Planar Subgraph; a 2-approximation for Max-TSP; and a 2-approximation for various Matching problems.
Introduction
A fundamental challenge in social choice and multi-agent systems is the gap between what we want to optimize—total social welfare—and what we can actually measure. Traditionally, maximizing social welfare requires "cardinal utilities," where every agent assigns a precise numerical value to every possible connection. However, humans are notoriously poor at providing these numbers, whereas they excel at providing "ordinal preferences" (e.g., "I prefer Alice over Bob").
This paper, presented at AAAI-18, addresses the question: How much social welfare is lost when we only have access to rankings? The researchers demonstrate that for a wide class of graph-based optimization problems, ordinal data is sufficient to reach near-optimal outcomes without ever knowing the underlying numerical utilities.
The ABC Framework and Ordinal Greedy Algorithm
The authors introduce a framework called ABC Systems to categorize constraints in graph optimization:
- A (Attachment): General structural requirements (e.g., the graph must be a tree or planar).
- B (Bounded Degree): Each agent (node) can have at most $b$ connections (edges).
- C (Component Size): Connected groups of agents cannot exceed a size $c$.
To solve these problems using only ordinal data, the authors analyze the Ordinal Greedy Algorithm. Unlike standard greedy algorithms that require global knowledge of edge weights, the Ordinal Greedy algorithm picks "undominated" edges—those where both endpoints rank each other as their top available choice. This local process ensures that decisions are made based solely on relative rankings rather than absolute utility values.
Key Theoretical Insights
Several critical insights emerge from the mathematical analysis of this framework:
- The Power of Binary Weights: The authors prove that the worst-case performance for ordinal algorithms occurs when edge weights are binary (0 or 1). This simplifies the analysis of hidden utilities into a counting problem of how many "good" edges are selected.
- Sparsity as a Welfare Guarantee: The "sparser" the problem's constraints (e.g., requiring a tree structure), the better the ordinal algorithm performs. The lack of numerical data is less detrimental when the resulting graph naturally has fewer edges.
- Pairwise Stability: Solutions found by the Ordinal Greedy algorithm are inherently "pairwise stable," meaning no two agents would mutually benefit by breaking current connections to form a new link with each other.
- No Metric Requirement: Unlike many previous approaches, these results do not rely on the triangle inequality. The approximation bounds hold for any arbitrary set of hidden utilities.
Results and Approximation Ratios
The paper establishes specific approximation ratios ($\alpha$), defined as the ratio of Optimal Welfare to Ordinal Welfare. A ratio of 1 represents a perfect match to the cardinal optimum.
As shown in the table above, the Ordinal Greedy algorithm provides a 2-approximation for Maximum Spanning Tree, Max-TSP, and $b$-Matching. This means that even with only ranking information, we can guarantee at least 50% of the maximum possible social welfare. For more complex constraints like Planar Subgraphs, the algorithm still maintains a constant 4-approximation.
Discussion and Future Directions
While these results provide strong worst-case guarantees, several avenues for future research remain. First, the current model assumes agents report their preferences truthfully; investigating mechanisms that are robust against strategic lying is a natural next step. Additionally, while these deterministic bounds are tight in the worst case, the authors suggest that randomized algorithms might offer improved expected approximation ratios. Finally, empirical studies could reveal how closely the Ordinal Greedy algorithm approaches the optimum in real-world scenarios, where performance is often significantly better than worst-case theoretical bounds suggest.
Summary updated