On-line firms deploy suites of software platforms, where each platform is designed to interact with users during a certain activity, such as browsing, chatting, socializing, emailing, driving, etc. The economic and incentive structure of this exchange, as well as its algorithmic nature, have not been explored to our knowledge. We model this interaction as a Stackelberg game between a Designer and one or more Agents. We model an Agent as a Markov chain whose states are activities; we assume that the Agent's utility is a linear function of the steady-state distribution of this chain. The Designer may design a platform for each of these activities/states; if a platform is adopted by the Agent, the transition probabilities of the Markov chain are affected, and so is the objective of the Agent. The Designer's utility is a linear function of the steady state probabilities of the accessible states minus the development cost of the platforms. The underlying optimization problem of the Agent -- how to choose the states for which to adopt the platform -- is an MDP. If this MDP has a simple yet plausible structure (the transition probabilities from one state to another only depend on the target state and the recurrent probability of the current state) the Agent's problem can be solved by a greedy algorithm. The Designer's optimization problem (designing a custom suite for the Agent so as to optimize, through the Agent's optimum reaction, the Designer's revenue), is NP-hard to approximate within any finite ratio; however, the special case, while still NP-hard, has an FPTAS. These results generalize from a single Agent to a distribution of Agents with finite support, as well as to the setting where the Designer must find the best response to the existing strategies of other Designers. We discuss other implications of our results and directions of future research.


翻译:在线公司部署软件平台套件, 每个平台的设计是用来与用户在某一活动期间进行互动的, 例如浏览、聊天、社交、电子邮件、驱动等。 我们的知识尚未探索这种交换的经济和激励结构以及其算法性质。 我们将这种互动模式建为设计师和一个或多个代理商之间的Stackelberg游戏。 我们将一个代理商建为Markov 链的代理商, 其状态是活动; 我们假设该代理商的效用是该链中稳定状态分布的线性功能。 设计师可能为其中每一项活动/状态设计一个平台; 如果该代理商采用一个平台, 马尔科夫链的过渡概率性结构以及其算法性性质, 设计师的效用是固定状态的概率的直线性功能, 其它平台的开发成本。 代理商的潜在优化问题 -- 如何选择采用该平台的州 -- 是一个 MDP 。 如果这个 MDP 设计师拥有一个简单但可信的设计结构, 马尔科夫的过渡性结构, 其当前汇率的稳定性的稳定性的分布必须是从一个稳定状态向另一个方向。

0
下载
关闭预览

相关内容

马尔可夫链,因安德烈·马尔可夫(A.A.Markov,1856-1922)得名,是指数学中具有马尔可夫性质的离散事件随机过程。该过程中,在给定当前知识或信息的情况下,过去(即当前以前的历史状态)对于预测将来(即当前以后的未来状态)是无关的。 在马尔可夫链的每一步,系统根据概率分布,可以从一个状态变到另一个状态,也可以保持当前状态。状态的改变叫做转移,与不同的状态改变相关的概率叫做转移概率。随机漫步就是马尔可夫链的例子。随机漫步中每一步的状态是在图形中的点,每一步可以移动到任何一个相邻的点,在这里移动到每一个点的概率都是相同的(无论之前漫步路径是如何的)。
专知会员服务
52+阅读 · 2020年9月7日
知识图谱在可解释人工智能中的作用,附81页ppt
专知会员服务
137+阅读 · 2019年11月11日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
已删除
将门创投
4+阅读 · 2017年12月5日
Arxiv
0+阅读 · 2021年9月13日
Arxiv
0+阅读 · 2021年9月10日
Arxiv
7+阅读 · 2021年5月25日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关VIP内容
专知会员服务
52+阅读 · 2020年9月7日
知识图谱在可解释人工智能中的作用,附81页ppt
专知会员服务
137+阅读 · 2019年11月11日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
已删除
将门创投
4+阅读 · 2017年12月5日
Top
微信扫码咨询专知VIP会员