Utilitarians Without Utilities: Maximizing Social Welfare for Graph Problems using only Ordinal Preferences - Full Version

Ben Abramowitz, Elliot Anshelevich

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:

  1. Degree ($b$): Limits the number of connections an agent can maintain.
  2. Component Size ($c$): Restricts the maximum size of any connected group or cluster.
  3. 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.

Comparison of approximation ratios for Ordinal Greedy vs. Omniscient Greedy and Best Known results.

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

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.
BibTeX
@misc{abramowitz2017utilitarians,
  author = {Ben Abramowitz and Elliot Anshelevich},
  title = {{Utilitarians Without Utilities: Maximizing Social Welfare for Graph Problems using only Ordinal Preferences - Full Version}},
  year = {2017},
  eprint = {1711.10588},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1711.10588},
}
Figure