Matching in online market platforms
Abstract/Contents
- Abstract
- The thesis contains three parts which provide for an in depth study of problems that are motivated from challenges faced by online platforms. The first two parts study matching problems in decentralized and centralized environments respectively and the third part is concerned with the aggregation of preferences. The first part of the thesis considers the problem of assortment planning in two-sided platforms, where self-interested agents are present on each side of the platform. While assortment planning has been studied extensively in the revenue management literature, it is concerned with the problem of assigning menus of goods (as opposed to people who can reject) to agents. In our problem, agents' utilities are derived from a random utility choice model (RUM). Two different design settings are explored - simultaneous (both sides propose at the same time) and sequential (one side proposes first). The optimal menu is completely characterized for the case of a single customer where a greedy algorithm is shown be optimal. Both design settings turn out to be NP-Hard for multiple customers. Two heuristics are proposed and a constant factor approximation algorithm is provided for the sequential setting. The second part of the thesis considers a centralized marketplace, where agents (drivers and passengers) arrive in an online manner and are matched after a possible delay. Agents arrive at a given set of locations which form a metric (distance between points satisfying the triangle inequality) and the platform needs to minimize the sum of distance and waiting costs. A natural trade-off that arises is the following: matching agents faster reduces waiting costs but waiting for more agents to arrive allows to create better matches. A randomized and a deterministic algorithm are proposed on the tree metric (that has been embedded from the original metric); both of which achieve a constant competitive ratio on the tree metric leading to a logarithmic competitive ratio on the general metric. The third part of the thesis looks at pairwise comparisons among agents specifically in the context of intransitivity. The goal is to develop and analyze parametric models that can support intransitivity. The key result is that such models have non-concave likelihood functions. Next, taking inspiration from the Condorcet paradox, a majority vote model is proposed. The majority vote model can support strong and arbitrarily long intransitive cycles and shows comparable performance against other parametric models which support intransitivity on publicly available datasets.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2019; ©2019 |
| Publication date | 2019; 2019 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Makhijani, Rahul Manoj |
|---|---|
| Degree supervisor | Ashlagi, Itai |
| Thesis advisor | Ashlagi, Itai |
| Thesis advisor | Goel, Ashish |
| Thesis advisor | Saban, Daniela |
| Degree committee member | Goel, Ashish |
| Degree committee member | Saban, Daniela |
| Associated with | Stanford University, Department of Management Science and Engineering. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Rahul Manoj Makhijani. |
|---|---|
| Note | Submitted to the Department of Management Science and Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2019. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2019 by Rahul Manoj Makhijani
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...