约束条件下的买方对卖方推荐

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Buyer to Seller Recommendation under Constraints》
---
作者：
Cheng Chen, Lan Zheng, Venkatesh Srinivasan, Alex Thomo, Kui Wu,
  Anthony Sukow
---
最新提交年份：
2014
---
英文摘要：
  The majority of recommender systems are designed to recommend items (such as movies and products) to users. We focus on the problem of recommending buyers to sellers which comes with new challenges: (1) constraints on the number of recommendations buyers are part of before they become overwhelmed, (2) constraints on the number of recommendations sellers receive within their budget, and (3) constraints on the set of buyers that sellers want to receive (e.g., no more than two people from the same household). We propose the following critical problems of recommending buyers to sellers: Constrained Recommendation (C-REC) capturing the first two challenges, and Conflict-Aware Constrained Recommendation (CAC-REC) capturing all three challenges at the same time. We show that C-REC can be modeled using linear programming and can be efficiently solved using modern solvers. On the other hand, we show that CAC-REC is NP-hard. We propose two approximate algorithms to solve CAC-REC and show that they achieve close to optimal solutions via comprehensive experiments using real-world datasets.
---
中文摘要：
大多数推荐系统设计用于向用户推荐项目（如电影和产品）。我们关注的是向卖家推荐买家的问题，这带来了新的挑战：（1）在买家不堪重负之前，对买家推荐数量的限制；（2）卖家在预算内收到的推荐数量的限制，（3）对卖家希望接收的买家群体的限制（例如，同一家庭不超过两人）。我们提出了以下向卖家推荐买家的关键问题：捕获前两个挑战的约束推荐（C-REC）和同时捕获所有三个挑战的冲突感知约束推荐（CAC-REC）。我们证明了C-REC可以用线性规划建模，并且可以用现代求解器有效地求解。另一方面，我们证明了CAC-REC是NP难的。我们提出了两种近似算法来求解CAC-REC，并通过使用真实数据集的综合实验表明，它们实现了接近最优的解。
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Social and Information Networks        社会和信息网络
分类描述：Covers the design, analysis, and modeling of social and information networks, including their applications for on-line information access, communication, and interaction, and their roles as datasets in the exploration of questions in these and other domains, including connections to the social and biological sciences. Analysis and modeling of such networks includes topics in ACM Subject classes F.2, G.2, G.3, H.2, and I.2; applications in computing include topics in H.3, H.4, and H.5; and applications at the interface of computing and other disciplines include topics in J.1--J.7. Papers on computer communication systems and network protocols (e.g. TCP/IP) are generally a closer fit to the Networking and Internet Architecture (cs.NI) category.
涵盖社会和信息网络的设计、分析和建模，包括它们在联机信息访问、通信和交互方面的应用，以及它们作为数据集在这些领域和其他领域的问题探索中的作用，包括与社会和生物科学的联系。这类网络的分析和建模包括ACM学科类F.2、G.2、G.3、H.2和I.2的主题；计算应用包括H.3、H.4和H.5中的主题；计算和其他学科接口的应用程序包括J.1-J.7中的主题。关于计算机通信系统和网络协议（例如TCP/IP）的论文通常更适合网络和因特网体系结构（CS.NI）类别。
--
一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Quantitative Finance        数量金融学
二级分类：General Finance        一般财务
分类描述：Development of general quantitative methodologies with applications in finance
通用定量方法的发展及其在金融中的应用
--
一级分类：Quantitative Finance        数量金融学
二级分类：Statistical Finance        统计金融
分类描述：Statistical, econometric and econophysics analyses with applications to financial markets and economic data
统计、计量经济学和经济物理学分析及其在金融市场和经济数据中的应用
--

---
PDF下载：
--> Buyer_to_Seller_Recommendation_under_Constraints.pdf (204.96 KB)

2022-5-6 06:54:12 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：约束条件 Applications Quantitative Econophysics Architecture

