团购网站相关外文翻译学士学位论文.doc

外文翻译原文1Matching Models for Preference-sensitive Group PurchasingMatching buyers and sellers is one of the most fundamental problems in economics and market design. An interesting variant of the matching problem arises when self-interested buyers come together in order to induce sellers to offer quantity or volume discounts, as is common in buying consortia, and more recently in the consumer group couponing space (e.g., Groupon).We consider a general model of this problem in which a group or buying consortium is faced with volume discount offers from multiple vendors, but group members have distinct preferences for different vendor offerings. Unlike some recent formulations of matching games that involve quantity discounts, the combination of varying preferences and discounts can render the core of the matching game empty, in both the transferable and nontransferable utility sense. Thus, instead of coalitional stability, we propose several forms of Nash stability under various epistemic and transfer/payment assumptions. We investigate the computation of buyer-welfare maximizing matchings and show the existence of transfers (subsidized prices) of a particularly desirable form that support stable matchings. We also study a nontransferable utility model, showing that stable matchings exist; and we develop a variant of the problem in which buyers provide a simple preference ordering over “deals” rather than specific valuationsa model that is especially attractive in the consumer spacewhich also admits stable matchings. Computational experiments demonstrate the efficacy and value of our approach. Categories and Subject Descriptors: I.2.11 Distributed Artificial Intelligence: Multiagent Systems; J.4Computer Applications: Social and Behavioral SciencesEconomicsGeneral Terms: Algorithms, Economics, TheoryAdditional Key Words and Phrases: stable matching, preferences, demand aggregation, group purchasing,volume discounts, daily deals, cooperative games.1. INTRODUCTIONMatching buyers and sellers is one of the most fundamental problems in economics anddeal” providers like Groupon and Living Social (and services that aggregate such deals) has propelled group discounts into the public consciousness.Group buying and demand aggregation has been studied from several perspectives, and many models have been proposed for their analysis. However, we consider a vital ingredient of group buying that has received insufficient attention in the literature, namely, the fact that buyers often have distinct preferences for the offerings of different vendors. Most matching models with volume discounts assume that vendor offerings are indistinguishable to buyers, which significantly limits their applicability. For instance,suppose two buyers X and Y are (jointly) comparing the offers of two vendors or some item: A offers a price of 10 for one unit, but a discounted price of 8 if both buy from him; and B offers a single price of 9 per unit. If A and B are indistinguishable, X and Y should cooperate and buy from A. But suppose X prefers B (with valuation 11.5) to A (valuation 10). In this case, X would prefer to stick with B unless Y offers some payment to switch vendors (Y would gladly share some of her generated surplus with X for this purpose). Without the ability to express preferences over vendors, “group buying” would not emerge even in this trivial example. market design. A wide variety of models and mechanisms have been developed that reflect different assumptions about the demands, valuations/preferences, and knowledge of the market participants and their ability to cooperate. Each leads to its own computational challenges when developing algorithms for computing stable (core) matchings,Nash equilibria, clearing prices or other solution concepts. In this paper, we address the problem of cooperative group buying, in which a group of buyers coordinate their purchases to realize volume discounts, mitigate demand risk, or reduce inventory costs. Group buying has long been used for corporate procurement,via industry-specific buying consortia or broadly based group purchasingorganizations (GPOs) Chen and Roma 2010. The advent of the Internet, in particular,has helped businesses with no prior affiliation more easily aggregate their demandAnand and Aron 2003. Consumer-oriented group purchasing has also been greatly facilitatedby the web; and the recent popularity of volume-based couponing and “dailydeal” providers like Groupon and Living Social (and services that aggregate such deals)has propelled group discounts into the public consciousness.Group buying and demand aggregation has been studied from several perspectives,and many models have been proposed for their analysis. However, we consider a vital ingredient of group buying that has received insufficient attention in the literature,namely, the fact that buyers often have distinct preferences for the offerings of different vendors. Most matching models with volume discounts assume that vendor offerings are indistinguishable to buyers, which significantly limits their applicability. For instance,suppose two buyers X and Y are (jointly) comparing the offers of two vendors for some item: A offers a price of 10 for one unit, but a discounted price of 8 if both buy from him; and B offers a single price of 9 per unit. If A and B are indistinguishable, X and Y should cooperate and buy from A. But suppose X prefers B (with valuation 11.5) to A (valuation 10). In this case, X would prefer to stick with B unless Y offers some payment to switch vendors (Y would gladly share some of her generated surplus with X for this purpose). Without the ability to express preferences over vendors, “group buying” would not emerge even in this trivial example.While matching becomes much more subtle in such models, assigning buyers to vendors in a way that triggers volume discounts, while remaining sensitive to buyer preferences, offers flexibility and efficiency gains that greatly enhance the appeal of group buying. Consider a group of businesses or buyers working with a GPO to procure supplies within a specific product category (e.g., manufacturing materials, packaging, transportation, payroll services, etc.). The GPO is able to negotiate volume discountsfrom a handful of suppliers or vendors, possibly with multiple discount thresholds. Buyers generally have different valuations for the offerings of different vendors (e.g., buyers may have slightly different manufacturing specifications; or may prefer the contract, payment or delivery terms of certain vendors). A suitable matching of buyers to vendors must trade off these preferences with the triggered discount prices.The same issues arise in consumer domains. Suppose a daily deal aggregator creates a “marketplace” for some product category, say, spas. Multiple spas offer deals that only trigger if a certain quantity is sold. Buyers are faced with a dilemma: they may want only one item, but are uncertain about which deal will trigger. If they only offer to buy (i.e., conditionally purchase) their most preferred spa, they may not get any deal if their preferred deal does not trigger. But if they offer on multiple spas to hedge that risk, they run the opposite risk of obtaining more items than they want. A matching model that allows consumers to specify preferences for items relative to their discounted prices provides flexibility that benefits both consumers and retailers.Our model. In broad strokes, our model assumes a set of vendors offering products (e.g., within a specific product category). Interacting with some GPO or informal buying group, vendors offer (possibly multiple) volume discounts that trigger if the group collectively buys in a certain quantity. We assume these are proposed or negotiated inadvance, and take them to be fixed, posted prices. For ease of exposition, we assume buyers have unit demand, hence treat items as partial substitutes. Each buyer has valuations for each item and quasilinear utility. Since vendor prices are fixed, our aim is to find an allocation of items to buyers that maximizes social welfare (i.e., sum of buyers utilities) given the discounts that trigger, while ensuring stability, or buyer “satisfaction” with the resulting allocation at the triggered prices. We consider two main variants of this problem. In the transferable utility (TU) model, the gains due to demand aggregation can be transferred between buyers to ensure cooperation. In the non-transferable utility (NTU) model, each buyer pays the (triggered) price of her allocated item. Both models have a role to play in specific business and consumer applications. We also consider various forms of knowledgeand recourse on the part of the buyer (e.g., whether they know only which discounts triggered, or have knowledge of the entire allocation and discount schedule). Our results. Since vendor prices are fixed given some demanded quantity, the model induces a coalitional game among the buyers, which we refer to as a discount matching game. Vendor discounts introduce significant externalities in the corresponding matching problem: this leads to the emptiness of core of such games in certain instances, both in the TU and the NTU sense. As a consequence, we consider unilateral deviations from the matching, and focus on the weaker notion of Nash stability under several different epistemic assumptions. We focus first (and primarily) on TU games. We establish that stable matchings (under all epistemic assumptions) not only exist, but that they maximize social welfare. Moreover, they can be realized using transfers only between buyers that are matched to the same vendor.We then consider computation of social welfare maximizing matchings: we show that the corresponding decision problem is NP-complete, but that, given a (fixed) set of discount prices, computing an optimal allocation can be done in polynomial time. As a result, a mixed integer programming (MIP) model of the problem can be formulated in which binary matching variables can be relaxed (as is typical in matching/assignment problems Roth et al. 1993), leaving a MIP whose only integer variables represent the triggering of specific discount thresholds (which, in practice, are relatively few). Experiments demonstrate the efficacy of the formulation. We then consider the NTU discount matching game, and show stable matchings exist. Finally, we consider qualitative discount matching games, a variant in which buyers do not specify valuations for items, but simply rank the deals offered (where a deal is any item and one of its discounted prices). This model is especially appealing in consumer domains, where buyers may be unable to articulate precise valuations for items, but can easily compare any two items at specific prices. As long as the rankings are rationalizable (i.e., correspond to quasi-linear preferences under some latent valuation), again stable matchings are guaranteed to exist. We do not address incentive issues with respect to reporting of buyer preferences. This is an important part of the design of such markets, but one we leave to future research. Truthful reporting of valuations is commonly assumed in work on procurement and inventory management (see below), where parties interact repeatedly. Similarly, we assume that sellers simply post (base and discounted) prices without regard to strategic interaction with buyers. While interactions between sellers w.r.t. Strategic price-setting is also of interest, the way in which “between-seller” equilibrium prices and discount schedules are set does not impact group buying decisions.Related work. Assignment games and matching markets have a rich history, and the literature is rife with connections between various forms of (individual and coalitional) stability, competitive equilibrium prices, etc. Shapley and Shubik 1971; Gale and Shapley 1962; Demange et al. 1986. While a general discount market model would consider strategic behavior on the part of both buyers and sellers, we take seller prices as given and focus on the one-sided problem that results by considering only the strategic behavior of buyers. Of special relevance is work on assignment models, auctions, and procurement optimization that deals explicitly with quantity discounts, buyer/bidder cooperation, and externalities in assignments. Within the context of auctions, Kothari et al. 2005 consider multi-unit (reverse) auctions with discount tiers, and use the VCG mechanism, but consider only a single buyer with no preferences over sellers.1 Conversely, Matsuo et al. 2005 model theproblem of a single seller offering multiple items, each with discount schedules. Buyers with combinatorial preferences bid for items, and allocations/prices are set using VCG; unlike our model, the discounts are not “posted prices” in the usual sense, but are merely used as reserve prices. While the mechanism and assumptions are quite different, and computation is not considered, their motivations are similar to ours. Leyton-Brown and Shoham 2000 study bidding clubs which collude in auction mechanisms to lower prices, and devise payment schemes that induce participation.Author: TYLER LU, CRAIG BOUTILIERNationality: CanadaOriginate from: Association for Computing Machinery, Inc.ISBN: 978-1-4503-1415-2Pages723-740 译文1团购匹配模型匹配买家和卖家，是经济学和市场设计最根本的问题之一。当具有个人利益的买家聚到一起以促使卖家提供批量折扣时，一个有趣的匹配问题的变种开始出现，而且在购买财团和最近在消费群的优惠券空间（例如，Groupon的）中都很普遍。我们就以一个一般的模型来考虑这个问题，其中团体或购买财团正面临着来自多个供应商提供的批量折扣，但小组成员对于来自不同供应商的产品有着不同的喜好。与一些现有的打着批量折扣的匹配博弈不同，结合不同消费者的喜好和不同折扣会是匹配博弈的核心，同时在转让和不可转让的都有实用意义。因此，与合并稳定性相反，我们在各种认知和转账/付款的假设下提出了几种Nash稳定的形式。我们调查并计算了买方福利的最大化匹配计算以及表明存在一个可以支持稳定匹配的特别理想的形式，即价格转移（价格补贴）。涉及的专业领域：算法，经济学，理论学其他关键词和短语：稳定的匹配，喜好，需求聚集，团购，批量折扣，每日交易，合作博弈。引言匹配买家和卖家，是经济学和市场设计最根本的问题之一。各种各样的模式和机制已经被用以放映需求假设、估值与偏好、以及反映市场参与者的知识和合作的能力。每个计算稳定的匹配（核心），纳什均衡，结算价格或其他解决方案概念开发算法时，导致其自身的计算挑战。在本文中，我们试图解决合作团购的问题，其中这些团队中的购买者协调其购买为实现批量折扣，降低需求风险，或降低库存成本。团购早已被用于企业采购，通过特定产业购买财团或广泛基于团购组织。互联网的出现，尤其帮助企业事先没有隶属关系，更容易聚集他们的需求。以消费者为导向的团购，因为互联网获得了很大的便利。而且最近流行的优惠券、像Groupon等供应商提供的“每日交易”和社会服务，极大地推动公众团体折扣的意识。我们可以从多个角度来研究团购和聚集需求，同时还可以用多个模型来对其进行分析。然而，我们认为团购的一个关键要素就是没有得到足够的重视，即事实上，购买者往往对不同供应商提供的铲平有不同的喜好。而大多数具有批量折扣的匹配模型均假设厂商提供的产品是无法区分，这极大地限制了购买者的不同喜好的需求。例如，假设两个买家X和Y对来自两家供应商提供的产品进行比较：A供应商提供每件10个单位的价格，但购买两件的折扣价就是每件8个单位的价格；B供应商提供每件9个单位的价格。如果A和B提供的商品是相似的，X和Y应该合作，并购买A提供的商品。但是，假设X更喜欢B提供的商品（与估值11.5 ），与 A提供的商品（估值10 ）相比。在这种情况下，X宁愿坚持与B ，除非y提供的一些支付切换供应商（Y很乐意分享一些她产生盈余为此目的与X ） 。如果供应商不能考虑消费者偏好问题， “团购”是不会实现的，即便在这个简单的例子中。虽然匹配变得更加微妙在这种模型中，分配买家向供应商用批量折扣的方式来触发，而其余敏感的买家喜好、提供了灵活性和效率的提高，也将大大提升产品的团购吸引力。我们可以考虑利用团购组织，促使企业或购买者的在一个特定的产品类别（例如，制造材料，包装用品，运输，工资服务等）中进行产品供给。团购组织是能够与少数供应商协商批量折扣，可能有多个折扣的阈值。购买者对不同厂商的产品（例如，买家可能略有不同的制造规格;或可能更喜欢某些厂商的合同，付款或交付条款）有不同的估值。一个合适的买家匹配向供应商必须权衡这些偏好与触发的折扣价格。同样的问题出现在消费者领域。假设每天大量交易的聚集为一些产品类别创建了“市场”一说，比如，温泉。多个水疗中心在只有达到一定数量的消费时才会提供一些优惠。消费者都面临着一个难题：他们可能只需要一个项目，但不确定哪些交易将触发。如果他们只提供给购买（即有条件购买）他们最喜欢的水疗中心，他们可能得不到任何优惠，如果他们的首选交易不会触发。但是，如果他们提