Lunch in Theory (Spring Recess) Talk by Edith Elkind on Wednesday [12:00 PM, 03/18, GCS 302c]

[Devansh Gupta]

Hi all,

Please join us for Lunch in Theory this Wednesday, 03/18 at 12:00 PM in GCS 302c. This week we have Edith Elkind presenting! Please find the title and abstract attached.

Reminder: Please bring your own lunch, as lunch will not be provided.

Best,

Devansh

Title: Fair and efficient bus stop allocation

Abstract: We consider a stylized formal model of public transportation, where a set of agents need to travel along a given road, and there is a bus that runs the length of this road. Each agent has a left terminal and a right terminal between which they wish to travel; they can walk all the way, or walk to/from the nearest stop and use the bus for the rest of their journey. The bus can make a fixed number of stops, and the planner needs to select locations for these stops. We study notions of efficiency and fairness for this setting. We give a polynomial-time algorithm for computing a solution that minimizes the total travel time; our approach can capture further extensions of the base model, such as more general cost functions or existing infrastructure. Further, we develop a polynomial-time algorithm that outputs solutions with provable fairness guarantees (such as a variant of the justified representation axiom or $2$-approximate core). We then explore whether our results can be extended to tree networks. 

Based on joint work with Martin Bullinger and Mohamad Latifian (AAMAS'25) and work in progress with Martin Bullinger, Mehrad Abbaszadeh and Arash Norozzade.

[David Kempe]

Hi everyone,

a small correction: Edith's talk will be this coming *Thursday*
(03/19) at noon in GCS 302C. So exactly our usual time and location
for theory talks.
We had a lot of confusing back and forth behind the scenes, so it's no
wonder Devansh got a little confused. (I was, too.)

>--
>You received this message because you are subscribed to the Google Groups
>"USC Computer Science Theory Announcements" group.
>To unsubscribe from this group and stop receiving emails from it, send an
>email to usc-theory+...@googlegroups.com.
>To view this discussion visithttps://groups.google.com/d/msgid/usc-theory/CAHYAtDipTDEgZm4xvcVuOWt14VgHx
>qnJ7Dn0jbtfUb4K_CUPjg%40mail.gmail.com.
>
>

--
David Kempe <david....@gmail.com>