买方对卖方的推荐，根据维多利亚大学，Canadacchenv@uvic.caLan维多利亚大学，Canadalanzheng@uvic.caVenkatesh维多利亚州斯里尼瓦桑大学，Canadavenkat@cs.uvic.caAlex维多利亚州托莫大学，Canadathomo@cs.uvic.caKui维多利亚大学，Canadawkui@uvic.caAnthonySukowTerapeakVictoria，Canadaanthony@terapeak.comABSTRACTThe大多数推荐er系统设计用于向用户推荐项目（如电影和产品）。我们关注的是向卖家推荐买家的问题，这带来了新的挑战：（1）在买家不堪重负之前，买家的推荐数量受到限制，（2）卖家在预算内收到的推荐数量受到限制，（3）对卖家希望接收的买家群体的限制（例如，同一家庭不超过两人）。我们提出了以下向卖家推荐买家的关键问题：捕获前两个挑战的约束推荐（C-REC）和同时捕获所有三个挑战的冲突感知约束推荐（CAC-REC）。我们证明了C-REC可以用线性规划建模，并且可以用MOD ern解算器有效地求解。另一方面，我们证明了CACREC是NP难的。我们提出了两种近似算法来求解CAC-REC，并通过使用真实世界数据集的综合实验表明，它们实现了接近最优的解。类别和主题描述词。3[信息存储和检索]：信息搜索和检索信息过滤；F.2.1[分析isof算法和问题复杂性]：数学算法和问题矩阵计算通用术语算法关键字买方推荐、优化、近似1。

简介我们研究在在线电子商务网站（如eBay）中向卖家推荐买家（RBS）的问题。这个问题本身就有一系列挑战，与向用户推荐商品的挑战截然不同。第一个挑战是，我们不想向所有卖家推荐顶级买家（根据他们的购买历史），因为这些顶级买家将被试图联系到他们的渴望卖家发出的数千条广告信息淹没。因此，我们需要适当的限制，以限制每个买家可以推荐的卖家数量。第二个挑战是，卖家通常不受预算限制，因此不希望向他们推荐的买家超过他们的支付能力。第三个挑战是，我们需要将顶级买家推荐给顶级卖家，将中层买家推荐给中层卖家，等等，因为这样可以最大限度地让买家和卖家都满意；通常，顶级买家会购买大量商品，而顶级卖家最有可能满足他们的胃口。一般来说，我们希望避免将顶级买家推荐给不那么优秀的卖家，除非后者已经被推荐的买家所饱和。在向用户（RIU）推荐商品（如电影）时，我们通常不会遇到这些挑战。例如，向一个在线网站的所有用户推荐最佳影片绝对没有问题；相反，它被广泛应用。此外，只要按照评级预测进行排序，就不存在向一个人推荐太多电影的问题。

最后，电影推荐是一个非常“民主”的过程；最好的电影总是推荐给不太优秀的用户，即那些不看很多电影并给它们打分的用户（冷启动用户）。综上所述，显然RBS与RIU非常不同，因此，我们需要一种新的形式化和新算法来解决RBS。据你所知，我们是第一个直接解决这一重要问题的人。这是因为经典广告是在“广播”模式下通过电视广告和搜索结果中的赞助商链接进行的，而这些都没有上述挑战。另一种广告方式是通过有针对性的活动。这通常由一家商户公司完成（或发起），包括确定其产品的目标客户群。同样，这样的流程与苏格兰皇家银行不同，苏格兰皇家银行有许多卖家在为买家竞争。在本文中，我们介绍了两个核心问题，约束推荐（C-REC）和冲突感知约束推荐（CAC-REC），以解决不同的TRBS场景。我们从一家在线公司的角度看待苏格兰皇家银行，比如eBay。这类公司通常会将买家的每一项建议与卖家的每一项建议关联起来。对于给定的卖家，买家的排名越高，推荐就越有价值。在C-REC中，我们假设每个买家和卖家都有asp-ECIC“能力”也就是说，一个买家不能被推荐给超过其能力的卖家，一个卖家也不能被推荐给超过其预算（能力）的买家。然后，目标是在尊重买方和卖方的能力约束的情况下，生成最大化总可行性（建议权重之和）的建议。在CAC-REC中，我们以自然的方式扩展了C-REC。也就是说，我们假设买家可能与其他买家“冲突”。

