Kavli Affiliate: Felix Fischer
| First 5 Authors: Javier Cembrano, Felix Fischer, Max Klimm, ,
| Summary:
We study mechanisms that select a subset of the vertex set of a directed
graph in order to maximize the minimum indegree of any selected vertex, subject
to an impartiality constraint that the selection of a particular vertex is
independent of the outgoing edges of that vertex. For graphs with maximum
outdegree $d$, we give a mechanism that selects at most $d+1$ vertices and only
selects vertices whose indegree is at least the maximum indegree in the graph
minus one. We then show that this is best possible in the sense that no
impartial mechanism can only select vertices with maximum degree, even without
any restriction on the number of selected vertices. We finally obtain the
following trade-off between the maximum number of vertices selected and the
minimum indegree of any selected vertex: when selecting at most~$k$ vertices
out of $n$, it is possible to only select vertices whose indegree is at least
the maximum indegree minus $lfloor(n-2)/(k-1)rfloor+1$.
| Search Query: ArXiv Query: search_query=au:”Felix Fischer”&id_list=&start=0&max_results=10