Incentives without monetary transfers

The major difficulty of algorithm design has always been identified with the understanding of the combinatorial structure underlying the optimisation problem at hand. However, this might be only one source of complexity for algorithm design. Indeed, the emergence of the Internet as the computing platform has enriched the picture by highlighting the presence of agents that selfishly evaluate the outcome of the computation. As a consequence, nowadays, algorithms have also to work in the presence of these selfish interests, which are often in contrast with the ultimate objective of the computation (e.g., optimality). The field of Algorithmic Mechanism Design (AMD) has as its main scope the realignment of the objective of the designer with those of the selfish agents through the design of so-called truthful mechanisms. Truthfulness guarantees that agents have no interest in misguiding the mechanism towards the computation of "wrong" (e.g., suboptimal) outcomes.

Truthfulness, however, comes with a heavy price tag. Specifically, monetary transfers between designer and agents are needed, for otherwise the only truthful mechanisms are dictatorships as from the celebrated Gibbart-Satterthwaite theorem. On one hand, dictatorships are neither interesting nor useful as the outcome solution might be arbitrarily "bad" for the designer's objectives (e.g., with a poor approximation guarantee of the measure of interest). On the other hand, while money might be reasonable in some applications, little justification can be found, in general, for either the presence of a digital currency or the use of money at all. There are contexts in which money is morally unacceptable (e.g., to support certain political decisions) or even illegal (as, e.g., in organ donations).

This proposal aims at reconsidering the role of money as a 'necessary evil' in AMD. We propose to reconcile computation and incentives without the use of monetary transfers by leveraging restricted domains, approximation, and well-motivated, relaxed notions of truthfulness. In detail, Gibbart-Satterthwaite theorem is proved under the hypothesis that agents have unrestricted domains (i.e., unrestricted ways to misguide the algorithm), yet many computer science applications only have quite well structured domains. What kind of approximation guarantee of the optimum can we achieve if we insist on truthfulness without money when agents have restricted domains? Our third leverage is a novel application of the concept of verification in AMD. Verification, in this context, means that some kind of misbehaviour of the agents can be uncovered (and punished accordingly). This idea mimics what happens in real life where "inspections of job done" are often the norm and allows for a relaxed notion of truthfulness whereby the set of agents' misbehaving strategies does not contain verifiable ones. The concept of verification has been extensively used in AMD with money; we ask here to what extent we can trade money with verification. How good is the approximation guarantee of the solutions output of truthful mechanisms without money that use verification?

We want to advance our knowledge in this (largely) unexplored middle ground between truthfulness, approximation, and money in relation to fundamental optimisation problems, with many applications in real life, such as Combinatorial Auctions and Facility Location, as well as in a more abstract way by relating particular forms of verification to truthfulness, money and other measures of interest. Our study attempts to build the foundations of (i) a more applied use of AMD; and, (ii) the application of game-theoretic models to the non-profit sector.

This research mainly aims at advancing our understanding of the interplay between incentives and computation and the role of monetary transfers within. A first natural beneficiary of this research is then the academic community of game theorists, well established in the UK and abroad. Due to invasive presence of incentives and the importance of rationality in decision making, the research in game theory is rooted in a number of (traditionally) different academic disciplines: theoretical computer science, economics, social science, operation research, neuroeconomics, management, just to name a few. The research pursued in this proposal has the potential to impact all of these academic areas. A broad impact on computer science research can also be envisioned. The absence of monetary transfers from the picture makes it easier to apply ideas/results of this proposal to classical computer science applications (e.g., resource allocation in operating systems).

The main stakeholders of this proposal are charities. Charities are well present in the UK society: according to the Charity Commission data [1], their total number has steadily increased since recession has hit the economy; between 1999 and 2013, "large" charities have tripled in number, just as the total annual income of the sector, totalling now the impressive amount of £61.431 billion. A non-negligible amount is due to retail income, wherein donated goods are sold to the public. Financial statements of big charities, see, e.g., [2, 3], report the lower donation of goods from the public as one of the biggest financial risks for their organisations; this is confirmed by a worrying decrease in stock levels in recent years. Smaller charities seem to perform better on this aspect, managing an income in the region of a million pounds with few shops [4]. Given the current economic climate, the only prospect for progression and better distribution will arise from new economic models of donation. The research agenda proposed can profoundly impact this "market", hitherto overlooked by researchers in the field, despite its social relevance and importance. In particular, the moneyless combinatorial auctions designed in WP1 will be of great help to design a platform wherein charitable donations are centrally allocated/distributed to single charities. The interest in better approximations of the optimal social welfare is far from being just academic: the better the outcome, the bigger the effect of the billions of pounds involved. General public and society, therefore, also represent (a second-tier) beneficiary of this proposal. It is worthy to note that although charities and the non-profit sector have benefited from recent and generic developments such as crowdfunding, there are to this date no specific initiatives that would include them as stakeholders in the Connected Digital Economy. The proposed work can be seen as one of the first truly specific online funding technology targeted primarily at charities. Further impact can be argued about policy makers. In the current financial climate, any decision to spend tax-payers' money for public facilities should be carefully considered in order to improve its "value-for-money", yet we have many examples of white elephant projects. Governments could inform their decisions by simply submitting the incentive-compatible mechanisms for facility location (WP2) to the interested sector of the society without the need for financial means to incentivate truthtelling.

References
[1] Charity commission, Sector facts and figures. Available at www.charitycommission.gov.uk/about- charities/sector-facts-and-figures.
[2] British Heart Foundation, Annual Report and Accounts 2012/13. Available at www.bhf.org.uk/publications/view-publication.aspx?ps=1002318.
[3] Oxfam, Annual Report 2012-13. Available at www.oxfam.org/en/about/annual-reports.
[4] Teesside Hospice, Annual report. Available at www.teessidehospice.org/about-us/facts-funding.