Web and Internet Economics - 18th International Conference, WINE 2022, Troy, NY, USA, December 12-15, 2022, Proceedings
Web and Internet Economics - 18th International Conference, WINE 2022, Troy, NY, USA, December 12-15, 2022, Proceedings
复制标题
网络和互联网经济学 - 第 18 届国际会议，WINE 2022，美国纽约州特洛伊，2022 年 12 月 12-15 日，会议记录
DOI：
10.1007/978-3-031-22832-2_11
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Cembrano J
中科院分区：
文献类型：
--
作者：
Cembrano J
我们研究的机制，选择一个有向图的顶点集的子集，以最大限度地提高任何选定的顶点的最小入度，受到公正性约束，一个特定的顶点的选择是独立的，该顶点的传出边缘。对于最大出度的图，我们给出了一个选择最多个顶点的机制，并且只选择入度至少是图的最大入度减1的顶点。然后，我们表明，这是最好的可能性，在这个意义上，没有公正的机制只能选择顶点的最大程度，即使没有任何限制所选择的顶点的数量。我们最终得到以下的权衡之间的最大数量的顶点选择和任何选定的顶点的最小入度：当选择在mostkvertices出n，它是可能的，只选择顶点的入度至少是最大入度减去。
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 outdegreed, we give a mechanism that selects at mostvertices 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 mostkvertices out ofn, it is possible to only select vertices whose indegree is at least the maximum indegree minus.