Online market intermediation

DOI10.4230/LIPICS.ICALP.2017.47MaRDI QIDQ5111378zbMATH OpenOpenAlexFDO

Authors Yiannis Giannakopoulos, Elias Koutsoupias, Philip Lazos

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1703.09279

zbMATH Keywords

online algorithmscompetitive analysisbilateral tradesequential auctionsoptimal auctions

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: 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 standard regularity assumptions, namely that $F_B$ is MHR and $F_S$ is log-concave. We study 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 $varTheta(sqrtn)$ and $varTheta(lnn)$, 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 were 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(lnn)$.

Recommendations

• Simple and near-optimal mechanisms for market intermediation
• Online trading as a secretary problem
• Revenue maximization for market intermediation with correlated priors
• Online algorithms for market clearing
• Dynamic Mechanism Design for Online Commerce

Cited in

(9)

• Optimal pricing for MHR distributions
• Dual mechanism for an online retailer
• Algorithms for maximum social welfare of online random trading
• Online trading as a secretary problem
• Simple and near-optimal mechanisms for market intermediation
• Market segmentation in online platforms
• Revenue maximization for market intermediation with correlated priors
• scientific article; zbMATH DE number 2089838 (Why is no real title available?)
• Online algorithms for market clearing

This page was built for publication: Online market intermediation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111378)