Towards fair and efficient public transportation: �The bus stop model��Edith Elkind �Northwestern University�joint work with �Martin Bullinger and Mohamad Latifian�

Participatory budgeting

• A set of P projects
• A budget b
• Each project p in P has a cost c_p
• Voters report preferences �over projects (utilities, approvals, etc.)
• Goal: select a budget-feasible�set of projects to fund �based on voters’ preferences
• Porto Alegre’89, Paris, New York, �Madrid, Cambridge (US), Evanston...

Participatory budgeting: goals

• Assume voters have approval preferences over projects ( or )
• Goal:
• Maximize social welfare?
• 51% of voters approve x, y, z worth b/3 each
• 49% of voters approve x', y', z' worth b/3 each
• Ensure fairness?
• Idea: large cohesive group of voters should be�represented in proportion to their size

Operationalizing fairness:�level of ambition = high

• Definition: core stability
• each voter controls b/n dollars
• voter’s utility: number of selected projects she approves
• an outcome S ⊆ P is in the core if �no group of voters N' can use �the money they control �to purchase a subset of projects Q ⊆ P �such that each voter in N' prefers Q to S
• downside: we don’t know if core is non-empty
• β-approximate core: no group can deviate if deviation shrinks its budget by β
• non-empty for β ≥ 32 (JMW’20)

Operationalizing fairness:�level of ambition = low

• Assume each project has cost 1�(multiwinner voting)
• each voter controls b/n dollars
• an outcome S ⊆ P provides justified representation (JR) if there is �no group of voters N' of size n/b such that
• there is a project p in P approved by all voters in N’
• each voter in N' approves no project in S
• several poly-time voting rules provide JR
• JR is a very weak property

Operationalizing fairness:�level of ambition = medium

• Assume each project has cost 1�(multiwinner voting)
• each voter controls b/n dollars
• an outcome S ⊆ P provides extended justified representation (EJR) if for each t there is �no group of voters N' of size tn/b such that
• there are t projects in P approved by all voters in N’
• no voter in N' approves t projects in S
• there is a poly-time voting rule that provides EJR (Method of Equal Shares)

Operationalizing fairness:�level of ambition = medium high

• General costs, approval ballots
• each voter controls b/n dollars
• an outcome S ⊆ P provides extended justified representation (EJR) if there is �no group of voters N' of such that
• voters in N' can jointly afford a set of projects Q
• all voters in N' approve all projects in Q
• no voter in N' approves |Q| projects in S
• there is a poly-time voting rule that provides EJR (Method of Equal Shares)

Beyond the standard model?

• Participatory budgeting is often used for urban planning
• Many urban planning issues are �not captured by the standard model
• cycle paths
• public transport routes
• What is a fair budget allocation �in the context of sustainable transport?

Ambition

• Fair selection of bus routes
• Why now?
• Challenges:
• frequencies
• transfers
• unobserved demand
• OR literature: typically, optimizing util �(and sometimes egal) welfare

​

Our work: choosing bus stop locations

• Single bus route running between 0 and U
• Set of m potential bus stop locations in [0, U]
• Budget b to build b stops
• n users
• user i wishes to travel from l _i to r_i
• User i can
• walk from l _i to r_i at cost |r_i – l _i|
• walk from l _i to a stop x, take a bus to stop y, �walk from y to r_i at cost |x- l _i| + α|y-x| + |r_i -y|
• α < 1 (possibly α = 0)

Utilitarian welfare

• Theorem: there is a poly-time algorithm� that chooses a set of b stops �to minimize the sum of the user costs
• dynamic programming
• Extends to:
• arbitrary additive cost functions �(uphill vs downhill, asphalt vs bricks)
• existing stops
• non-identical costs per stop (given in unary)

Fairness

• Each agent controls b/n dollars
• An outcome S is in the core if there is no set of agents N’ and no set of stops T such that N’ can afford T and for each i in N’ c_i(T) < c_i(S)
• An outcome S provides JR if there is no set of agents N’ with |N’|≥ 2n/b and no pair of stops T = {x, y} such that for each i in N’ c_i(T) < c_i(S)
• no group of agents can benefit �by building a single stop

Algorithm

• Theorem: for α = 0 (bus travel has no cost) �Algorithm 1 returns
• a JR solution
• a solution in the 2-core

Algorithm: analysis

• Theorem: for α = 0 (bus travel has no cost) �Algorithm 1 returns a solution in the 2-core
• Proof:
• let S be the solution returned by Algorithm 1
• suppose for contradiction agents in M deviate to T
• |T| ≤ b|M|/(2n)
• for a stop t in T, let M_t be the set of agents with at least one terminal closer to t than to every stop in S
• |M_t|< 2n/b
• |U _t∈T M_t| ≤ |T|2n/b <|M|
• hence, for some i in M each of her terminals is �closer to S than to T, a contradiction

Limitations

• Theorem: for α > 0 Algorithm 1 may �fail to return a JR solution
• Open problem: does a JR solution �always exist for α > 0?
• Theorem: Even for α = 0 Algorithm 1 may �fail to return a solution in (2- ε)-core
• Open problem: is core always non-empty?
• open even for α = 0
• Remark: 16-core is always non-empty (for all α)

​

Impossibility: strong JR

• An outcome S provides strong JR if there is �no set of agents N’ with |N’|≥ 2n/b and �no pair of stops T = {x, y} such that for each i in N’ c_i(T) ≤ c_i(S) and for some i in N’ c_i(T) < c_i(S)
• Theorem: there are instances in which� no outcome provides strong JR (even for α = 0)
• n = 8, b = 4
• 2n/b = 4: 4 agents “deserve” 2 stops
• in any solution, at least 4 agents are not served

​

Experiments