We consider a multi-retailer system where the sellers are connected with each other via a transportation network and the transactions with the consumers happen on a platform. Each consumer is serviced by only one retailer. Since the demands to the sellers (i.e., the retailers on the platform) are stochastic in nature, supplies can be either in excess or in deficit. Transshipping these items laterally among the retailers benefits both, the platform and the retailers. For retailers, excess supply leads to wastage and deficit to a loss of revenue, while via transshipment, they get a better outcome. The platform can also earn some revenue in facilitating this process. However, only the sellers know their excess (which can be salvaged at a price or transshipped to another seller) or the deficit (which can be directly procured from a supplier or transshipped from another seller), both of which have multiple information that is private. We propose a model that allows lateral transshipment at a price and design mechanisms such that the sellers are incentivized to voluntarily participate and be truthful. Experimenting on different types of network topologies, we find that the sellers at more central locations in the network get an unfair advantage in the classical mechanism that aims for economic efficiency. We, therefore, propose a modified mechanism with tunable parameters which can ensure that the mechanism is more equitable for non-central retailers. Our synthetic data experiments show that such mechanisms do not compromise too much on efficiency, and also reduce budget imbalance.

Ride-hailing services’ main feature is mediating the assignment and transactions between drivers and passengers. Essentially, they decide on the quality of passengers’ experience and the drivers’ workload balancing. To boost the company’s profit, these services try to maximize the utility for the passengers by optimizing the matching, resulting in shorter waiting times and better service availability. Often, in the process of maximizing revenue, drivers’ interests get sidelined. We focus on two objectives: efficiency (minimizing total distance traveled by drivers) and fairness (minimizing the maximum traveled distance by any driver) for shared-mode rides, where the vehicles’ capacity is two passengers. We theoretically show the relation between the optimal solutions of both objectives and as the problem is computationally intractable, we propose a heuristic algorithm to achieve an approximately optimal solution. We also propose a re-assignment-based algorithm when the aim is to achieve maximum matching with fairness up to a given threshold, if that is feasible. The experimental analysis for the proposed algorithms on real-world data from Chicago city shows that our approach can significantly improve fairness for drivers without losing much efficiency.

We study the parameterized complexity of the optimal defense and optimal attack problems in voting. In both the problems, the input is a set of voter groups (every voter group is a set of votes) and two integers k_a and k_d corresponding to respectively the number of voter groups the attacker can attack and the number of voter groups the defender can defend. A voter group gets removed from the election if it is attacked but not defended. In the optimal defense problem, we want to know if it is possible for the defender to commit to a strategy of defending at most k_d voter groups such that, no matter which k_a voter groups the attacker attacks, the out-come of the election does not change. In the optimal attack problem, we want to know if it is possible for the attacker to commit to a strategy of attacking k_a voter groups such that, no matter which k_d voter groups the defender defends, the outcome of the election is always different from the original (without any attack) one. We show that both the optimal defense problem and the optimal attack problem are computationally intractable for every scoring rule and the Condorcet voting rule even when we have only3candidates. We also show that the optimal defense problem for every scoring rule and the Condorcet voting rule is W[2]-hard for both the parameters k_a and k_d, while it admits a fixed parameter tractable algorithm parameterized by the combined parameter (ka, kd). The optimal attack problem for every scoring rule and the Condorcet voting rule turns out to be much harder – it is W[1]-hard even for the combined parameter (ka, kd). We propose two greedy algorithms for the OPTIMAL DEFENSE problem and empirically show that they perform effectively on reasonable voting profiles.