PaperlayerView exact revision on arXiv

Source-linked AI summary

Sum of Us: Strategyproof Selection from the Selectors

Noga Alon, Felix Fischer, Ariel D. Procaccia, Moshe Tennenholtz

arXiv:0910.4699v1cs.GTcs.AI

TL;DR

The paper asks how to select k popular or trusted agents in directed networks when agents can misreport their outgoing edges and care only about being selected. It develops randomized strategyproof selection and proves that deterministic strategyproof selection cannot achieve finite approximation for 1 ≤ k ≤ n−1, while randomized selection has ratio at most four and approaches one as k grows.

  • Problem

    The problem is to select k agents maximizing total indegree when agents can misreport outgoing edges to improve their own chance of selection.

    Source: §1 · p. 2

  • Method

    The paper studies deterministic selection and designs randomized m-RP, which partitions agents and selects high-indegree agents using incoming edges from other subsets.

    Source: §1 · p. 4

  • Results

    At most four: randomized strategyproof selection achieves this approximation ratio and approaches one as k grows, whereas no deterministic strategyproof mechanism has a finite ratio for 1 ≤ k ≤ n−1.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Randomization permits finite-ratio strategyproof selection where deterministic strategyproof selection cannot provide any finite approximation.

    Source: §1 · p. 4

    For randomized strategyproof 1-selection, the upper bound is four while the lower bound is two; the paper conjectures a 2-approximation exists.

    Source: §5 · p. 12

Abstract

from arXiv · show

We consider directed graphs over a set of n agents, where an edge (i,j) is taken to mean that agent i supports or trusts agent j. Given such a graph and an integer k\leq n, we wish to select a subset of k agents that maximizes the sum of indegrees, i.e., a subset of k most popular or most trusted agents. At the same time we assume that each individual agent is only interested in being selected, and may misreport its outgoing edges to this end. This problem formulation captures realistic scenarios where agents choose among themselves, which can be found in the context of Internet search, social networks like Twitter, or reputation systems like Epinions. Our goal is to design mechanisms without payments that map each graph to a k-subset of agents to be selected and satisfy the following two constraints: strategyproofness, i.e., agents cannot benefit from misreporting their outgoing edges, and approximate optimality, i.e., the sum of indegrees of the selected subset of agents is always close to optimal. Our first main result is a surprising impossibility: for k \in {1,...,n-1}, no deterministic strategyproof mechanism can provide a finite approximation ratio. Our second main result is a randomized strategyproof mechanism with an approximation ratio that is bounded from above by four for any value of k, and approaches one as k grows.

1 Introduction

The paper models selection in directed networks as choosing k agents with the highest total indegree, while agents care only about being selected and can misreport outgoing edges. It shows deterministic strategyproof selection cannot achieve finite approximation for 1 ≤ k ≤ n−1, while randomized strategyproof selection can achieve a ratio at most four that approaches one as k grows.

1 Introduction

  • The model treats agents as alternatives too: an edge from one agent to another represents approval, trust, or support, and agents value only their own selection.The objective is the selected agents’ total indegree; Internet search and social networks motivate the setting.Source: §1 · p. 2
  • Approximation is used to admit strategyproof mechanisms, not to address computational complexity, because maximizing total indegree is tractable.The paper situates this work in approximate mechanism design without money and relates the setting to selection games, leader election, and reputation systems.Source: §1 · p. 3
  • For 1 ≤ k ≤ n−1, no deterministic strategyproof k-selection mechanism has a finite approximation ratio.The result rules out even mechanisms that always avoid excluding the only agent with positive indegree.Source: §1 · pp. 3–4
  • Random m-Partition randomly divides agents into m subsets and selects roughly k/m high-indegree agents per subset using incoming edges from other subsets.The mechanism is strategyproof for every m.Source: §1 · p. 4
  • A suitable m gives randomized strategyproof selection an approximation ratio of at most four, approaching one as k grows.The paper also proves a randomized strategyproof lower bound of 1+Ω(1/k^2), equal to two when k = 1.Source: §1 · p. 4
  • Randomized group-strategyproof k-selection has approximation ratio at least (n−1)/k, essentially no better than selecting k agents uniformly at random.Uniform random selection is group strategyproof and has ratio n/k.Source: §1 · p. 4

2 The Model

The model uses directed graphs on agents and selects a k-subset. Agents value their own selection, while the mechanism seeks to maximize the selected set’s total indegree subject to strategyproofness or group strategyproofness.

2 The Model

  • A graph has agents as vertices, and a deterministic k-selection mechanism maps each graph to a k-subset of agents.A randomized mechanism instead returns a probability distribution over k-subsets.Source: §2 · pp. 4–5
  • An agent’s utility is one if selected and zero otherwise, so agents care only about their own selection.Deterministic mechanisms are a special case of randomized ones that choose an outcome with probability one.Source: §2 · pp. 4–5
  • Strategyproofness requires that an agent cannot benefit by changing its reported outgoing edges; group strategyproofness bars a coalition from jointly misreporting so all gain.The group-strategyproofness definition allows a deviation where no coalition member loses, strengthening the stated impossibility result.Source: §2 · p. 5
  • The optimization target is the sum of selected agents’ indegrees, and mechanisms are evaluated by how closely they approximate its maximum.Indegree is the number of incoming edges.Source: §2 · p. 5

