Person:

Rao, Malvika

We consider a setting in which a worker and a manager may each have information about the likely completion time of a task, and the worker also affects the completion time by choosing a level of effort. The task itself may further be composed of a set of subtasks, and the worker can also decide how many of these subtasks to split out into an explicit prediction task. In addition, a worker can learn about the likely completion time of a task as work on subtasks completes. We characterize a family of scoring rules for the worker and manager such that information is truthfully reported, best effort is exerted by the worker in completing tasks as quickly as possible, and collusion is not possible. We study the factors influencing when a worker will split a task into subtasks, each forming a separate prediction target.

The design of incentives becomes challenging when faced with externalities. In this thesis I resolve this difficulty in two settings: position auctions and software economies. The first part of the thesis studies value externalities in position auctions. I develop a constraint-based model that allows an advertiser to submit, along with its bid, additional constraints to state how its value for clicks depends on the positions of the other ads with which it is allocated. I establish complexity results for winner determination and prove the existence of Nash and envy-free equilibria under certain conditions.

A significant contribution of this thesis is that it proposes a foundation for software economies. I first study a setting in the private software economy consisting of a single task, a worker, and a manager. This is a combination of a repeated principal-agent problem and a prediction problem. I characterize a scoring system that elicits truthful information, leading to accurate predictions from both agents and best effort from the worker.

In the public software economy, I consider the problem of how to incentivize deep fixes to bugs from both computational as well as theoretical perspectives. In the computational work, I introduce a dynamic model of the software ecosystem and propose subsumption mechanisms as a solution. Next, I adapt an approximation methodology that is well-suited to large market settings, known as mean field equilibrium, to the model. I conduct an experimental study to characterize the system in equilibrium and derive lessons for market design.

I perform theoretical analysis of a simple mean field model of deep fixes and prove the existence of a mean field equilibrium. Further, I define a new type of dynamic market equilibrium, called correctness equilibrium, and prove its existence. Finally I consider the relationship between mean field equilibrium and correctness equilibrium, showing that mean field equilibrium need not satisfy a notion of efficiency whereas correctness equilibrium does.

Software correctness has bedeviled the field of computer science since its inception. Software complexity has increased far more quickly than our ability to control it, reaching sizes that are many orders of magnitude beyond the reach of formal or automated verification techniques.

We propose a new paradigm for evaluating "correctness" based on a rich market ecosystem in which coalitions of users bid for features and fixes. Developers, testers, bug reporters, and analysts share in the rewards for responding to those bids. In fact, we suggest that the entire software development process can be driven by a disintermediated market-based mechanism driven by the desires of users and the capabilities of developers.

The abstract, unspecifiable, and unknowable notion of absolute correctness is then replaced by quantifiable notions of correctness demand (the sum of bids for bugs) and correctness potential (the sum of the available profit for fixing those bugs). We then sketch the components of a market design intended to identify bugs, elicit demand for fixing bugs, and source workers for fixing bugs. The ultimate goal is to achieve a more appropriate notion of correctness, in which market forces drive software towards a correctness equilibrium in which all bugs for which there is enough value, and with low enough cost to fix, are fixed.

We study the problem of how to incentivize deep fixes to software bugs, where a deep fix attempts to correct the root cause of the bug instead of just suppressing it superficially. To this end we introduce a dynamic model of the software engineering ecosystem. We then solve this problem by proposing subsumption mechanisms. In a subsumption mechanism, deeper fixes can replace or subsume shallower fixes and a worker’s payoff increases if his fix subsumes other fixes. We use a solution concept known as mean field equilibrium, an approximation methodology suited to large market settings. Taking a computational approach, we simulate the dynamic model of the ecosystem with subsumption mechanisms. Our algorithm achieves convergence and thus estimates a mean field equilibrium. We further compare our mechanism to baseline mechanisms using metrics, such as percentage of bugs receiving deep fixes, rate of bugs fixed, and cost to the user. Simulation results indicate that the subsumption mechanism performs favourably versus the baseline mechanisms.

Software construction has typically drawn on engineering metaphors like building bridges or cathedrals, which emphasize architecture, specification, central planning, and determinism. Approaches to correctness have drawn on metaphors from mathematics, like formal proofs. However, these approaches have failed to scale to modern software systems, and the problem keeps getting worse. We believe that the time has come to completely re-imagine the creation of complex software, drawing on systems in which behavior is decentralized, self-regulating, non-deterministic, and emergent---like economies. In this paper we describe our vision for, and prelimary work on, the creation of software economies for both open systems and internal corporate development, and our plans to deploy these ideas within one of the largest developer communities at IBM.

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 NPhard, we bound the approximation ratio for social welfare in eGSP and provide parameterized complexity results.