The fundamental assignment problem is in search of welfare maximization
mechanisms to allocate items to agents when the private preferences over
indivisible items are provided by self-interested agents. The mainstream
mechanism \textit{Random Priority} is asymptotically the best mechanism for
this purpose, when comparing its welfare to the optimal social welfare using
the canonical \textit{worst-case approximation ratio}. Despite its popularity,
the efficiency loss indicated by the worst-case ratio does not have a constant
bound. Recently, [Deng, Gao, Zhang 2017] show that when the agents' preferences
are drawn from a uniform distribution, its \textit{average-case approximation
ratio} is upper bounded by 3.718. They left it as an open question of whether a
constant ratio holds for general scenarios. In this paper, we offer an
affirmative answer to this question by showing that the ratio is bounded by
$1/\mu$ when the preference values are independent and identically distributed
random variables, where $\mu$ is the expectation of the value distribution.
This upper bound also improves the upper bound of 3.718 in [Deng, Gao, Zhang
2017] for the Uniform distribution. Moreover, under mild conditions, the ratio
has a \textit{constant} bound for any independent random values. En route to
these results, we develop powerful tools to show the insights that in most
instances the efficiency loss is small.

本文研究了基本的分配问题，提出了一种新的机制来最大化效益，即当提供自利智能体对不可分割项目的私人偏好时，我们提出了一种新的机制：随机优先级机制，并且发现这种机制的效率损失具有常数界 。

具有独立偏好的分配问题的平均情况分析

Average-case Analysis of the Assignment Problem with Independent  Preferences

In this paper, we study the classic problem of fairly allocating indivisible
items with the extra feature that the items lie on a line. Our goal is to find
a fair allocation that is contiguous, meaning that the bundle of each agent
forms a contiguous block on the line. While allocations satisfying the
classical fairness notions of proportionality, envy-freeness, and equitability
are not guaranteed to exist even without the contiguity requirement, we show
the existence of contiguous allocations satisfying approximate versions of
these notions that do not degrade as the number of agents or items increases.
We also study the efficiency loss of contiguous allocations due to fairness
constraints.

本文研究了在一条线段上分配不可分割物品的问题，要求分配公平且连续，即每个代理的束形成线段上的连续块。我们证明了满足比例公平性，无嫉妒性和公平性这些经典公平概念的连续分配即使没有连续性要求也无法保证存在。然而，我们证明了存在近似满足这些概念的连续分配，其近似程度不随代理或物品数量的增加而降低。同时，我们也研究了由于公平性约束而导致的连续分配的效率损失。

公平分配不可分割物品的连续区块

Fairly Allocating Contiguous Blocks of Indivisible Items

The Generalized Second Price (GSP) auction is the primary auction used for
monetizing the use of the Internet. It is well-known that truthtelling is not a
dominant strategy in this auction and that inefficient equilibria can arise. In
this paper we study the space of equilibria in GSP, and quantify the efficiency
loss that can arise in equilibria under a wide range of sources of uncertainty,
as well as in the full information setting. The traditional Bayesian game
models uncertainty in the valuations (types) of the participants. The
Generalized Second Price (GSP) auction gives rise to a further form of
uncertainty: the selection of quality factors resulting in uncertainty about
the behavior of the underlying ad allocation algorithm. The bounds we obtain
apply to both forms of uncertainty, and are robust in the sense that they apply
under various perturbations of the solution concept, extending to models with
information asymmetries and bounded rationality in the form of learning
strategies.
We present a constant bound (2.927) on the factor of the efficiency loss
(\emph{price of anarchy}) of the corresponding game for the Bayesian model of
partial information about other participants and about ad quality factors. For
the full information setting, we prove a surprisingly low upper bound of 1.282
on the price of anarchy over pure Nash equilibria, nearly matching a lower
bound of 1.259 for the case of three advertisers. Further, we do not require
that the system reaches equilibrium, and give similarly low bounds also on the
quality degradation for any no-regret learning outcome. Our conclusion is that
the number of advertisers in the auction has almost no impact on the price of
anarchy, and that the efficiency of GSP is very robust with respect to the
belief and rationality assumptions imposed on the participants.

本文研究了广义第二价格 (GSP) 拍卖中的均衡状态空间，并量化了广泛来源的不确定性和完全信息设置下可能出现的低效均衡状态损失。通过贝叶斯博弈模型，得出了 2.927 的损失因子上限，证明了拍卖参与者关于其他参与者和广告质量因素的部分信息的贝叶斯模型中的效率损失。此外，在完全信息设置中，我们证明了对于三个广告商的情况下，纯纳什均衡的 “惩罚因子” 的上限接近于 1.282，同时我们展示了类似的低上限的结果适用于任何遵循无后悔策略的拍卖结果。