例如，一位买家可能会使用与另一位买家相同的IP Address或Browser cookie，这表明这两位买家共享同一台电脑，可能住在同一个家庭。卖家可能不希望成为相互冲突的推荐买家，例如卖家销售电视、洗衣机等家庭用品的情况。我们表明，C-REC可以使用线性规划建模，并可以使用现代解算器有效求解。另一方面，我们证明了CAC-REC是NP难的。我们提出了两种近似算法来解决CAC-RECand问题，并通过使用真实数据集的综合实验表明，它们获得了接近最优的解。具体而言，我们的贡献如下：1。我们开始研究inRBS系统产生的自然问题：在各种约束条件下，我们如何向卖家推荐高价值买家？2.在存在容量约束（C-REC）的情况下，我们将问题建模为整数线性规划，并证明该问题可以使用LP解算器进行优化求解（即LP解是积分的）。对于容量和冲突约束（CACREC）的情况，我们证明了该问题是NP难问题，并将其建模为半定规划和整数线性规划。我们提出了一种贪婪算法，该算法具有可扩展性，接近最优。4.我们对真实世界的数据集进行了广泛的实验评估，验证了上述可扩展性和最优性的主张。2.相关工作RBS与基于约束的推荐任务相关（参见[2,16,3,4,12,15,8]）。前两项工作考虑了对项目特征（属性）的约束，因此他们没有像我们一样研究同一类型的约束。其余的工作与我们的第一个C-REC问题更密切相关。Karimzadehgan等人[5,3,4]研究了优化科学论文评审任务的问题。

与C-REC类似，它们对每个审阅者分配的纸张配额进行限制。然而，与C REC不同的是，在他们的优化设置中，审稿人与论文的匹配是基于专业知识的多个方面的匹配。Taylor在[12]中还考虑了论文评审分配问题。与C-REC的区别在于，它不考虑对审稿人和论文进行排序。Xie、Lakshmanan和Wood在[15]中研究了复合建议的问题，其中每个建议都包含一组项目。他们还考虑包括可推荐给用户的项目数量。然而，他们的目标是，当每件商品都有价格支付时，将推荐的一套商品的成本降到最低。Parameswaran、Venetis和Garcia Molina[8]研究了课程需求约束下的课程推荐问题。与[15]类似，[8]的目标是提出一套建议。然而，他们面临的挑战是对复杂的学术要求进行建模（例如，从5门数学课程中选择2门以满足学位要求）。这些约束与我们考虑的约束不同。据我们所知，我们考虑的第二个问题CAC-REC是全新的。3.约束推荐（C-REC）我们首先研究推荐问题，不考虑买家之间的冲突。为了形式化地描述这个问题，我们将买卖双方网络建模为一个无向的二部图（图1）G=h（B，S），e，WI，其中B={B，B，…，bm}表示买方列表，S={S，S，…，sn}卖方列表，e B×S是边的集合，W:E→R+边的权重。图1:C-REC。

这些数字是学位限制。为了方便起见，我们稍微滥用了符号，并使用mn-d维度向量来表示E=[eij]，eij=1表示买方i和卖方jand eij=0之间存在优势。类似地，我们使用一个向量来表示w=[wij]。如果eij=0，那么wij=0。当下标很难读懂时，如下一节所述，我们也使用W（i，j）来表示wij。买家与买家之间的边缘重量∈ B和a卖家J∈ S、 wij，如果买方被推荐给卖方，则反映了可靠性价值。在实践中，我们可能会基于各种商业模式对二部图进行预处理。例如，我们可以根据投入和收入、买卖的最近情况等来订购商家或卖家。此外，我们可以将买家的优势限制在卖家的排名范围内，这样买家就不会被推荐给她“级别”之外的卖家。通常，只有一定数量的买家被推荐给卖家是可取的，因为卖家可能会被其他方面压倒，或者因为卖家需要为推荐支付费用。同样，向大量卖家推荐abuyer也是不合理的，因为买家可能会在以后被许多未经请求的请求所欺骗。为了避免这个问题，go od推荐系统应该允许我们对与个人买家和卖家相关的推荐数量进行培训。换句话说，我们需要把度约束D:B∪ s→ 二部图中的N。我们用（m+n）维列向量D=[D（i）]T表示D。表示X=[xij]T表示0-1变量的mn维列向量，其中xij=1表示买方i建议卖方j，否则xij=0。constrainedrecommendation（C-REC）问题是找到一组建议，以便在度约束（即maxXW-Xs）下，建议的总收益最大化。T

