In digital health and EdTech, recommendation systems face a significant
challenge: users often choose impulsively, in ways that conflict with the
platform's long-term payoffs. This misalignment makes it difficult to
effectively learn to rank items, as it may hinder exploration of items with
greater long-term payoffs. Our paper tackles this issue by utilizing users'
limited attention spans. We propose a model where a platform presents items
with unknown payoffs to the platform in a ranked list to $T$ users over time.
Each user selects an item by first considering a prefix window of these ranked
items and then picking the highest preferred item in that window (and the
platform observes its payoff for this item). We study the design of online
bandit algorithms that obtain vanishing regret against hindsight optimal
benchmarks.
We first consider adversarial window sizes and stochastic iid payoffs. We
design an active-elimination-based algorithm that achieves an optimal
instance-dependent regret bound of $O(\log(T))$, by showing matching regret
upper and lower bounds. The key idea is using the combinatorial structure of
the problem to either obtain a large payoff from each item or to explore by
getting a sample from that item. This method systematically narrows down the
item choices to enhance learning efficiency and payoff.
Second, we consider adversarial payoffs and stochastic iid window sizes. We
start from the full-information problem of finding the permutation that
maximizes the expected payoff. By a novel combinatorial argument, we
characterize the polytope of admissible item selection probabilities by a
permutation and show it has a polynomial-size representation. Using this
representation, we show how standard algorithms for adversarial online linear
optimization in the space of admissible probabilities can be used to obtain a
polynomial-time algorithm with $O(\sqrt{T})$ regret.

使用用户的有限注意力解决推荐系统中的长期回报偏差问题，通过在线贪心算法和多项式时间算法降低后悔度和寻优问题。

用户有限注意力的利用：失配、学习和排序

Misalignment, Learning, and Ranking: Harnessing Users Limited Attention

Game theory provides a quantitative framework for analyzing the behavior of
rational agents. The Iterated Prisoner's Dilemma in particular has become a
standard model for studying cooperation and cheating, with cooperation often
emerging as a robust outcome in evolving populations. Here we extend
evolutionary game theory by allowing players' strategies as well as their
payoffs to evolve in response to selection on heritable mutations. In nature,
many organisms engage in mutually beneficial interactions, and individuals may
seek to change the ratio of risk to reward for cooperation by altering the
resources they commit to cooperative interactions. To study this, we construct
a general framework for the co-evolution of strategies and payoffs in arbitrary
iterated games. We show that, as payoffs evolve, a trade-off between the
benefits and costs of cooperation precipitates a dramatic loss of cooperation
under the Iterated Prisoner's Dilemma; and eventually to evolution away from
the Prisoner's Dilemma altogether. The collapse of cooperation is so extreme
that the average payoff in a population may decline, even as the potential
payoff for mutual cooperation increases. Our work offers a new perspective on
the Prisoner's Dilemma and its predictions for cooperation in natural
populations; and it provides a general framework to understand the co-evolution
of strategies and payoffs in iterated interactions.

扩展进化博弈论通过允许玩家策略及其回报随着遗传变异的选择而进化，提供了一般框架来理解策略和回报在迭代博弈中的共同进化过程，揭示出利益和成本之间的权衡使得合作的瓦解是如此极端以至于合作的平均回报可能下降，即使相互合作的潜在回报仍在增加。