Utilitarians Without Utilities: Maximizing Social Welfare for Graph Problems Using Only Ordinal Preferences


  • Ben Abramowitz Rensselaer Polytechnic Institute
  • Elliot Anshelevich Rensselaer Polytechnic Institute




Ordinal Preferences, Approximation Algorithms, Matching, Greedy, TSP, Graph Algorithms


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.




How to Cite

Abramowitz, B., & Anshelevich, E. (2018). Utilitarians Without Utilities: Maximizing Social Welfare for Graph Problems Using Only Ordinal Preferences. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.11453



AAAI Technical Track: Game Theory and Economic Paradigms