3 Deterministic Mechanisms

For every 1 ≤ k < n, no deterministic strategyproof k-selection mechanism has a finite approximation ratio. A parity argument on star graphs establishes the impossibility, alongside boundary cases and a voting interpretation.

3 Deterministic Mechanisms

  • For k=n, selecting everyone is the sole mechanism and is optimal; allowing selection of at most k agents instead permits a deterministic strategyproof finite-ratio mechanism selecting at most two agents for k≥2.The at-most-k variant differs from the requirement to select exactly k agents.Source: §3 · pp. 5, 7
  • For k=1, removing agent 2’s outgoing edge leaves agent 2 as the only agent with positive degree, while the mechanism still selects agent 1.The selected subset then has zero incoming edges despite an available subset with positive incoming edges, so the approximation ratio is infinite.Source: §3 · p. 5
  • For k=n−1, the question is whether strategyproofness can ensure that an agent receiving the only incoming edges is not the one left unselected.The paper gives a negative answer, even when each agent has at most one outgoing edge, and relates the result to a voting game where one member is eliminated.Source: §3 · p. 6
  • For every 1 ≤ k < n, no deterministic strategyproof k-selection mechanism gives a finite approximation ratio.The result holds even when attention is restricted to graphs where each agent has at most one outgoing edge.Source: §3 · p. 6
  • On star graphs centered at agent n, every nonempty binary vector must select n, while strategyproofness pairs each other agent’s selections across vectors differing in its coordinate.These constraints make the total selection count odd by counting n separately, but even because every graph selects exactly k agents, a contradiction.Source: §3 · pp. 6–7

4 Randomized Mechanisms

Randomization permits finite-approximation strategyproof selection, and random partitioning yields guarantees approaching optimality as k grows. Requiring group strategyproofness is much more restrictive: random selection is optimal up to a small gap.

4.1 SP Randomized Mechanisms

  • A deterministic two-group partition mechanism is strategyproof but has no finite approximation ratio when all edges lie within groups.Random partitioning avoids fixing groups independently of the input while retaining the cross-group selection idea.Source: §4.1 · p. 7
  • m-RP randomly partitions agents and selects roughly k/m agents per group using only incoming edges from other groups, making it strategyproof.The number chosen per group is rounded up or down to total k; if the initial selections fall short, remaining agents are chosen uniformly at random.Source: §4.1 · p. 8
  • The 2-RP mechanism has approximation ratio four, while m-RP also achieves 1+O(1/k^(1/3)) for an appropriate growing m.For k=1, the analysis gives a lower bound of two and an upper bound of four; the authors conjecture a ratio of two is achievable.Source: §4.1 · pp. 8–10
  • A strategyproof mechanism exists with approximation ratio at most four for every k, and the ratio approaches one as k grows.Choosing the best m for each k gives a bound of min{4,1+O(1/k^(1/3))}.Source: §4.1 · p. 9
  • No randomized strategyproof k-selection mechanism can achieve an approximation ratio below 1+Ω(1/k^2).For k=1, the paper gives an explicit lower bound of two.Source: §4.1 · pp. 9–10

4.2 GSP Randomized Mechanisms

  • Under group strategyproofness, random k-subset selection achieves ratio n/k, while no randomized mechanism can do better than (n−1)/k.Thus random selection is optimal up to this small gap, and the lower bound also holds for coalitions of size at most two.Source: §4.2 · p. 10

5 Discussion

The discussion examines how payments, utility assumptions, edge weights, and stronger truthfulness requirements affect the results. It identifies a practical conference-review application and leaves the single-winner randomized strategyproofness gap open.

5 Discussion

  • Payments can implement the optimal solution truthfully, but even paying only pivotal nonselected agents may require paying everyone in cases such as a clique.The paper states that no truthful payment scheme does better.Source: §5 · p. 11
  • With utility for selected neighbors weighted by β, the random-partition guarantee extends to social welfare; for β≥1, optimal selection is strategyproof.When β is positive but small, a variation on random partitioning achieves a social-welfare approximation close to one even for k=1.Source: §5 · p. 11
  • The main positive result extends to weighted edges, but maximizing incoming weight can misrepresent reputation when missing edges mean no knowledge and low weights mean distrust.Source: §5 · p. 11
  • In conference review, three reviewers per paper make maximizing total incoming score equivalent to maximizing average score, so m-RP can form a truthful program.Source: §5 · p. 11
  • The paper's randomized mechanisms are universally strategyproof, although its stated definition requires only strategyproofness in expectation.Universal strategyproofness means truthfulness for every fixed random outcome; the authors note this makes Theorem 4.1 stronger than stated.Source: §5 · p. 11
  • For randomized strategyproof selection with k=1, the upper bound is four and the lower bound is two; achieving two remains a conjecture.Source: §5 · p. 12
  • For the alternative objective of maximizing minimum indegree, deterministic strategyproof impossibility still applies, while randomized strategyproof guarantees remain unclear.Source: §5 · p. 12

