Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Fw: OR student seminar 5/5 -- Improved Online Contention Resolution for Matchings and Applications to the Gig Economy

Yeganeh Ali Mohammadi yeganeh at stanford.edu
Thu May 5 10:22:39 PDT 2022


Hi all,

Tristan and Mohammad are giving a talk today at OR student seminar on online matching.
It might be of interest to some of you.

Location: Y2E2-101
Time: 5-6pm


________________________________
From: or-seminars <or-seminars-bounces at lists.stanford.edu> on behalf of Bryce McLaughlin <brycem at stanford.edu>
Sent: Thursday, May 5, 2022 10:11 AM
To: or-seminars at lists.stanford.edu <or-seminars at lists.stanford.edu>; student-or-seminar at lists.stanford.edu <student-or-seminar at lists.stanford.edu>
Subject: Re: OR student seminar 5/5 -- Improved Online Contention Resolution for Matchings and Applications to the Gig Economy

Hi all!

A reminder that Tristan and Mohammed will be presenting their work at 5pm in Y2E2-101

Hope to see you there.

Best,
Bryce

On Thu, Apr 28, 2022 at 6:53 PM Bryce McLaughlin <brycem at stanford.edu<mailto:brycem at stanford.edu>> wrote:
Hi all,

Next week we will be continuing the OR student seminar on Thursday at 5pm where Tristan and Mohammad will be in-person, location TBD presenting their work Improved Online Contention Resolution for Matchings and Applications to the Gig Economy.

Please note the new time.

Title: Improved Online Contention Resolution for Matchings and Applications to the Gig Economy

Abstract:
Motivated by applications in the gig economy, we study approximation algorithms for a sequential pricing problem. The input is a bipartite graph G=(I,J,E) between individuals I and jobs J. The platform has a value of v_j for matching job j to an individual worker. To find a matching, the platform can consider the edges  (i, j) in any order and make worker i a one-time take-it-or-leave-it offer to complete the job j at a price of the platform's choosing, after which the worker accepts with a known probability. What is the best way to make offers to maximize revenue and/or social welfare?

   The optimal algorithm is known to be NP-hard to compute (even if there is only a single job). With this in mind, we design efficient approximations to the optimal policy via a new Random-Order Online Contention Resolution Scheme (RO-OCRS) for matching. Our main result is a 0.456-balanced RO-OCRS in bipartite graphs and a 0.45-balanced RO-OCRS in general graphs. These algorithms improve on the recent bound of 0.432 of Brubach et al., and improve on the best-known lower bounds for the correlation gap of matching, despite applying to a significantly more restrictive setting.  From this we obtain a 0.456-approximate algorithm for the sequential pricing problem.


As always, if you plan on attending in person please fill in this brief form<https://docs.google.com/forms/d/e/1FAIpQLSdLzUgt_r80s9erlnD0W2krOCOZgcO2JSGHpMhaczVEcwme8A/viewform?usp=sf_link> before Tuesday -- We need to have headcounts before ordering for refunding purposes.

Finally, we would like to thank the generosity of the Management Science and Engineering department, the Operations, Information, and Technology group at the Business School, Infanger Investment Technology, and the Diener-Veinott family for supporting this event.

Hope to see you at this seminar and in the many soon to follow.
Best,
Bryce
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220505/dcb00c14/attachment-0001.html>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00001.txt
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220505/dcb00c14/attachment-0001.txt>


More information about the theory-seminar mailing list