English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider ordinal approximation algorithms for a broad class of utilitymaximization problems for multi-agent systems. In these problems, agents haveutilities for connecting to each other, and the goal is to compute amaximum-utility solution subject to a set of constraints. We represent these asa class of graph optimization problems, including matching, spanning treeproblems, TSP, maximum weight planar subgraph, and many others. We study theseproblems in the ordinal setting: latent numerical utilities exist, but we onlyhave access to ordinal preference information, i.e., every agent specifies anordering over the other agents by preference. We prove that for the large classof graph problems we identify, ordinal information is enough to computesolutions which are close to optimal, thus demonstrating there is no need toknow the underlying numerical utilities. For example, for problems in thisclass with bounded degree $b$ a simple ordinal greedy algorithm always producesa ($b+1$)-approximation; we also quantify how the quality of ordinalapproximation depends on the sparsity of the resulting graphs. In particular,our results imply that ordinal information is enough to obtain a2-approximation for Maximum Spanning Tree; a 4-approximation for Max WeightPlanar Subgraph; a 2-approximation for Max-TSP; and a 2-approximation forvarious Matching problems.

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