=Paper=
{{Paper
|id=Vol-1678/paper15
|storemode=property
|title=Iterative Committee Elections for Collective Decision-Making in a Ride-Sharing Application
|pdfUrl=https://ceur-ws.org/Vol-1678/paper15.pdf
|volume=Vol-1678
|authors=Sophie L. Dennisen,Jörg P. Müller
|dblpUrl=https://dblp.org/rec/conf/ijcai/DennisenM16
}}
==Iterative Committee Elections for Collective Decision-Making in a Ride-Sharing Application==
https://ceur-ws.org/Vol-1678/paper15.pdf
Iterative committee elections for collective decision-making in a ride-sharing
application∗
Sophie L. Dennisen, Jörg P. Müller
Institut für Informatik
Technische Universität Clausthal
38678 Clausthal-Zellerfeld, Germany
sophie.dennisen@tu-clausthal.de, joerg.mueller@tu-clausthal.de
Abstract on all possible destinations. In this context, the question
arises how to agree on a common subset of destinations to
We investigate the use of voting methods for mul- visit.
tiagent decision-making in cooperative traffic ap- We propose to use committee voting rules to design an ini-
plications. We consider a ride-sharing problem in tial solution and to allow dissatisfied passengers to leave the
which passengers use committee elections to col- group and to apply iterative winner determination until all re-
lectively decide on sets of points of interest to visit. maining passengers are satisfied with the selected subset of
In this paper, we propose an iterative voting pro- destinations.
tocol for the committee voting rules Minisum Ap- The trend in transportation systems goes towards automa-
proval and Minimax Approval. Using this proto- tisation, i.e. non-automated vehicles will be replaced by au-
col, voters can leave a group if their dissatisfac- tonomous vehicles over time, increasing safety and decreas-
tion with the election result exceeds a threshold ing environment pollution.
value. We evaluate the rules for the ride-sharing Our model is motivated by a future scenario in which tradi-
problem using an agent-based simulation. Our re- tional urban traffic is replaced by autonomous vehicles (AVs),
sults indicate that for initial group sizes around 20, where the city provides AVs for visitors of the city. Once a
both rules tend to require equal numbers of iter- visitor boards an AV, s/he transmits his/her preferences re-
ations for dissatisfaction threshold values around garding the possible destinations etc. to the AV, e.g. via
zero. We showed that Minisum Approval needs dis- smartphone app.
tinctly fewer iterations than Minimax Approval for From the perspective of the urban traffic management,
values between zero and half the size of the candi- pooling the visitors into as large groups as possible is desir-
date set. In some cases, for values around half the able as it reduces energy consumption and increases safety.
size of the candidate set, Minimax needs fewer it- Thus, we assume that the urban traffic management encour-
erations. For higher values, both rules need tenden- ages the visitors to group together in autonomous vehicles as
tially the same number of iterations. When aiming soon as they enter the intraurban area.
at minimising the number of iterations, we recom- We assume that the visitors are grouped together in au-
mend to apply Minisum Approval for threshold val- tonomous shared vehicles (ASVs) provided by the city at pre-
ues between zero and half the size of the candidate fined boarding points, as proposed by Dennisen and Müller
set. For higher values, we recommend to use Mini- [2015].
max Approval. We focus on visitors who submit their preferences regard-
ing all possible destinations in the respective urban area.
1 Introduction This approach raises several questions.
There are diverse approaches for vehicle routing and ride- 1. How can the passengers of a shared vehicle agree on a
sharing problems. In vehicle routing, the goal is to design common route?
a low-cost route so that each node is visited by exactly one 2. How should one deal with passengers who are not satis-
vehicle. In ride-sharing, it is usually assumed that each pas- fied with the selected route?
senger has exactly one desired destination.
Here, we consider another approach for the situation that 1.1 Outline
the passengers of the shared vehicles submit their preferences The remainder of the paper is structured as follows. In Sec-
∗ tion 2, the state-of-the-art is depicted, and in Section 3 the
This research has been supported by the German Research
Foundation (DFG) through the Research Training Group Social- research gap is described. Section 4 gives an overview on the
Cars: Cooperative (De-)centralized Traffic Management (GRK definitions, our solution approach and the voting architecture
1931). The focus of the SocialCars Research Training Group is on used for the simulations. Section 5 describes an example sce-
significantly improving the citys future road traffic, through cooper- nario. Section 6 includes the experimental settings, the results
ative approaches. This support is gratefully acknowledged. and the discussion, and Section 7 concludes the paper.
2 State-of-the-art 2.4 Rural Flexible Transport Systems
Velaga et al. [2012] developed a passenger-centric agent-
There is a range of works on the areas Ride-Sharing, Vehi-
based flexible transport systems (FTS) platform using argu-
cle Routing and Transportation Systems. Here, we discuss a
mentation theory. Each passenger provides the following in-
selection of those works.
formation:
2.1 The Vehicle Routing Problem • origin
• destination
According to the review paper by Laporte [1992], the Vehicle
Routing Problem (VRP) is defined as follows. • travel time window
Input: G = (V, A) graph where V = {1, .., n} is a set of • order of preference among: travel cost, number of
vertices representing cities with the depot located at vertex changes and journey length.
1, and A is the set of arcs. With every arc (i, j), i 6= j, is The first three items are requirements, i.e. conditions that
associated a non-negative distance matrix C = (cij ). In some must be fulfilled for a journey to be a candidate.
contexts, cij can be interpreted as travel cost or travel time. The brokering subsystem gathers all the plausible journeys
The goal is to design a set of least-cost vehicle routes so and composes a certain number of allocations, i.e. an assign-
that ment of passengers to sequences of vehicles.
The final step is to choose the globally preferred allocation
• each city except for the depot is visited by exactly one from this set. For this, Velaga et al. [2012] use a variation
vehicle of the Borda voting rule; each of the passenger agents votes
• all vehicle routes start and end at the depot by assigning a rating to each candidate allocation, and the
allocation with the best rating wins. Velaga et al. [2012] do
• some side constraints are satisfied not consider committee elections.
2.2 Dynamic ride-sharing 3 Research Gap
In the review article by Agatz et al. [2012], the authors re- According to Laporte [1992], in the VRP, the objective func-
fer by dynamic ride-sharing to a system where an automated tion is usually dependent on travel time or travel cost, depend-
system made available by a ride-sharer provider matches up ing on the edges. In our approach, we focus on agreeing on a
drivers and riders on short notice. common subset of POIs, disregarding the routing problem in
Most studies on ride-sharing consider one of the following the first phase.
specific objectives when determining ride-sharing matches. In the RFTS model by Velaga et al. [2012], the candidates
are a number of plausible assignments of passengers to jour-
• Minimise system-wide vehicle-miles neys, not the points of interest (POIs), i.e. the construction of
the journeys is independent from the voting process. In our
• Minimise the system-wide travel time approach, the voting process is necessary for the construction
• Maximise the number of participants of the routes.
Bistaffa et al. [2014] do not consider the preferences of
In ride-sharing, it is assumed that each rider wants to travel passengers over several destinations, but assume that each
from his/her origin to his/her destination. passenger has exactly one desired destination and generate
coalitions with minimal cost routes.
2.3 Sharing Rides with Friends None of these approaches focuses on how to agree on a
common subset of destinations to visit based on the passen-
One aspect which has been considered regarding ride-sharing gers’ preferences over all possible destinations.
is the constraints of the social network connecting the com- In this paper we propose that the passengers of a shared
muters. Bistaffa et al. [2014] consider the Social Ridesharing vehicle agree on a common subset of destinations to visit
Problem, where a set of commuters, connected through a so- via committee election and to apply iterative winner deter-
cial network, arrange one-time rides at short notice. They mination until all remaining passengers are satisfied with the
focus on the associated optimisation problem of forming the selected subset of destinations, i.e. in each iteration, the
cars to minimise the travel cost of the overall system, mod- most dissatisfied passenger leaves the group and the remain-
elling the problem as a graph constrained coalition formation ing votes are re-evaluated.
(GCCF) problem, where the set of feasible coalitions is re- From the operative perspective, a small number of itera-
stricted by a graph, i.e. the social network. tions is desirable: On the one hand, the fewer iterations are
They assume real-time ride-sharing, arranging one-time conducted, the more passengers are left and the better the ca-
rides with private cars and focus on providing an approach pacity of the shared vehicle is utilised. On the other hand,
that, given the desired starting points and destinations of a in each iteration communication between the visitors and the
community of commuters, can share cars to lower associated chair is required, i.e. minimising the number of iterations re-
transportation costs, i.e. travel time and fuel, while consid- duces the communication expense.
ering the constraints imposed by the social network that con- Thus, in this paper, we focus on the following research
nects such commuters. questions.
Assuming that visitors group together dependent on their
time of arrival (i.e. in a random fashion) and only change
Committee voting rules for scenario
to other shared vehicles at the starting point(s), decide on a
common route via commitee election: Both committee voting rules considered for the ride-sharing
scenario assume Approval vectors, i.e. votes from {0, 1}n ,
1. How do different committee voting rules under an iter- where a “0” at i-th position stands for disapproval and a “1”
ative protocol compare regarding the number of itera- at i-th position for approval of the i-th candidate.
tions? Following Brams et al. [2007a,b], the dissatisfaction of a
voter v with a selected committee com is measured via the
2. Given a committee voting rule, how many iterations will Hamming distance HD(v, com).
tendentially be conducted until the committee election is
terminated?
Minisum Approval Minisum Approval selects a commit-
tee for which the sum of the Hamming distances between all
4 Definitions and Methods votes and the committee is minimal. This corresponds to a
utilitarian approach.
4.1 Definitions
Election Minimax Approval Minimax Approval as proposed
Here, we follow the definition in Rothe et al. [2012]. An by Brams et al. [2007a,b]; Kilgour et al. [2006] selects a com-
election is defined as a tuple (C, V ) where C = {c1 , ..., cm } mittee for which the maximum Hamming distance between a
is the set of candidates and V = {v1 , ..., vn } is the list of vote and the committee is minimal. This corresponds to an
votes over C. Each voter is represented via his/her vote which egalitarian approach.
specifies his/her preferences over the candidates in C. Which
form the votes take depends on the voting rule. 4.2 Approach
Under the assumption that visitors of a city are encouraged to
Voting Rule
conduct round-trips in shared vehicles provided by the city,
Following Rothe et al. [2012], given a candidate set there is the question how the passengers of a shared vehicle
C, a voting rule is a social-choice correspondence f : agree on a common route. We assume that the vehicles can
{(C, V )|(C, V ) is a valid election} −→ P(C) which assigns rank in size from taxi size to bus size.
to each valid election (C, V ) a set of winning candidates. To We propose to use committee elections to agree on an ini-
determine a unique winner, it can be necessary to apply a tie- tial solution. When considering the initial solution, it is pos-
breaking rule. sible that some passengers are dissatisfied. Such dissatisfied
passengers can be allowed to leave the shared vehicle at the
Committee election start point(s) and change to other vehicles. This leads to it-
Analogously to the above definition, a committee election can erative winner determination. We propose to use an iterative
be defined as a tuple (C, V, k) with non-negative integer k ≤ voting protocol as depicted in Figure 1. The figure depicts the
m = |C|. steps for the non-iterative protocol as described in Dennisen
and Müller [2015] in solid lines and the additional steps for
Committee voting rule the iterative protocol in dashed lines.
Analogously to voting rules, one can define committee voting
rules. For a given candidate set C and non-negative integer
k ≤ m = |C|, a committee voting rule is a function which as-
signs to each valid committee election (C, V, k) a set of win-
ning committees. To determine a unique winning committee,
it can be necessary to apply a tie-breaking rule.
Following the definition in Baumeister et al.
[2015], a committee voting rule is a mapping
g : {(C, V, k)|(C, V, k) is a valid committee election} −→
Fk (C) with Fk (C) the set of all committees from C of size
k.
Voting protocol
Here, we use the notion of voting protocols in the sense that
a voting protocol defines the communication processes be-
tween the agents involved in the election.
Voting mechanism
In the context of this paper, a voting mechanism consists of a
voting protocol and a voting rule or committee voting rule. Figure 1: Centralised iterative protocol
In the non-iterative protocol, the chair starts the election by protocol/rule; this is realised via customisation of the Agent
sending an election message to all voters and the voters Architecture class.
respond by submitting their votes to the chair. As soon as Which modules in the Agent Architecture class are used
the chair has received all votes, s/he computes the result of by the respective agent depends on the role of the agent. The
the election according to the given voting rule and sends the chair agent uses the election launcher module responsible for
result to all voters. starting the election, the votes manager module which col-
In the iterative protocol, after receiving the result, the vot- lects the votes and the winner determination module which
ers check via a dissatisfaction threshold if they are dissatisfied computes the result of the votes according to the voting rule.
with the result. Based on their (unaltered) votes, they submit The voter agents uses the voting module responsible for sub-
a satisfied or a dissatisfied message to the chair. mitting votes.
If there is at least one dissatisfied voter, the chair removes
the most dissatisfied voter and computes the result for the re- 5 Example scenario
maining voters. Otherwise, the election is terminated.
Consider as example the following scenario. Four visitors
4.3 Voting Architecture t1 , t2 , t3 , t4 who want to visit Manhattan, NY form together
to a group at a predefined point s in Northern Manhattan.
Each of them submits his/her preferences regarding all possi-
ble POIs. Due to time constraints on the operative side, their
common route can only cover exactly three POIs. For sim-
plicity, we assume that there are six possible POIs: Guggen-
heim Museum (pG ), MoMA (pM ), Times Square (pT ), Em-
pire State Building (pE ), Flatiron Building (pF ) and China-
town (pC ). The corresponding graph is depicted in Figure
3.
Figure 3: Graph for illustrating example
s pG pM pT pE pF pC
Figure 2: Voting Architecture
We decided to evaluate the behaviour of different voting In the simplest model, the passengers of a shared vehicle
mechanisms via multiagent-based simulation. This allows for submit their preferences in form of approval votes, i.e. they
testing diverse input combinations and later extension to dy- indicate approval of a candidate by assigning a “1” to it and
namic traffic simulations. disapproval of a candidate by assigning a “0” to it.
As a voting architecture, we developed an adaptation of In the illustrating scenario, we assume that the visitors sub-
J-MADeM, an agent-based architecture implemented in Ja- mit their preferences as approval vectors. In this case, one
son by Grimaldo et al. [2010]. Jason is an interpreter de- can apply the committee voting rule Minisum Approval. The
veloped by Bordini et al. [2005], written in Java for an ex- votes and the scores are depicted in Table 1.
tended version of AgentSpeak, a logic-based agent-oriented
programming language that is suitable for the implementation
of reactive planning systems according to the Belief-Desire- Table 1: Approval scores for illustrating example
Intention (BDI) architecture. POI pG pM pT pE pF pC
Currently, in our voting architecture, two voting protocols t1 1 0 1 1 0 1
and two committee voting rules are implemented. The ar- t2 1 0 1 1 0 0
chitecture allows for extension to further voting protocols t3 1 0 1 0 1 0
and voting rules such as decentralised non-iterative protocols, t4 0 0 0 1 1 1
decentralised iterative protocols, the voting rules Condorcet Score 3 0 3 3 2 2
(based on pairwise comparisons), Borda and the committee
voting rule Minisum-Ranksum (based on positional scores) For committee size k = 3, the winning committee is K =
as described in Baumeister and Dennisen [2015]. {pG , pT , pE }. Assuming that the shared vehicle drives from
The architecture is structured as depicted in Figure 2. The North to South until it heads back to its starting point, the
Jason Runtime handles the agent cycles and the communica- shared vehicle would take the route s → pG → pT → pE →
tion between the agents. The chair and voter agents are lo- s, as depicted in Figure 4.
cated in a parameterised environment. They receive the sim- For approval vectors, the straightforward approach to mea-
ulation parameters in form of initial beliefs and call the voting sure the dissatisfaction with an elected committee is to con-
• the number m of candidates (POIs)
Figure 4: Resulting route
• the size k of the committee to be elected
• the dissatisfaction threshold t
• the committee voting rules
s pG pM pT pE pF pC
• the voting protocol(s)
For each run, the votes are generated as follows: For each
position in each vote, a “1” or a “0” is selected with equal
probability, resulting in homogenous electorates.
sider the Hamming distance between the respective vote and In each run, the number of necessary iterations is saved.
the elected committee. We measured and compared the number of iterations un-
The Hamming distances between the votes and the elected der the iterative protocol for Minimax Approval and Minimax
committee pG , pT , pE are depicted in Table 2 Approval for several input combinations (n, m, k, t).
In each simulation, we conduct 100 runs and mea-
sure the median of the numbers of iterations for Min-
Table 2: Hamming distances for illustrating example isum and Minimax as well as the median of differences
1 0 1 1 0 0 Hamming distance iteration minisum − iterations minimax. In our sim-
t1 1 0 1 1 0 1 1 ulations, we consider three different settings.
t2 1 0 1 1 0 0 0
t3 1 0 1 0 1 0 2 1. Vary the values for dissatisfaction threshold t
t4 0 0 0 1 1 1 4 2. Vary the values for committee size k
3. Vary the values for number of candidates m
Assuming dissatisfaction threshold t = 2, t4 leaves the
group and looks for another shared vehicle. 6.2 Results
Exploring the impact of dissatisfaction threshold t on
Table 3: Approval scores for illustrating example, second it- iteration numbers
eration In our first setting, we considered all possible values of dis-
POI pG pM pT pE pF pC satisfaction threshold t for number of voters n = 20, num-
t1 1 0 1 1 0 1 ber of candidates m = 10, committee size k = 5, i.e.
t2 1 0 1 1 0 0 0 ≤ t ≤ m = 10. The results are depicted in Figure 5.
t3 1 0 1 0 1 0 The figure shows that the number of iterations decreases for
Score 4 0 4 3 1 1
both voting rules with increasing dissatisfaction threshold t.
For values of t around 0, it is impossible to satisfy the voters,
In this case, the removal of the dissatisfied voter does not so that both voting rules need 20 iterations, creating empty
alter the outcome of the committee election, so the route stays groups. For smaller values of t above zero, i.e. for hard-
the same. to-please voters, Minisum needs tendentially fewer iterations
than Minimax. For values of t above m/2 and near m/2, i.e.
6 Evaluation for more tolerant voters, Minimax needs fewer iterations than
We investigated the impact of the dissatisfaction threshold for Minisum. For higher values, both rules need zero iterations.
the visitors t, the number of POIs to be visited k and the num- Consider the input combination n = 20, m = 10, k =
ber of offered POIs m on the number of iterations needed by 5, t = 4. The boxplot for the differences between Minisum
the voting rules Minisum and Minimax Approval. and Minimax is depicted in Figure 6. The median of the dif-
ferences is −3, i.e. Minisum needs tendentially 3 iterations
6.1 Experimental Settings fewer than Minimax for dissatisfaction value t = 3.
Our simulations were conducted with the following technical For t = 4, the Wilcoxon rank sum test with continuity
settings. correction yields W = 988.5 and p-value < 2.2e − 16 <
0.05, i.e. we can reject the null hypothesis that there is no
• Jason-1.4.2 statistical difference between the distributions.
• Java 1.8.0 65 Consider the input combination n = 20, m = 10, k =
• Windows 8.1 5, t = 6. The boxplot for the differences between Minisum
and Minimax is depicted in Figure 7. The median of the dif-
• HDF5 for storing input and output data ferences is 1, i.e. Minimax needs tendentially one iterations
• R x64 3.2.3 for evaluation fewer than Minisum.
For t = 6, the Wilcoxon rank sum test with continuity
As configuration parameters for the simulation, we have correction yields W = 8734.5 and p-value < 2.2e − 16 <
• the number n = 20 of voters (visitors): n = 20 is ori- 0.05, i.e. we can reject the null hypothesis that there is no
ented towards bus sizes statistical difference between the distributions.
#(Iterations Minisum) − #(Iterations Minimax)
20
Minisum
Minimax
●
5
Difference
15
●
4
10
3
5
2
0
1
−5
0
Figure 7: Boxplot of differences for n = 20, m = 10, k = 5,
0 2 4 6 8 10 t=6
dissatisfaction threshold t
rules need fewer iterations for medium values of k. Here,
Figure 5: Median of iteration numbers for Minisum and Minimax needs one iteration fewer than Minisum for medium
Minimax and median of differences (Minisum-Minimax) for values of k. For other values of k, both rules need tendentially
n = 20, m = 10, k = 5 against dissatisfaction threshold t. the same number of iterations.
#(Iterations Minisum) − #(Iterations Minimax)
Table 4: Medians for m = 10, n = 20, t = 5 and varying k
k Iterations Minisum Iterations Minimax Difference
● 1 6 7 -1
2 5 6 -1
2
3 5 5 -1
4 5 5 -1
0
5 4 5 -1
−2
6 4 5 -1
7 5 6 -1
8 5 6 -1
−4
9 7 9 -1
−6
−8
Table 5: Medians for m = 10, n = 20, t = 6 and varying k
k Iterations Minisum Iterations Minimax Difference
Figure 6: Boxplot of differences for n = 20, m = 10, k = 5,
1 2 2 0
t=4 2 2 1 0
3 2 0 1
4 1 0 1
Exploring the impact of committee size k on iteration 5 1 0 1
numbers 6 1 0 1
In the second setting, we fixed the number of candidates m = 7 2 0 1
10 the number of voters n = 20, varied committee size k, 8 2 1 1
i.e. the number of effectively visited POIs and measured the 9 2 3 0
median of differences for dissatisfaction threshold values t =
5 and t = 6. Consider the input combination n = 20, m = 10, k =
The results for t = 5 are depicted in Table 4 and Figure 8, 5, t = 6. The boxplot for the differences between Minisum
the results for t = 6 in Table 5 and Figure 9. and Minimax is depicted in Figure 10. The median of the dif-
Table 4 shows that both voting rules need fewer iterations ferences is 1, i.e. Minimax needs tendentially one iterations
for medium values of k, i.e. the closer k is to m/2, the fewer fewer than Minisum.
iterations are needed. For t = 5, the median of the differences The Wilcoxon rank sum test with continuity correction
between Minisum and Minimax is −1, i.e. Minisum needs yields W = 8667.5 and p-value < 2.2e − 16 < 0.05, i.e.
tendentially one iteration fewer than Minimax. we can reject the null hypothesis that there is no statistical
Table 5 and Figure 9 show a similar trend. Both voting difference between the distributions.
20
20
Minisum Minisum
Minimax Minimax
Difference
15
Difference
15
10
10
5
5
0
0
−5
−5
2 4 6 8
2 4 6 8
committee size k
committee size k
Figure 9: Median of iteration numbers for Minisum and
Figure 8: Median of iteration numbers for Minisum and Minimax and median of differences (Minisum-Minimax) for
Minimax and median of differences (Minisum-Minimax) for n = 20, m = 10, t = 6 against committee size k
n = 20, m = 10, t = 5 against committee size k
#(Iterations Minisum) − #(Iterations Minimax)
Exploring the impact of number of candidates m on
iteration numbers 4 ●
In the third setting, we fixed n = 20, k = 5, t =
bm/2c , dm/2e and measured the median of differences for
3
different numbers of offered POIs m = 10, 15, 20. The re-
sults are depicted in Table 6.
2
Table 6: Median of differences for m = 10, 15, 20, n =
1
20, k = 5, t = bm/2c, dm/2e
Minisum Minimax Difference
0
m = 10, k = 5, t = 5 4 4.5 -1
m = 15, k = 5, t = 7 6 6 0
m = 15, k = 5, t = 8 3 1 2
m = 20, k = 5, t = 10 5 4 1 Figure 10: Boxplot of differences for n = 20, m = 10, k =
5, t = 6
Table 6 shows no clear relation between the number of the
candidates and the iteration numbers for Minisum and Min- If k lies around m/2, Minimax needs tendentially fewer
imax Approval. For m = 15, k = 5, one can again see the iterations than Minisum for values of t close to m/2, i.e. for
influence of t on the numbers of iterations. more tolerant voters.
For higher values of t, the difference decreases until both
6.3 Discussion committee voting rules tend to need the same number of iter-
Assuming shared vehicles with a capacity of 20 and numbers ations.
of offered POIs up to 20, our results indicate that a favourable In practice, there are several motives for minimising the
constellation from operative perspective would be to offer two number of iterations.
times as many POIs as can be visited by a shared vehicle - the • Capacity utilisation: The fewer iterations are conducted,
voting rules need fewer iterations if the number of effectively the more visitors remain in the shared vehicle
visited POIs lies around half the number of offered POIs.
• Communication expense: In each iteration, the visitors
The dissatisfaction threshold has an considerable impact:
have to communicate with the chair in order to indicate
For threshold values around 0, Minisum and Minimax tend to
if they are satisfied or dissatisfied.
need the same number of iterations. For higher values below
m/2, i.e. if the voters are hard to please, Minisum needs In order to minimise the number of iterations, we recom-
distinctly fewer iterations than Minimax. mend to apply Minisum Approval for the case that it is ex-
pected that the visitors are hard-to-please. If you expect that European Journal of Operational Research, 223(2):295–
the visitors are more tolerant, we recommend to use Minimax 303, 2012.
Approval. Dorothea Baumeister and Sophie Dennisen. Voter Dissat-
So far, Computational Social Choice methods have been isfaction in Committee Elections. In Proceedings of the
largely subject to theoretical analysis. There are hardly any 2015 International Conference on Autonomous Agents and
attempts to use them in the engineering of socio-technical Multiagent Systems, pages 1707–1708. International Foun-
multiagent systems such as traffic modeling and management. dation for Autonomous Agents and Multiagent Systems,
The ride-sharing scenario is relatively simple but we believe 2015.
it is yet suitable as an experimental scenario due to its relative
generality and the relevance (and hardness) of the underlying Dorothea Baumeister, Sophie Dennisen, and Lisa Rey. Win-
optimisation problems. The concept is applicable for non- ner Determination and Manipulation in Minisum and Min-
autonomous driving as well: In the case of non-autonomous imax Committee Elections. In Algorithmic Decision The-
driving, one could equate the chair agent with the owner/ ory, pages 469–485. Springer, 2015.
driver. Filippo Bistaffa, Alessandro Farinelli, and Sarvapali D Ram-
Our next step will be to reproduce our results for further churn. Sharing rides with friends: a coalition formation
input combinations (n, m, k, t). Note that we conducted in- algorithm for ridesharing. 2014.
vestigations for relative small numbers of available POIs. For Rafael H Bordini, Jomi F Hübner, and Renata Vieira. Jason
larger numbers of POIs, we aim to compare the properties of and the golden fleece of agent-oriented programming. In
Minisum Approval and Minimax Approximation algorithms. Multi-agent programming, pages 3–37. Springer, 2005.
In the setting considered in this paper, we used a a fixed
dissatisfaction threshold to determine the dissatisfaction of Steven J Brams, D Marc Kilgour, and M Remzi Sanver.
the visitors. In a dynamic scenario, it would make sense to A Minimax Procedure for Electing Committees. Public
let the visitors decide individually if they are satisfied or dis- Choice, 132(3-4):401–420, 2007a.
satisfied. To simulate this, one would need a stochastic model Steven J Brams, D Marc Kilgour, and M Remzi Sanver. A
to determine the dissatisfaction thresholds. Minimax Procedure for Negotiating Multilateral Treaties.
Furthermore, we will consider the situation that the voters In Diplomacy games, pages 265–282. Springer, 2007b.
cannot only leave their initially assigned groups but change Sophie L Dennisen and Jörg P Müller. Agent-Based Voting
to another groups. Architecture for Traffic Applications. In Multiagent System
Also, a challenge for future research is to study the run- Technologies, pages 200–217. Springer, 2015.
time performance of the voting mechanisms taking the time
requirements of collective decision situations in real traffic Francisco Grimaldo, Miguel Lozano, Fernando Barber, and
into account. Alejandro Guerra-Hernández. J-MADeM v1. 1: A full-
fledge AgentSpeak (L) multimodal social decision library
in Jason. In The 8th European Workshop on Multi-Agent
7 Conclusion Systems (EUMAS 2010), 2010.
In this paper, we investigated the usability of methods known D Marc Kilgour, Steven J Brams, and M Remzi Sanver. How
from tha area of computational social choice in future cooper- to Elect a Representative Committee using Approval Bal-
ative traffic environments consisting of automated or human- loting. In Mathematics and Democracy, pages 83–95.
operated vehicles, able to communicate with each other, e.g. Springer, 2006.
using Vehicle-to-X communication technologies. In particu- Gilbert Laporte. The vehicle routing problem: An overview
lar, we considered a ride-sharing scenario where visitors of a of exact and approximate algorithms. European Journal of
city share vehicles with seating capacities similar to buses to Operational Research, 59(3):345–358, 1992.
visit points of interest.
We proposed an iterative voting protocol based on the well- Jörg Rothe, Dorothea Baumeister, Claudia Lindner, and Irene
known Minisum Approval and Minimax Approval committee Rothe. Einführung in Computational Social Choice: In-
voting rules, allowing dissatisfied travellers to leave a group dividuelle Strategien und kollektive Entscheidungen beim
and join a different one. Using an agent-based simulation, Spielen, Wählen und Teilen. Springer-Verlag, 2012.
we compared iterative Minisum Approval and Minimax Ap- Nagendra R Velaga, Nicolás D Rotstein, Nir Oren, John D
proval with respect to their convergence properties. Nelson, Timothy J Norman, and Steve Wright. Develop-
The main result is that iterative Minisum Approval outper- ment of an integrated flexible transport systems platform
forms Minimax approval in this respect for threshold values for rural areas using argumentation theory. Research in
higher than 0 and lower than m/2. If k lies around m/2, Transportation Business & Management, 3:62–70, 2012.
there is a slight advantage to Minimax Approval for values of
t close to m/2.
References
Niels Agatz, Alan Erera, Martin Savelsbergh, and Xing
Wang. Optimization for dynamic ride-sharing: A review.