Online bipartite-matching platforms are ubiquitous and find applications in
important areas such as crowdsourcing and ridesharing. In the most general
form, the platform consists of three entities: two sides to be matched and a
platform operator that decides the matching. The design of algorithms for such
platforms has traditionally focused on the operator's (expected) profit. Since
fairness has become an important consideration that was ignored in the existing
algorithms a collection of online matching algorithms have been developed that
give a fair treatment guarantee for one side of the market at the expense of a
drop in the operator's profit. In this paper, we generalize the existing work
to offer fair treatment guarantees to both sides of the market simultaneously,
at a calculated worst case drop to operator profit. We consider group and
individual Rawlsian fairness criteria. Moreover, our algorithms have
theoretical guarantees and have adjustable parameters that can be tuned as
desired to balance the trade-off between the utilities of the three sides. We
also derive hardness results that give clear upper bounds over the performance
of any algorithm.

该研究提出了一种在线双向配对平台的算法，可同时为双方市场提供公平的处理保证，考虑了原则主义公平的组和个人标准，并在操作者利润计算的最坏情况下降低其利润，具有理论保证和可调参数来平衡三方的效用，并发现可以给出任何算法性能的明确上界。

网络二分图匹配中的 Rawls 公正：双边、群体和个人

Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual

We generalize the classic problem of fairly allocating indivisible goods to
the problem of \emph{fair public decision making}, in which a decision must be
made on several social issues simultaneously, and, unlike the classic setting,
a decision can provide positive utility to multiple players. We extend the
popular fairness notion of proportionality (which is not guaranteeable) to our
more general setting, and introduce three novel relaxations ---
\emph{proportionality up to one issue, round robin share, and pessimistic
proportional share} --- that are also interesting in the classic goods
allocation setting. We show that the Maximum Nash Welfare solution, which is
known to satisfy appealing fairness properties in the classic setting,
satisfies or approximates all three relaxations in our framework. We also
provide polynomial time algorithms and hardness results for finding allocations
satisfying these axioms, with or without insisting on Pareto optimality.

本文将不可分割资源公平分配的问题扩展到了一个决策必须在多个社会问题上同时做出的公平公共决策问题，并引入了三种新的松弛解法，最终证明了最大纳什福利解决方案适用于所有三个松弛解法，并提供了满足这些公理的分配的多项式时间算法和难度结果。

公平的公共决策制定

Fair Public Decision Making

The Stackelberg equilibrium solution concept describes optimal strategies to
commit to: Player 1 (termed the leader) publicly commits to a strategy and
Player 2 (termed the follower) plays a best response to this strategy (ties are
broken in favor of the leader). We study Stackelberg equilibria in finite
sequential games (or extensive-form games) and provide new exact algorithms,
approximate algorithms, and hardness results for several classes of these
sequential games.

本文研究了在有限序贯博弈中 Stackelberg 均衡解概念，提供了几类序贯博弈的新的精确算法、近似算法和难度结果。

有限顺序博弈的斯塔克贝格均衡计算

Computation of Stackelberg Equilibria of Finite Sequential Games

Variable selection for sparse linear regression is the problem of finding,
given an m x p matrix B and a target vector y, a sparse vector x such that Bx
approximately equals y. Assuming a standard complexity hypothesis, we show that
no polynomial-time algorithm can find a k'-sparse x with ||Bx-y||^2<=h(m,p),
where k'=k*2^{log^{1-delta} p} and h(m,p)<=p^(C_1)*m^(1-C_2), where delta>0,
C_1>0,C_2>0 are arbitrary. This is true even under the promise that there is an
unknown k-sparse vector x^* satisfying Bx^*=y. We prove a similar result for a
statistical version of the problem in which the data are corrupted by noise.
To the authors' knowledge, these are the first hardness results for sparse
regression that apply when the algorithm simultaneously has k'>k and h(m,p)>0.

该论文介绍了在观察到一个 m x p 的矩阵 B 和目标向量 y 的情况下，如何找到一个稀疏向量 x，使得 Bx 等于 y 的近似解，给出了该问题不存在多项式时间算法的证明，并对该问题的统计版本进行了类似的证明。