The semi-random graph process is a single player game in which the player is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is presented to the player independently and uniformly at random. The player then adaptively selects a vertex $v$, and adds the edge $uv$ to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. In this paper, we introduce a natural generalization of this game in which $k$ random vertices $u_1, \ldots, u_k$ are presented to the player in each round. She needs to select one of the presented vertices and connect to any vertex she wants. We focus on the following three monotone properties: minimum degree at least $\ell$, the existence of a perfect matching, and the existence of a Hamiltonian cycle.

翻译：半随机图形进程是一个单玩家游戏, 玩家最初在其中展示了一个以美元为顶点的空图。 在每一回合中, 向玩家独立、 统一地随机地展示一个顶点$u$u$ 。 玩家随后随机地选择一个顶点$v$, 并在图形中添加边缘 $uv$ 。 对于一个固定的单调图形属性, 玩家的目标是在尽可能短的回合中强制图形以高概率满足此属性。 在本文中, 我们引入了这个游戏的自然化, 每回合中随机向玩家展示一个 $k$u_ 1,\ ldots, u_ k$。 她需要选择一个显示的顶点, 并连接到她想要的任何顶点 。 我们关注以下三个单点属性: 最小度至少为 $\ ell$, 存在完美的匹配和汉密尔顿周期的存在 。</s>