AX（一）≤ D（i），i、 一,≤ 我≤ m+nxij∈ {0, 1}, i、 j，1≤ 我≤ m、 一,≤ J≤ n、 （1）式中，矩阵A为（m+n）×mn矩阵，定义如下：[e，…，e1n][e，…，e2n]。。。[em1，…，emn][e，0，…，0]。[em1，0，…，0]。。。。。。。。。[0，…，0，e1n]。[0，…，0，emn].|{z}（m+n）×mn（2）度约束由AX（i）给出≤ D（i），其中x（i）表示（向量）AX中的第i个元素，D（i）表示D中的第i个元素。从上述公式中，很容易看出CREC问题可以简化为运筹学[1,10,11]中的运输问题，因此我们得到了一个LP问题，该问题可以由现代求解者有效地解决。此外，还可以证明LP解是LSO积分。4.冲突感知约束推荐（CAC-REC）我们现在考虑问题CREC的自然泛化。在某些情况下，卖家会倾向于推荐买家的多样化列表，以避免某些冗余。例如，卖家可能希望他们的名单中不包括每户超过一名推荐买家。在大多数情况下，为某一特定商品向一个家庭中的多个潜在买家做广告是不必要的。我们将使用（未加权）冲突边缘（图2）表示两个买家之间存在此类依赖或冲突。我们将此建议问题称为冲突建议（CAC-REC）。目标是计算一个最大权重子图，满足C-REC中的DegreeConstraint，另外要求推荐给任何特定卖家的买家列表中的冲突边数小于阈值。图2:CAC-REC。数字为度约束，红色边表示冲突。为了更准确地描述CAC-REC，CACREC的输入包括以下信息：1。

无向加权图G=h（B，S），E∪ C、 W与E B×S，C B×B和重量W:E→ R+；2.学位限制D:B∪ s→ N3.冲突阈值t。CAC-REC中的目标是计算G，G′=（（B，S），E′）的最大权重子图G′∪ 满足以下两个约束条件：1。对于任何我在B∪ S、 dG′（一）≤ D（i）2。对于S中的任何k，|{（i，j）|（i，k），（j，k）∈ E′（i，j）∈ C′}|≤t、 这里，dG′（i）表示su-bgraph′中顶点i的阶。接下来，我们将展示，考虑到购买者之间的冲突，推荐问题的复杂性会显著增加。4.1 CAC的NP硬度结果在本节中，我们提供了强有力的证据，证明CACREC不太可能有高效（即多项式时间）算法，因为它是NP难的。定理1。CAC-REC是NP难的。证据我们从区间规划中的收益最大化问题出发，给出了一个多项式时间的推论。区间调度（RMIS）实例中的收益最大化：t台机器的集合M={M，M，…，mt}和n个作业的集合J={J，J，…，jn}。对于j中的每个工件j，我们给出了三个参数：（1）S（j），可以加工j的机器集（2）R（j，-), 在不同机器（3）I（j）上处理作业j时获得的一组可能地点，即必须处理作业j的时间间隔。目标：为机器上的一部分作业找到一个可行的计划，使计划作业的总收入最大化。我们现在描述了从RMIS到CAC-REC的缩减。给定收益最大化问题的一个实例I，构造一个图G（I），它是CAC-REC的一个实例。定义G（I）=h（J，M），E∪ C、 W i和E J×M，CJ×J和重量W:E→ R+如下所示：E={（jk，ml）|ml∈ S（jk）}C={（jk，jl）|I（jk）∩ I（jl）6=}.o W（jk，ml）=R（jk，ml）D（jk）=1表示所有k，D（ml）=n表示所有l.ot=0。现在我们来解释上面的删减。

作业jk和机器mlif之间有一个边，MLF属于可以处理作业jk的机器集（jk）。如果作业JK和作业JL的处理时间间隔重叠，则两者之间存在明显的优势。边上的权重（jk，ml）表示在machineml上处理作业jk所获得的收入。由于每个作业最多可以分配给一台机器，因此它们的度约束设置为1。分配给任何机器的作业数量没有限制，因此，它们的度限制设置为n。最后，分配给同一台机器的两个作业之间必须没有冲突。因此，t被设置为0。很容易看出，CAC-REC实例G（I）的最优解产生RMIS实例I的最优解。换句话说，满足上述度约束和冲突约束的G（I）的最大权重子图正好对应于I中的场地最大化时间表。此外，我们观察到，上述缩减是多项式时间缩减。因此，我们得出结论，CAC-REC是NP难的。4.2 CAC的SDP算法在上一节中，我们证明了CAC-REC是NPhard。在本节和下一节中，我们将为CAC-REC设计两种高效算法，提供接近最优的高质量解决方案。我们的第一个CAC-REC算法基于半定规划方法。为了理解这种方法的动机，回想一下我们在第3节中描述的C-REC的LPC公式。使用第3节和第4.1节中的术语，冲突约束可以描述如下：X（jk，jl）∈Cxkixli≤ T 我∈ S（3）也就是说，冲突约束是二次的。我们使用一个单独的t来进行说明。在实践中，不同的卖家可以有不同的t值。我们现在将展示如何将CAC-REC模拟为一个半限定程序。