# Strategyproof Computing **URL:** \ **Category:** Protocol Design\ **Created:** [October 16, 2023, 8:44pm UTC](https://forum.anoma.net/t/strategyproof-computing/310 "2023-10-16T20:44:39Z")\ **Posts on this page:** 1\ **Page:** 1
**Author:** ![apriori](https://dub1.discourse-cdn.com/flex013/user_avatar/forum.anoma.net/apriori/32/1655_2.png) [@apriori](https://forum.anoma.net/u/apriori)\ **Post date:** [October 16, 2023, 8:44pm UTC](https://forum.anoma.net/t/strategyproof-computing/310/1 "2023-10-16T20:44:39Z")
# Strategyproof Computing: Systems Infrastructures for Self-interested Parties This post highlights the key findings of this somewhat prophetic [paper](https://dash.harvard.edu/bitstream/handle/1/4101256/Ng_Strategyproof.pdf?sequence=2): _Strategyproof Computing: Systems Infrastructures for Self-interested Parties_ by Ng, Chaki, David C. Parkes, and Margo Seltzer. 2003. This paper informs much of the current thinking of the SUAVE design as a marektplace for mechanisms. As such, I’ve highlighted the key finds with some deliberate notes. All credit to the authors. h/t Andrew Miller and Quintus. ## (1) Introduction - SPC is a vision that explicitly recognizes and embraces the self-interest and incentives of individual parties in a distributed system - Self-interest manifests in many compelling future scenarios for next-generation computing - Scenarios in pervasive computing - depict a world where computing elements collaborate effortlessly behind the scenes in smart environments - SPC considers the problem of designing systems with useful long-term equilibrium behavior, when users or their computation/agents have presumably figured out how to play the game to their advantage **2 threads to pull on** 1. Market based approaches to resource allocation 2. Economic theory of mechanism design - Distributed systems should be populated with strategy proof mechanisms but without requiring a specific mechanism - Strategyproof computing is an infrastructure effort that seeks to enable multiple participants e.g., - to describe and deploy new mechanisms, centered around services and resources on an open playing field - Without this validation, mechanisms cannot commit to implement particular rules and the useful simplifying effort that mechanisms can have on strategies facing participants can quickly unravel > A critical roles of the infrastructure is to validate the incentive properties of the mechanisms ## (2) Strategyproof computing **Main ingredients** - Local strategyproof mechanisms - Open market for mechanisms - No single mechanism can possibly be appropriate for all requirements in a heterogenous system - SPC provides the dial-tone equivalent for the development and deployment of computing services that explicitly handle incentives ### (2.1) Guiding Principles 1. **Incentives first** - the self-interest of participants in distributed systems should be explicitly addressed by system designers, just like fault tolerance and security. 2. **Utility-based** - resource allocation decisions should be made in a framework that considers the utility of users for different outcomes as the basis for arbitration. Utility should be measured in terms of a common currency allowing for an explicit trade-off b/w multiple users and different components of the system. 3. **Simple** - simplify the decisions facing participants in distributed multi-agent systems such as the optimal statements to make about local capabilities e.g., 4. **Open systems** - allow for innovation and competition of design of new services. A successful open system requires a lightweight infrastructure in which we only introduce universal and minimal components, to enable deployment of services without preventing future deployment of unanticipated applications. 5. **Decentralized** - the control structure in distributed computing systems must be decentralized, both to respect the autonomy of the nodes that own the property rights to resources, but also for reasons of computational scale and timeliness of information. ### (2.2) Economic Foundations **2 theories from economics** 1. **Mechanism Design (MD)** - explicitly models each participant as a game-theoretic agent. MD wants to design optimal incentives for preferred system-wide outcomes 2. **Relaxed view** - propose an open market for mechanisms that must only satisfy certain local incentive properties, essentially within the scope of the local deployment - In accepting multiple mechanisms each of limited scope, you move away from the perfect optimality and perfect incentive properties of pure MD. - **Strategyproof mechanisms (SPM)** - self-interested party communicates their own utility through straightforward truth-revelations about requirements and capabilities regardless of what the strategies and behaviors of other parties might be > Strategyproofness addresses the design principles of incentives first, utility based and simple. - MD is beautiful in theory but brittle and unworkable in its purest form - The desired simplicity that comes from strategyproofness comes at an economic cost, and there are a number of well-known economic limitations of strategyproof mechanisms. - **Combinatorial auctions** - heterogenous auctions are simultaneously offered to sale and participants can submit bids for explicit bundles. > SPC considers the existence of multiple mechanisms, each of which is locally strategyproof within its scope - Local strategyproof mechanism M is one in which truth revelations is a dominant strategy for any participant that - SPC infrastructure must provide support for multiple users to design and support local strategyproof (LSP) mechanisms in a market for mechanisms. > This decision represents a trade-off between providing a large enough scope to sufficiently simplify the game-theoretic decisions facing a participant while maintaining a small enough scope to build computationally reasonable resource allocation mechanisms. The degree to which market forces lead to the emergence of mechanisms with right scope is an important research question. ### (2.3) Basic Concepts 1. LSP mechanism 2. Public Interface 3. Validation #### LSP Mechanism - Resource privders or intermediaries will create LSP mechanisms for admittance into distributed systems. - intermediaries profit by facilitating between buyers and providers #### Public Interface - Each LSP mechanism provides a public interface that facilitates how parties can find mechanisms and composes services across mechanisms - Part of the interface will make claims about incentive properties, and statistical properties on the utility of participants that hit that mechanisms The interface must specify 1. Service request language - language to describe home others can query the service. At a minimum the language should Include a 2. Restrictions - on the preferences of parties that are submitting requests, for which the incentive properties of the mechanism hold. This is important because it will depend on the particular type of goal a user wants to accomplish 3. Utility statistics - provide information on the average utility that parties have realized with the mechanism in the past #### Validation > The infrastructure will assume the key role of providing validation of the incentives and statistical properties of LSP mechanisms. - Suppose a new mechanism claims it is LSP and is admitted into the system. How can we precent it from lying? - This is the reason for validation schemes must be provided by the infrastructure for strategyproof systems to function - Truth revealing equilibrium of well defined mechanism can unravel without the ability to commit to a set of rules - validation can be provide without requiring the direct checking of the rules of mechanisms > Proposal: simply check the _input_ and the _output_ streams for correct behavior - This provides only a weak from of violation - there is no evidence to support the failure of incentive properties. - Infrastructure will assign a certificate to a newly-adopted LSP mechanism. This certificate can be presented to other parties so they can interact truthfully with confidence. > Proposal: check the claimed incentive properties by inspection of the requests made to a mechanisms and its responses 1. **Active monitoring** - with police agents that belong to the infrastructure 2. **Passive monitoring** - subset of requests and responses are monitors ## (3) Validation Experiments - Validation schemes are crucial for robustness > Proposal: validation is performed by the infrastructure without any knowledge of the auction algorithms. - Inputs for the validation will be the bids submitted to LSPs along with the resulting allocation and payments - Challenge - understand how to do this efficiently in terms of computational and space complexity > Experiment: determine what are the typical amount of auctions needed to detect a non-LSP mechanism in a simple setting - Consider a multi-unit allocation problem with M identical items and single minded agents that require particular bundle of items - Validation scheme does not require truthful agents only a stream of inputs and outputs into the mechanism - Consider a simple 1st price greedy auction which is a non-LSP mechanism. - The utility of agent i with value (k\_i, v\_i) given a bid (x\_i, p\_i) is simply stated as u\_i(k\_i, v\_i; x\_i, p\_i) = \left\{ \begin{array}{l} v\_i - p\_i \\ 0 \end{array} \right. \text{ if successful and } x\_i \> k\_i - Let B denote the set of bids submitted to an auction - In validation take bids (x\_i, p\_i) ∈ B and - If a mechanism is LSP, then it is necessary that u(x\_i, p\_i; x\_i, p\_i) ≥ u(x\_i, p\_i; x\_j, p\_j) \text{ (1) } - for all pairs of bids i, j ∈ B - To check for failure of LSP it is sufficient to find a single pair of bids of which condition (1) fails. - All three curves in figure 2 detect non-LSP auctions early - Validation becomes more effective with higher numbers of items ## (4) System Research Challenges > **AI related challenges** > > - computational MD > - design of description languages > - inference methods for verification > - methods of automated composition > - machine learning methods to identify > - scope of new mechanisms > - automatically tune existing mechanisms ### (4.1) LSP Mechanisms > Basic research goal - establish the core validity of local strategyproofness in the context of system settings - SPC mechanisms are often price-based or based around generalizations of the philosophy enshrined in Vickrey’s auction - How expressive are strategyproof mechanisms, given we allow them to be limited in scope? ### (4.2) Validation and Verification - Active and passive monitoring techniques are most effective if the responsible parties cooperate. - There are many types of mechanisms and many are one time participants - must have ways to stop short-lived mechanisms from hurting other parties ### (4.3) Scalability and Decentralization - Traditional MD is completely centralized; a single node collects info from all parties and computes an outcome. - we need to target strategies and mechanisms for decentrlaized MD > **Challenges** : mechanism implemented in the nodes that stand to gain from resource allocation decision, which means that it must be rational for these nodes to choose to implement the computation and the message passing required to deploy the mechanism - Develop fundamental building blocks including redundancy, partitioning, and dynamic selection to address challenges ### (4.4 ) Composition - LSP mechanisms that a party interacts with are not strategy proof necessarily - the party may behave strategically to obtain the highest possible utility from one of the mechanisms > How can we scale up with distinct LSP mechanisms? - Need to be able to discover and compose LSP mechanisms to form larger- scope LSP mechanism sets - very SUAVE like. - One method is to develop mechanisms that provide real options to users rather than just outcomes from which a user cannot decommit ### (4.5) Measurements > The negative effects of self-interest within a system must be clearly quantified - Past attempts point out ways in which self-interested parties can alter a system’s topology, but there does not seem to be much urgency in addressing incentive issues. - The main difficulty is what to measure? ### (4.6) Deployment Issues > **Challenge** : Until real Strategyproof mechanisms join a particular system, the parties in the system may not observe direct benefits of strategyproof computing and hence may leave. Likewise there will be less incentive for anyone to develop a LSP mechanism. - How can we begin to deploy strategyproof systems? - What if we take the hybrid approach and target up-and-coming systems such as specific grid systems? - SPC will affect parties in a system in both positive and negative ways - Overall, users have much to gain from strategyproof systems as they can interact truthfully and minimize interactions to get their resources while still extracting desirable utilities - Resource providers have costs to develop LSP mechanisms - an investment that will pay off in the long-run with user activity ## (5) Conclusion > SPC is an incentives-first agenda that proposes research into the design of an appropriate infrastructure to provide the ability to embrace incentives and allow the build-out of mechanisms to handle self-interest in distributed systems. - It is important to recognize Incentive issues in next generation distributed systems, such as p2p systems, and to design protocols to simplify strategic choices facing users - The next steps