A Proof of Theorem 4.1

The proof analyzes an optimal k-set under random partitions, first using a two-way split and then a k^(1/3)-way split. It uses concentration bounds to establish the later part of the theorem.

A Proof of Theorem 4.1

  • For n = 8 and k = 4, Figure 3 illustrates the optimal set split across two subsets of the partition.The optimal set shown is {1,2,3,4}.Source: Figure 3 · p. 14
  • A random two-way partition places an expected OPT/2 edges incoming to the optimal set across the two subsets.The proof counts edges into the optimal set whose endpoints lie in different subsets.Source: A Proof of Theorem 4.1 · p. 14
  • For the k^(1/3)-way partition, Zi counts the other optimal-set agents in the same subset as agent i.The proof uses these counts to analyze the mechanism's expected indegrees.Source: A Proof of Theorem 4.1 · p. 15
  • Chernoff bounds control the probabilities used in the concentration argument, and convergence of a series with terms exp(−Θ(x^2))·Θ(x) establishes (8).The proof handles (9) similarly and then completes Theorem 4.1.Source: A Proof of Theorem 4.1 · p. 17

B The Edge Scan Mechanism

For k ≥ 2, allowing selection of at most k agents permits a strategyproof mechanism with a bounded approximation ratio. The Edge Scan Mechanism uses two scans to select agents targeted by edges.

B The Edge Scan Mechanism

  • For k ≥ 2, selecting at most k agents allows a strategyproof mechanism with a bounded approximation ratio.The section notes that selecting an agent with an incoming edge suffices when such an edge exists.Source: B The Edge Scan Mechanism · p. 18
  • The at-most-k result is presented against the earlier impossibility of bounded approximation for deterministic strategyproof k-selection.The mechanism's two scans provide the section's construction.Source: B The Edge Scan Mechanism · p. 18
  • The Edge Scan Mechanism orders agents lexicographically and scans from both ends to find edge targets.Each scan selects the agent pointed to by the first edge it encounters.Source: B The Edge Scan Mechanism · p. 18

The Edge Scan Mechanism.

The Edge Scan Mechanism partitions edges by direction relative to the lexicographic ordering and chooses a target in each direction. It is strategyproof and guarantees an incoming-edge selection when the graph has an edge, but may have a poor approximation ratio.

The Edge Scan Mechanism.

  • The mechanism separates edges into those pointing right and those pointing left in the agent ordering.Each scan uses one of these edge classes.Source: The Edge Scan Mechanism · p. 18
  • Each directional scan selects an edge target by an extreme-index rule, with a fallback agent if that edge class is empty.The left-to-right scan uses minimum indices; the reverse scan uses maximum indices.Source: The Edge Scan Mechanism · p. 18
  • An agent cannot improve its selection chance by changing outgoing edges: adding edges targets another agent, while removing them is too late once its vote is considered.This is the mechanism's stated strategyproofness argument.Source: The Edge Scan Mechanism · p. 18
  • When the graph has an edge, the mechanism selects an agent with an incoming edge and has a finite approximation ratio that can be as bad as Ω(nk).The two scan winners can coincide, leaving a singleton that cannot be deterministically completed to size two in a strategyproof way.Source: The Edge Scan Mechanism · p. 18

C The Sliding Partition Mechanism

The appendix discusses a randomized Sliding Partition Mechanism designed to improve the upper bound for k = 1. The proposed improvement fails, though its counterexample may be useful for future work on Conjecture 4.3.

C The Sliding Partition Mechanism

The Sliding Partition Mechanism.

The Sliding Partition Mechanism builds an eliminated set by repeatedly choosing the remaining agent with minimum indegree from that set, then selects the sole agent left. It is strategyproof, but its approximation ratio has a lower bound of Ω(n^1/5).

The Sliding Partition Mechanism.

  • Starting with S empty, the mechanism repeatedly adds an agent of minimum indegree from S until |S|=n−1, then selects the only agent outside S.Source: The Sliding Partition Mechanism · p. 19
  • The mechanism is strategyproof because only eliminated agents' outgoing edges are used, and eliminated agents can no longer be selected.Source: The Sliding Partition Mechanism · p. 19
  • On the one-edge graph where 2-RP's analysis is tight, Sliding Partition gives a 2-approximation; the source agent is eliminated before its target with probability 1/2.Source: The Sliding Partition Mechanism · p. 19
  • A bad instance is a tree where agent 1 has n^3/5 supporters, each with n^2/5 incoming edges, while all other agents have indegree zero.Source: The Sliding Partition Mechanism · p. 19
  • With high probability, agent 1 has fewer than n^2/5 incoming edges from S at t0; if fewer than n^2/5 agents in T were eliminated, agent 1 is eliminated next.At t0, agents outside {1}∪T are eliminated before the remaining agents in T.Source: The Sliding Partition Mechanism · p. 19
  • The Sliding Partition Mechanism's approximation ratio is at least Ω(n^1/5), and optimizing the example's parameters can strengthen this lower bound.Source: The Sliding Partition Mechanism · p. 19
Loading 0910.4699v1…