# Agreement Technologies for Coordination in Smart Cities
## 3 Applications
### Coordination of Traffic Flows through Intelligent Intersections
#### 3.1.1 Mechanism for Single Intersection
Once the new bids are collected, they constitute the bid set. Then, the auctioneer executes the algorithm for the winner determination problem (WDP), and the winner set is built, containing the bids whose reservation requests have been accepted. During the WDP algorithm execution, the auctioneer still accepts incoming bids, but they will only be included in the bid set of the next round. The auctioneer sends a _CONFIG_ message to all bidders that submitted the bids contained in the winner set, while a _REJECTION_ message is sent to the bidders that submitted the remaining bids. Then, a new round begins, and the auctioneer collects new incoming bids for a certain amount of time. Figure 3: Auction policy. Figure 2: Bundle of items for a reservation request. Notice that the auction must be performed in real time, so both the bid collection and the winner determination phase must occur within a specific time window. This implies that optimal and complete algorithms for the WDP are not suitable. Therefore, we used an approximation algorithm with _anytime_ properties (i.e., the longer the algorithm keeps executing, the better the solution it finds) [27]. We expect our policy based on combinatorial auction (CA) to enforce an inverse relation between the amounts spent by the bidders and their _delay_ (the increase in travel time due to the presence of the intersection). That is, the more money a driver is willing to spend for crossing the intersection, the faster will be its transit through it. For this purpose, we designed a custom, microscopic, time-and-space-discrete simulator, with simple rules for acceleration and deceleration [27]. The origin O and destination D of each simulated vehicle are generated randomly. The destination implies the type of turn that the vehicle will perform at the intersection, as well as the lane it will use to travel. We created different traffic demands by varying the expected number of vehicles \(\lambda\) that, for every O-D pair, are spawned in an interval of 60 s, using a Poisson distribution. The bid that a driver is willing to submit is drawn from a normal distribution with mean 100 cents and variance 25 cents, so the agents are not homogeneous in the sense that the amount of money that they are offering differs from one to another. Figure 4 plots (in logarithmic scale) the relation between travel time and bid value for values of \(\lambda\) = 20, with error bars denoting 9% confidence intervals. It clearly shows a sensible decrease of the delay experienced by the drivers that bid from 100 to 150 cents. The delay reduction tends to settle for drivers that bid more than 1000 cents. Similar results are achieved with lower and higher densities [27]. Notice that even with a theoretically infinite amount of money, a driver cannot experience zero delay when approaching an intersection, as the travel time is influenced by slower potentially \"poorer\" vehicles in front of it. Extensions to our mechanism that address this problem are subject to future work. We also analysed the impact that such a policy has on the intersection's _average_ delay, comparing it to the FCFS strategy. Figure 5 shows that when traffic demand is low, the performance of the CA policy and the FCFS is approximately the same but, as demand grows, there is a noticeable increase of the average delay when the intersection manager applies CA. The reason is that the CA policy aims at granting a reservation to the driver that values it the most, rather than maximising the number of granted requests. Thus, a bid \(b\) whose value is greater than the sum of \(n\) bids that share some items with \(b\) is likely to be selected in the winner set. If so, only one vehicle will be allowed to transit, while \(n\) other vehicles will have to slow down and try again. When extending the CA mechanism to multiple intersections, we tried to reduce this \"social cost\" of giving preference to drivers with a high valuation of time. Figure 4: Bid-delay relation.