Loading...
Please wait, while we are loading the content...
Similar Documents
Stochastic Matching CMSC 858 F : Algorithmic Game Theory Fall 2010
| Content Provider | Semantic Scholar |
|---|---|
| Author | Saha, Barna Liaghat, Vahid |
| Copyright Year | 2010 |
| Abstract | This summary is mostly based on the work of Saberi et al. [1] on online stochastic matching problem proposed by Feldman et al. [2] as a model of display ad-allocation. We are given a bipartite graph; one side of the graph corresponds to a fixed set of bidders with budget limit of one and the other side represents the set of possible adword types. At each time step, an adword is sampled independently from the given distribution and it needs to be matched upon its arrival to an available bidder. The goal is to maximize the size of the matching. Algorithms with a competitive ratio better than 1 − 1/e are known under the assumption that the expected number of arriving adwords of each type is integral. In [1] Saberi et al. present an online algorithm for the general (non-integral) problem with a competitive ratio of 0.702. A key idea of the algorithm is to collect statistics about the decisions of the optimum offline solution using Monte Carlo sampling and use those statistics to guide the decisions of the online algorithm. They also show that no online algorithm can have a competitive ratio better than 0.823. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.cs.umd.edu/~hajiagha/AGT10/LS-8-scribe.pdf |
| Alternate Webpage(s) | http://www.cs.umd.edu/~hajiagha/AGT10/LS-8-scribe.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
