Online Market Intermediation
Online Market Intermediation
复制标题
DOI：
10.4230/lipics.icalp.2017.47
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
Yiannis Giannakopoulos;E. Koutsoupias;Philip Lazos
中科院分区：
文献类型：
--
作者：
Yiannis Giannakopoulos;E. Koutsoupias;Philip Lazos
我们研究了一个动态的市场环境，其中一个中介与一个未知的大代理序列相互作用，这些代理可以是卖家或买家：他们的身份，以及序列长度n，以一种对抗的在线方式决定。每个代理商只对一种商品感兴趣，市场上的所有商品都是相同的。中介对代理人对物品的价值有一些先验的、不完全的知识：所有卖方的价值都独立地来自相同的分布F＿S，所有买方的价值都来自F＿B。这两个分布可能不同，我们做出共同的规则性假设，即F＿B是MHR， F＿S是log-凹。我们关注在线定价机制，并在竞争分析基准下分析两个目标：中介利润最大化和社会福利最大化。首先，在消极方面，对于一般代理序列，我们分别证明了两个目标的Theta（\sqrt (n)）和Theta（\ln n）的紧密竞争比。另一方面，在额外的假设下，中介知道卖家和买家数量之比的某个界\alpha，我们设计了竞争比分别为1+ 0(1)和4的渐近最优在线机制。此外，我们研究了在整个执行过程中可以存储在库存中的商品数量有界的模型，在这种情况下，利润的竞争比被改进为O（ln n）。
We study a dynamic market setting where an intermediary interacts with an unknown large sequence of agents that can be either sellers or buyers: their identities, as well as the sequence length n, are decided in an adversarial, online way. Each agent is interested in trading a single item, and all items in the market are identical. The intermediary has some prior, incomplete knowledge of the agents' values for the items: all seller values are independently drawn from the same distribution F_S, and all buyer values from F_B. The two distributions may differ, and we make common regularity assumptions, namely that F_B is MHR and F_S is log-concave. We focus on online, posted-price mechanisms, and analyse two objectives: that of maximizing the intermediary's profit and that of maximizing the social welfare, under a competitive analysis benchmark. First, on the negative side, for general agent sequences we prove tight competitive ratios of Theta(\sqrt(n)) and Theta(\ln n), respectively for the two objectives. On the other hand, under the extra assumption that the intermediary knows some bound \alpha on the ratio between the number of sellers and buyers, we design asymptotically optimal online mechanisms with competitive ratios of 1+o(1) and 4, respectively. Additionally, we study the model where the number of items that can be stored in stock throughout the execution is bounded, in which case the competitive ratio for the profit is improved to O(ln n).