An important question in a software economy is how to incentivize deep rather than shallow fixes. A deep fix corrects the root cause of a bug instead of suppressing the symptoms. This paper initiates the study of the problem of incentive design for open workflows in fixing code. We model the dynamics of the software ecosystem and introduce subsumption mechanisms. These mechanisms only make use of externally observable information in determining payments and promote competition between workers. We use a mean field equilibrium methodology to evaluate the performance of these mechanisms, demonstrating in simulation that subsumption mechanisms perform robustly across various environment configurations and satisfy important criteria for market design.

We introduce a bidding language for expressing negative value externalities in position auctions for online advertising. The unit-bidder constraints (UBC) language allows a bidder to condition a bid on its allocated slot and on the slots allocated to other bidders. We introduce a natural extension of the Generalized Second Price (GSP) auction, the expressive GSP (eGSP) auction, that induces truthful revelation of constraints for a rich subclass of unit-bidder types, namely downward-monotonic UBC. We establish the existence of envy-free Nash equilibrium in eGSP under a further restriction to a subclass of exclusion constraints, for which the standard GSP has no pure strategy Nash equilibrium. The equilibrium results are obtained by reduction to equilibrium analysis for reserve price GSP (Even-Dar et al. 2008). In considering the winner determination problem, which is NP-hard, we bound the approximation ratio for social welfare in eGSP and provide parameterized complexity results.

Minimum distance localization is the problem of finding the shortest possible path for a robot to eliminate ambiguity regarding its position in the environment. We consider the problem of minimum distance localization in self-similar environments, where the robot's sensor has limited visibility, and describe two randomized algorithms that solve the problem. Our algorithms reduce the risk of requiring impractical observations and solve the problem without excessive computation. Our results are validated using numerical simulations.