Abstract
In social choice and multi-agent systems, maximizing social welfare—the sum of individual utilities—is a primary objective. However, eliciting precise numerical utilities from agents is often impractical. This paper investigates the "implicit utilitarian" framework, where agents provide only ordinal rankings while underlying cardinal utilities remain hidden. We demonstrate that for a broad class of graph-based optimization problems, a simple Ordinal Greedy algorithm achieves solutions within a small constant factor of the absolute mathematical optimum. Our results cover constraints including degree bounds, component sizes, and attachment properties, providing robust guarantees for problems such as Matching, the Traveling Salesperson Problem, and Spanning Trees.
Introduction
A fundamental challenge in mechanism design is the difficulty humans face when assigning exact numerical values to their preferences. While an agent can easily rank alternatives, quantifying the magnitude of preference (e.g., "I prefer Alice 1.42 times more than Bob") is cognitively demanding and often inconsistent. The implicit utilitarian approach addresses this by asking: how much social welfare is lost when we only have access to rankings? This loss, termed "distortion," has been well-studied for simple voting, but this work extends the analysis to complex graph-based structures where agents form connections subject to specific constraints.
The ABC System Framework
To generalize our findings, we introduce ABC Systems, a framework that characterizes constraints based on three properties:
- Degree ($b$): Limits the number of connections an agent can maintain.
- Component Size ($c$): Restricts the maximum size of any connected group or cluster.
- Attachment ($A$): A structural property ensuring that if an edge is excluded, it is because the nodes are already connected via an alternative path (essential for spanning trees and planar graphs).
The Ordinal Greedy Algorithm
The core of our analysis focuses on the Ordinal Greedy Algorithm. Unlike standard greedy approaches that require global knowledge of edge weights, Ordinal Greedy operates locally. It selects an edge $(u, v)$ if it is "undominated"—meaning $u$ prefers $v$ over any other currently available neighbor, and $v$ reciprocates this preference.
Beyond its welfare guarantees, we show that the Ordinal Greedy solution is inherently pairwise stable. In the resulting network, no two agents would mutually benefit by breaking their current links to form a new connection, a critical property for the stability of real-world social networks.
Theoretical Methodology
Analyzing ordinal algorithms is traditionally difficult because they cannot compare the "strength" of preferences across different agents. We overcome this using a significant technical contribution: The Binary Reduction (Theorem 1). We prove that the worst-case distortion for the Ordinal Greedy algorithm always occurs when the hidden cardinal utilities are binary (0 or 1). This reduction allows the use of charging arguments to map the weight of the optimal solution to the greedy solution, simplifying the derivation of tight approximation bounds.
Key Results
Our analysis yields specific approximation ratios for various optimization problems. A "2-approximation," for instance, guarantees at least 50% of the maximum possible social welfare. Notably, for many problems, the Ordinal Greedy algorithm performs identically to an "Omniscient Greedy" algorithm that has full access to the hidden numerical values.
The results indicate that the algorithm is particularly effective on "sparse" problems. When constraints force the final graph to be sparse (such as a tree or planar graph), the ordinal information provided by rankings is highly effective at capturing the underlying utility structure.
Conclusion and Future Work
This work establishes that exact utility values are not a prerequisite for effective social welfare maximization in graph problems. While our results provide strong worst-case guarantees, several avenues for future research remain. First, we assume agents report their rankings truthfully; investigating strategic behavior and "truthful" ordinal mechanisms is a vital next step. Second, while we avoid assuming utilities follow a metric (like the triangle inequality), doing so could potentially improve the approximation factors. Finally, empirical testing could reveal that the average-case performance of Ordinal Greedy is even closer to the optimum than our theoretical bounds suggest.
Summary updated