Subsidy design for better social outcomes
Maria-Florina Balcan Matteo Pozzi Dravyansh Sharma




























Subsidy design for better social outcomes
    Maria-Florina Balcan

 

        Carnegie Mellon University

        Matteo Pozzi

		

        Carnegie Mellon University
        Dravyansh Sharma

         

        Toyota Technological Institute at Chicago
    Received April 17, 2024; accepted September 4, 2024
====================================================================================================================================================================================================================



§ ABSTRACT  

    Overcoming the impact of selfish behavior of rational players in multiagent systems is a fundamental problem in game theory. Without any intervention from a central agent, strategic users  take actions in order to maximize their personal utility, which can lead to extremely inefficient overall system performance, often indicated by a high Price of Anarchy. Recent work <cit.> investigated and formalized yet another undesirable behavior of rational agents, that of avoiding freely available information about the game for selfish reasons, leading to worse social outcomes. A central planner can significantly mitigate these issues by injecting a subsidy to reduce certain costs associated with the system and obtain net gains in the system performance. Crucially, the planner needs to determine how to allocate this subsidy effectively.

We formally show that designing subsidies that perfectly optimize the social good, in terms of minimizing the Price of Anarchy or preventing the information avoidance behavior, is computationally hard under standard complexity theoretic assumptions. On the positive side, we  show that we can learn provably good values of subsidy in repeated games coming from the same domain. This data-driven subsidy design approach avoids solving computationally hard problems for unseen games by learning over polynomially many games. We also show that optimal subsidy can be learned with no-regret given an online sequence of games, under mild assumptions on the cost matrix. Our study focuses on two distinct games: a Bayesian extension of the well-studied fair cost-sharing game, and a component maintenance game with engineering applications. 
    
    
    










§ INTRODUCTION


Multiagent systems often need a central agent to intervene and avoid harmful consequences of selfish decisions of individual agents. Subsidy is a form of positive intervention where the central agent reduces the cost of some actions in the system, with the goal of leading agents to better social outcomes. The amount of subsidy available to the central agent is typically scarce and therefore it is crucial to optimize its allocation. Prior research has addressed this by designing subsidy schemes that approximately optimize the Price of Anarchy <cit.>. In this work we extend the study of subsidy design for games in three different directions: we study the impact of subsidy beyond the Price of Anarchy objective and show its usefulness in preventing an undesirable information avoidance behavior, we establish formal hardness results for designing optimal subsidy schemes, and  show how an alternative novel data-driven approach can be used to design subsidy by exploiting historical data or related games.
















Concretely, critical infrastructure maintenance typically involves joint responsibility shared among multiple stakeholders, and  failure of coordination can lead to disastrous consequences. For example, different segments of a large road network are typically managed by different civil authorities. 
With an increasingly connected physical and digital world, it is a major challenge to coordinate large-scale systems consisting of several disjointly owned components. As a result, one crucially needs a central planner—who has the ability to allocate shared resources to avoid major catastrophic failures—to ensure  smooth operation of the overall system. In the above examples, this central agent could be a government department with appropriate jurisdiction. Ideally, the central agent would ensure a judicious use of the common resources which are to be allocated to appropriate stakeholders to incentivize them to do their part. Identifying the optimal resource allocations can be hard, but 
very often the central agent manages multiple similar systems or has access to relevant historical data. Could one take advantage of this data availability to improve the allocation?

Alternatively, in modern market systems, consumers have several options and would prefer to select options that meet their needs at the smallest cost. Often the consumer commits to an action based on expected long-term costs. For example, people buy health insurance plans and effectively  share the cost of healthcare with other subscribers to the plan.  If they could accurately estimate their need for medical services, people who determine they would not need any expensive medical procedures would opt out and drive up the insurance costs. An intervention by the governement to reduce the cost of health insurance plans could ensure that these people still opt in and the system is robust to the additional information regarding need for medical services. This intervention to guide the market is expensive, and also needs a careful allocation. As with infrastructure maintenance, optimal allocation is hard and one would like to use historical market data to guide it.

Coordination in  infrastructure projects poses multiple challenges when different pieces are owned by different agents. 
In systems requiring all of multiple components to simultaneously work, the failure of any single component can bring the entire system down. 
As a countermeasure, critical systems often have in place some amount of redundancy in terms of the components needed for the system to function. But this could introduce volunteer's dilemma, where the agents with knowledge of their redundancy can choose to not invest the due maintenance cost in hope that a different agent would put in the cost instead. Furthermore, selfish agents could choose to ignore or deliberately not collect important information about their own component, if public knowledge of that information comes at increased personal cost to them. With these various strategic aspects at play, a good amount of literature is devoted to identifying and circumventing such issues as individual agents <cit.>.

A common lesson from major failures and the primary recommendation for avoiding large-scale failure is ensuring an active role by the top management in coordination and resource allocation  <cit.>. For example, in public-private partnership infrastructure projects a central government agency typically decides the allotment of common resources among the various project stakeholders. Resources are typically scarce, and therefore a judicious allocation is crucial to ensure that all the critical components essential for the project function properly. The challenge can be particularly severe in  systems with a large number of components. 





  
Games studied.  
We consider a component maintenance game  based on <cit.>. We model the common responsibility as disjoint components maintained by individual agents or stakeholders, each having a binary state denoting whether the component is functioning or broken. For simplicity, we will assume known (prior) probabilities which govern whether the component will work, which are a common knowledge among all agents. The overall system is also assumed to have a binary state, given by some boolean function of the component states. For example, the overall system consisting of five components might function only if all components are functioning, or it might function if at least one of the first three components is functioning and at least one of the next two components is functioning. The components are repairable, and the agent maintaining it can choose to repair their component at some personal cost, or choose to do nothing. If an agent repairs
their component, then it is assumed to be guaranteed to function. In addition to the repair cost which is only charged to agents that undertake repair, all agents are assumed to experience a large cost if the overall system fails (see Section <ref> for formal details of the game). Furthermore, any individual component may be publically inspected (without any inspection cost) to determine whether it is actually working or broken. In this case, the agents may have a tendency to avoid having the state of their component inspected and revealed to everyone to avoid increased personal cost at equilibrium. In our model, it is the agents that could inspect a component but do not control the information about the inspected state, i.e. the state of an inspected component is revealed to all agents irrespective of who owns the component.

We also study a Bayesian extension of the classical cost-sharing game. We are given a collection of actions, each associated with some cost and  different actions being available to a fixed subset of agents. All agents that select a fixed action from the collection share the cost of that action. For example, if the actions are commute options like bus, train or car and agents are commuters, the cost of running the bus is shared by its users. In the Bayesian extension, there is a prior over of the action costs and agents choose actions based on the mean cost under the distribution. The true  cost of some action may be inspected and the information revealed to all the agents.



  
Summary of contributions. We formalize the problem of effective resource allocation by a central agent to improve the performance of a multi-agent system by subsidizing certain costs associated with the system.  
We consider  distinct objectives that the  central agent might have,

    
  (a) to use subsidy to reduce the price of anarchy for the system, i.e. to ensure that the harmful effect of the selfish behavior and lack of coordination and   of the agents on the social cost is minimized,


  (b) to ensure that the value of information (measured as change in agent's cost at equilibrium before and after inspection) about the state of an inspected component is non-negative for all agents.
 

We show that the system can perform poorly on each of the above objectives in the absence of any subsidy. The goal of the central agent therefore is to determine the smallest subsidy budget needed to ensure that one of the above objectives is met. We will show (Section <ref>) that  this calculation of optimal budget by the central agent can be done exactly for a simple small system, and the optimal subsidy allocation can be different for different objectives. We further show that in contrast
it is computationally hard to do so in more general systems under standard complexity theoretic assumptions. The computational hardness results (located in Section <ref>) for computing the optimal subsidy hold for both the above objectives, for both component maintenance and cost-sharing games.  

On the positive side, if the central agent has access to data about multiple games, we show (in Section <ref>) that a good value of the subsidy and allocation can be achieved with a polynomial number of game samples coming from an arbitrary game distribution. Moreover, if the games happen sequentially, the agent can perform nearly as well as the best subsidy scheme in hindsight, under very mild assumptions on the adversarial sequence of games. Since designing an optimal subsidy scheme is computationally hard, we would like to avoid having to solve the problem too many times in repeated games from the same domain. If we have access to similar games (e.g. infrastructure projects in similar counties), the subsidy design problem is still  hard, but we can potentially avoid a large number of repeated intensive computations. Moreover, the central agent may need to decide the value of subsidy on a new unseen game instance without observing the relevant parameters for this “test” game, for example the prior distribution on component failure. We obtain polynomial bounds on the sample complexity of the number of sample games needed to learn the optimal subsidy, which imply that we need to optimize the subsidy only for polynomially many games and can use the “learned” subsidy scheme on further game instances. 

We also obtain no-regret guarantees on learning the subsidy parameter in an online sequence of games, under a mild smoothness assumption on the repair costs. This could be useful for example in studying potential failure in a communication network with dynamically changing nodes/components.

While Lin et al. <cit.> introduces the component maintenance game and expose the challenge of information avoidance in small systems with a constant number of agents, we study general  systems with an arbitrary number of components and consider additional relevant objectives from the perspective of a central agent that can provide subsidy to some agents to reduce the repair cost of their component. While the use of subsidy has been studied in the context of cost-sharing games <cit.>, we study an interesting Bayesian extension where agents may experience negative Value of Information, establish new formal hardness results for optimal subsidy design and an a data-driven approach for overcoming the computational hardness in subsidy allocation.

Our main tool for showing the above positive results is to employ a recently introduced paradigm for beyond worst-case analysis called data-driven algorithm design <cit.>. Unlike traditional analysis, where one gives exact or approximate performance bounds applicable for worst-case instances, this paradigm focuses on “typical” problem instances that one actually encounters. This is similar to average-case analysis, but instead of a uniform distribution over problem instances, any arbitrary (fixed but unknown) distribution over the problem instances is allowed.





 §.§ Related Work


Component maintenance games. Management of engineering systems often involves maintaining multiple components arranged in some scheme that govern the overall functionality of the system; these components are controlled by different agents that make decisions under uncertainty <cit.>. Often this involves careful planning and resource allocation by a central agent whose goal is ensuring that the overall cost to the agents is small, and that the agents make good use of any available information about the component states <cit.>. The central agent could design incentives or subsidy to be given to specific agents for improving the overall system. The role of   subsidy and taxation has been studied in both cooperative and non-cooperative games <cit.>. Typically, a central agent designs a subsidy (or taxation) scheme, which effectively alters the game parameters by changing the costs/profits of the agents, to minimize some objective like the Price of Anarchy. We examine optimization of novel objectives in addition to previously analyzed ones in the context of component maintenance games, and demonstrate a first application of a learning-theoretic lens to overcome the worst-case computational hardness of subsidy design.

Cost-sharing games.
Cost-sharing game is a classical game in algorithmic game theory. Several variants of this game have been studied in the literature, including a set cover version <cit.> which we study here, and multicast game where network users connect to a source by paying for a route to the source and sharing cost <cit.>. Prior work has shown that subsidy is crucial for the former, while best response dynamics are sufficient to obtain a small Price of Anarchy for the latter. While <cit.> propose a primal-dual approach for approximately minimizing PoA under subsidy, we complement their results by establishing NP-hardness of exact optimization and further study the information avoidance phenomenon in a Bayesian extension of the game.

Value of Information.
Information avoidance has been studied extensively in behavioral sciences, economics, psychology and public health <cit.>. People can decide to seek or avoid certain information based on their goals, and strategic considerations can cause agents to ignore free and useful information. In the component maintenance games that we study, the information  corresponds to the true state of some inspected component. Agents can choose to not seek this information (about their own component, or that of another agent) even if it is freely available, if it could make them worse off (e.g. increase the need to repair their component) even at the cost of making the overall system more likely to fail. <cit.> demonstrates this phenomenon in several multi-agent network systems. <cit.> focuses on component inspection and  the value of information metric, and the results apply to games with a small constant number of agents.  In contrast, we study a broader variety of metrics of interest to the central agent, provide formal hardness results for n-agent games, and complement them with positive results under the data-driven algorithm design lens. 


Central agent improving equilibrium performance. Another related line of work considers steering strategic agents to “good” equilibria in  a variety of settings, typically with the help of a central agent. <cit.> consider using a public service advertising campaign, where the central agent prescribes actions to agents and a fraction of the agents (influenced by the campaign) follow actions that could lead to better equilibria. Another variant of the problem is to lead learning dynamics in a certain games where the game happens in phases for the same set of agents, and the impact of the campaign is only assumed in early rounds <cit.>. Similarly, <cit.> consider leading dynamics of agents with vanishing average regret. In contrast, our repeated game settings in Section <ref> consist of non-identical but similar games, for example corresponding to different infrastructure projects managed by the same central agent. <cit.> consider central agents that can modify the network structure, and study computational tractability for different utility functions and notions of “good” equilibrium.



Data-driven algorithm design is a tool for beyond worst-case analysis of algorithms, for learning algorithms that work well on typical problems coming from a common problem domain <cit.>. The technique has been successfully used in designing more effective algorithms for combinatorial problems, with applications to machine learning as well as mechanism design <cit.>.The technique has been successfully used in designing more effective algorithms for combinatorial problems <cit.>, with applications to machine learning <cit.> as well as mechanism design <cit.>. We will use the data-driven algorithm design approach  to learn subsidy schemes from multiple related games. We provide sample complexity guarantees when the games are drawn independently from a fixed distribution, and no-regret guarantees when learning subsidy in an online sequence of games.















§ FORMAL NOTATION, SETUP AND MOTIVATING EXAMPLES

Let G=⟨ N,(S_i),(cost_i)⟩ denote a game, where N is a set of n agents (or players), S_i is the finite action space of agent i∈ N, and cost_i is the cost function of agent i. The joint action space of the agents is S=S_1×…× S_n. Given joint action s=(s_1,…,s_n)∈ S let s_-i denote the actions of all agents except agent i, i.e. s_-i= (s_1,…,s_i-1,s_i+1,…,s_n). The cost function cost_i:S→ of agent i (which the agent seeks to minimize) is a function of the joint action s∈ S. The social cost function of the game is the sum of cost functions of all the agents in the game, cost=∑_i=1^ncost_i. The optimal social cost is = min_s∈ Scost(s). 
Given a joint action s, the best response of agent i is the set of actions _i(s_-i) that minimizes its cost given s_-i, i.e., _i(s_-i) = _a∈ S_icost_i(a,s_-i). A joint action s∈ S is a (pure) Nash equilibrium (or NE) if no agent can benefit from unilaterally deviating to another action, in other words every agent is simultaneously playing a best response action in s, i.e., s_i ∈_i(s_-i) for every i∈ N. A Nash equilibrium  is said to be global  or optimal if it also minimizes the social cost among all Nash equilibria. We say a Nash equilibrium is a local or suboptimal equilibrium if it is not global.



To the above standard model of a game, we add a central agent whose goal is to improve social outcomes by allocating subsidy which reduces costs for certain actions. Formally, we have the following definition of a subsidy scheme.


A subsidy scheme  is defined as a set of functions subs_i:S→_≥0 where subs_i(s) gives the subsidy offered by the central agent to agent i given joint action s. In a subsidized game using scheme , the cost of agent i is given by the difference function cost_i^:=cost_i-subs_i, and total subsidy provided for joint action s∈ S is subs(s)=∑_isubs_i(s). 


The Price of Anarchy measures the reduction in system efficiency (social cost) due to selfish behavior of the agents 
<cit.>. We define Price of Anarchy (PoA) in the presence of subsidy along the lines of <cit.> as the ratio of the sum of total social cost and subsidy in the worst case equilibrium, to the optimal social cost.


Let 𝕊={subs_i} denote the subsidy scheme. Let _NE(𝕊)⊆ S denote the subset of states corresponding to Nash equilibria when the cost for agent i is cost_i-subs_i. Suppose 0 and _NE(𝕊){}. Then the Price of Anarchy under subsidy  is given by 


    PoA(𝕊)=max_s∈_NE(𝕊)cost^(s)+subs(s)/.


We also define a related metric for studying the effectiveness of subsidy scheme , 


    PoA(𝕊)=max_s∈_NE(𝕊)cost^(s)+subs(s)/min_s∈_NEcost(s),


where _NE denotes the set of Nash equilibria in the component maintenance game (in the absence of any subsidy), provided min_s∈_NEcost(s) 0 and _NE(𝕊){}_NE.


By setting zero subsidies (i.e. subs_i(s)=0 for each i,s) we recover the usual Price of Anarchy, PoA <cit.>. Note that finding the subsidy scheme that optimizes PoA(𝕊) or PoA(𝕊) corresponds to the same optimization problem. In some games, it will be easier to show absolute bounds on PoA(𝕊). Note that PoA(𝕊)=PoA(𝕊)/PoS, where PoS is the usual Price of Stability in the unsubsidized game <cit.>.  

Besides PoA, we will also be interested in another quantity called Value of Information <cit.> which we define next. Suppose the costs of agents have some uncertainty, which we model by a prior  θ (common belief shared by all the agents) over some finite information set  about the game (e.g. the component states in a component maintenance game, or  action costs in a cost-sharing game, see below). The expected cost of agent j under joint action s is given by l_j(s,θ)=_I∼θ[cost_j(s)]. We will refer to this as the prior game. The Value of Information for agent j when information i∈ is revealed is the change in expected cost of the agent from the prior θ to the posterior θ^i,e_i, where e_i denotes the revealed value of the information i. For example, in the component maintenance  game defined below the information i corresponds to the some agent's component and e_i corresponds to the revealed state (working or broken). The game with expected costs given by l_j(s,θ^i,e_i) is called the posterior game. Formally, the value of information is defined as follows.

 Denote by θ the prior, and by θ^i,e_i the posterior when information i∈ is revealed to be e_i. Let s,s̃ be joint actions which are Nash Equilibria in the prior and posterior games respectively. The Value of Information for agent j when information i is revealed as  e_i is given by 
    VoI_j,i(s,s̃) := l_j(s,θ)-l_j(s,θ^i,e_i). We say that the Value of Information is non-negative for agent j if VoI_j,i(s,s̃)≥ 0 for  any information i∈ and any prior/posterior equilibria s,s̃. The worst-case Value of Information is defined as min_s,s̃VoI_j,i(s,s̃), where the minimum is over joint actions from prior and posterior Nash Equilibria. We will often call this simply the Value of Information, the worst-case aspect will be clear from context (lack of explicit arguments s,s̃).



We will be interested in a collection of related game instances, specifically the sample complexity of number of game instances needed from a distribution over the games to learn a good value of subsidy. Formal definitions follow the standard in data-driven algorithm design, and are deferred to Section <ref>. We will now proceed to formally describe the component maintenance and cost-sharing games and instantiate the above abstract definitions for both.

Component maintenance game <cit.>. 

Each agent is associated with a component c_i which has a binary state x_i∈{0,1} where x_i=0 corresponds to a broken component and x_i=1 corresponds to a functioning component. The action space of each agent is also binary, S_i={0,1}, where action s_i=1 indicates that the agent repaired the component (denoted RE), and s_i=0 denotes that the agent did nothing (denoted DN). The state x_i of c_i is updated after action s_i as x'_i=max{x_i,s_i}. This corresponds to “perfect repair”, i.e. if an agent picks the RE action, their component is guaranteed to work, and otherwise it stays as is. For a tuple of actions s, we will denote the updated state by '(s), or simply ' when s is evident from context. The state u of the system is a fixed binary function of the component states, u=ϕ(), where =(x_1,…,x_n) and ϕ:{0,1}^n→{0,1}[The component maintenance game intuitively corresponds to monotone boolean functions ϕ, but our results  easily extend to general boolean functions.]. For example, if ϕ(x_1,x_2,x_3)=(x_1 x_2) x_3, the system functions either when both components c_1 and c_2 are working, or when component c_3 is working. Here u=0 denotes a failure of the system. Let u'=ϕ(') denote the state of the system after the agents' actions. The cost for agent i is given by, cost_i=C_is_i+1-u' for repair cost C_i∈. Note that C_i could be negative, for example if there is a reward or incentive associated with the repair of component i which more than offsets what the agent pays for its repair. The actions depend on the belief about the state  of the components, which we model by a distribution θ over {0,1}^n. We will assume here that components and therefore their probability of functioning are independent, and that all agents share the same common belief about the state of the components, i.e. θ is fixed and known to all the agents. The system failure probability under this belief is P_ϕ(θ)=1-_∼θ[ϕ()], and the expected cost of action s_i to agent i, given other agents' actions are s_-i, is l_i(s_i,s_-i,θ)=_∼θ[cost_i]=C_is_i+1-_∼θ[ϕ(')]. Similarly, the expected social cost is defined as l(s,θ)=_∼θ[cost]=∑_il_i(s_i,s_-i,θ) for s=(s_1,…,s_n). 

We now imagine that each agent j has the ability, for free, to inspect their own component to determine its state.  The catch, however, is that this state is revealed to all agents. The revelation of the state would result in an updated common belief θ̃, corresponding to the conditional distribution given the known component state, and therefore an updated cost function for all agents. As a result, the set of Nash equilibria can now change and the agent may suffer higher personal cost in the new equilibria, inducing the agent to avoid inspecting their own component for selfish reasons. We will use the terminology prior (respectively posterior) game and equilibria to refer to the game before (respectively after) the inspection of any fixed component c_j. We next formalize the setup and instantiate the Value of Information metric for component maintenance game  to capture this behavior.

Component inspection game <cit.>. Suppose the inspection of component c_j reveals state y_j∈{0,1}. We will assume perfect inspection, i.e. y_j=x_j. Denote posterior belief after the inspection of component c_j by θ^j,y_j. If agent i switches action from s_i to s_i^j,y_j after the inspection (and other agents switch from s_-i to s_-i^j,y_j), the value of information about inspection of c_j for agent i and posterior y_j is given by VoI_i,j(s_i,s_-i,s_i^j,y_j,s^j,y_j_-i) := l_i(s_i,s_-i,θ)-l_i(s_i^j,y_j,s_-i^j,y_j,θ^j,y_j). The expected value of information is given by VoI_i,j(s_i,s_-i,s_i^j,*,s_-i^j,*) := l_i(s_i,s_-i,θ)-_y_jl_i(s_i^j,y_j,s_-i^j,y_j,θ^j,y_j), where s^j,* is the collection of states s^j,0,s^j,1. Here the posterior loss is computed as the expectation (based on prior) for the various possible outcomes for the inspection of a given component j. Typically we will assume that the joint actions s and s^j,y_j are Nash equilibria. We want the value of information to be non-negative for each agent i, when inspecting any component j, for any choice of equilibrium states. The expected value of information is easier to ensure to be non-negative, but implies a weaker (less robust) guarantee, so we will focus on the (inspection-specific) value of information. A motivation for ensuring that the value of information is non-negative is to not have any undesirable information avoidance behavior among the agents, where agents may choose to ignore freely available information (about the inspected component state) for selfish reasons (to reduce personal cost, for example by choosing to not repair their broken component), which could lead to sub-optimal social cost or an undesirable system state.






Fair-cost sharing game. Let ={a_j} denote the (finite) set of all possible actions for all the agents. There is a function f:→ 2^N such that 
agent i∈[N] may use any action a_j for which i∈ f(a_j). Note that there may be multiple options corresponding to the same subset of agents. Under uniform or fair cost-sharing, all agents that use an action a_j in some state s∈ S equally share its cost. That is, in the classical fair cost-sharing game there is a deterministic function c:→[0,C_max] such that if k agents from f(a_j) use an action a_j in some state s, then cost_i(s) for each of these agents is c(a_j)/k. Here, we will consider a Bayesian extension where the costs of some actions in  are associated with some uncertainty. The action costs are given by a distribution θ_c over [0,C_max]^|| and the agents all know the costs under the prior given by l_i(s,θ_c)=1/k_θ_c[c(a_j)], where k is the number of agents opting for action a_j in state s. This means we expect the agents to act according to the mean costs of actions under θ_c in the absence of additional information.

Analogous to the component inspection game above, suppose the inspection of action a_j reveals its true cost c_j∈[0,C_max]. Denote posterior belief after the revelation of the cost of action a_j by θ_c^j,c_j. If agent i switches action from s_i to s_i^j,c_j after the inspection (and other agents switch from s_-i to s_-i^j,c_j), the value of information about inspection of a_j for agent i and posterior c_j is given by VoI_i,j(s_i,s_-i,s_i^j,c_j,s^j,c_j_-i) := l_i(s_i,s_-i,θ_c)-l_i(s_i^j,c_j,s_-i^j,c_j,θ_c^j,c_j). The expected value of information is given by VoI_i,j(s_i,s_-i,s_i^j,*,s_-i^j,*) := l_i(s_i,s_-i,θ_c)-_c_jl_i(s_i^j,c_j,s_-i^j,c_j,θ_c^j,c_j), where s^j,* is the collection of posterior states s^j,c_j for different posterior costs c_j. As before, typically we will assume that the joint actions s and s^j,c_j are Nash equilibria. 

A model for information avoidance. One way to model information avoidance is to adapt the advertising model of <cit.>. The model proceeds in the following steps:

    
  * Some components C⊆ c_[n] are inspected. If a component c_i is inspected, information y_i∈{0,1} about it is collected. Here y_i=0 indicates the component was broken, and y_i=1 indicates it is working. y_i is a random variable with distribution p_i(θ). This updates the belief to θ'.
    
  * The information is revealed to all agents. Each agent may independently decide to ignore the information with probability α.
    
  * Agents that use the information play best response actions based on belief θ', agents that ignore the information play best response actions based on belief θ. The agents settle on a (local) Nash equilibrium.
    
  * This is repeated for T rounds, after this each agent learns their own value of information i.e. whether it wants to use or ignore the information, and does the same thing from then on (learn-then-decide model of <cit.>).





§ FURTHER QUESTIONS



    
  * Is the best response dynamics guaranteed to converge for this game? Is it a potential game <cit.>?
    
  * For two agents and series system, we know the value of information can be negative for local Nash equilibriums. Under what conditions (inspection, α, number of rounds T) can the agents reliably learn the value of information?
    
  * Are there inspection strategies C such that agents are steered towards global Nash equilibrium (for which the value of information is non-negative)?





 §.§ Motivating examples for how subsidy can help






Component maintenance game. We first present a motivating example where subsidy for component repair costs can help improve social cost by steering the system to a better equilibrium.

<cit.> give examples of local equilibria for two agent games where the Value of Information (VoI is defined as difference of prior loss defined above, and posterior loss when a component is inspected) is negative. This is undesirable as it can trigger the agents to avoid the perfect information on component state for selfish reasons. We present a motivating example where subsidy for component repair costs can help improve social cost as well as prevent information avoiding behavior on inspection.

[PoA in a 2-series system] Consider the two component series system depicted in Fig <ref>. Suppose that the components are independent and
the failure probabilities (according to the common prior belief) for components c_1 and c_2 are both 0.5, and the repair cost is
C_1 = C_2 = 0.3. Then the cost matrix for the component maintenance game is given in Table <ref>. For instance, for the joint action DN-DN (recall that action DN stands for “do nothing” and RE for “repair”) the system works with probability 0.5× 0.5=0.25 and therefore the cost to agents is P_ϕ(θ)=1-0.25=0.75. explain table Notice that both DN-DN and RE-RE are Nash equilibria for the  game, but RE-RE has a smaller social cost.  If the central authority provides a subsidy of 0.05+ϵ for the repair action, for any ϵ>0, then it would incentivize the agents to switch their actions from DN to RE, and the only Nash equilibrium is RE-RE. Note that the cost reduction in RE-RE (0.3 to 0.25-ϵ for each agent) equals the subsidy provided by the central agent in this case, and the social cost + subsidy for RE-RE is preserved, while ruling out the sub-optimal equilibrium DN-DN.
    Suppose there is central authority that is invested in minimizing the social cost and tackling information avoidance. One approach towards fixing the above problem of negative VoI is for the central authority to give an extra incentive (subsidy, or reward) to some agents to repair their components.
For example consider the two component series system from <cit.>. Suppose that the components are independent and
the failure probabilities for c_1 and c_2 are 0.6
and 0.9 respectively, and the repair cost is
C_1 = C_2 = 0.3. Then the cost matrix for the game (both prior, and posterior cost when component c_1 is inspected) is given in Figure <ref>. Notice that while DN-DN is not a Nash equilibrium in the prior game, but it becomes one in the event item i is inspected and is broken y_i=0. As a result the value of  information (VoI) can be negative for both agents. If the central authority gives agent 1 an incentive of 0.2+ϵ for any ϵ>0, then it would incentivize agent 1 to switch their action from DN to RE in the posterior game y_i=0 (which will cost 1.0-ϵ after the subsidy) and negative VoI can be avoided in this example.  More generally, for any costs C_1=C_2=ϵ<1, if c_2>1-C_1, then for y_i=0 case, we will have DN-DN a sub-optimal equilibrium which can be arbitrarily worse than RE-RE, by a factor of 1/ϵ.






  
  
  
  
  

































The above example illustrates how using a subsidy scheme, the central agent can potentially eliminate undesirable Nash equilibria by effectively modifying the repair costs in the component maintenance game. 
 In the component maintenance game, we will consider subsidy schemes that incentivize repair, i.e.  subs_i(0,s_-i)=0 for all agents i (no subsidy awarded for the action “do nothing”). We also say that a subsidy scheme is uniform if the scheme is identical for all agents and actions, i.e. subs_i(1,s_-i)=c_subs a fixed constant for all agents i for some constant c_subs≥ 0. We consider two types of subsidies which a central agent, whose goal is to altruistically maximize social welfare, can offer to reduce the repair cost of certain components.


Conditional vs. unconditional subsidies.  The central agent may offer an unconditional subsidy which effectively reduces the cost of repair for the components, or may be conditional on inspection in order to encourage agents to inspect their components, even when the information about the state of an agent's component results is something the agent might want to avoid (in the absence of subsidy). 
Formally, in a  component inspection game involving inspection of some component j, a general  subsidy consists of three functions for each agent i given by subs_i, subs_i^1, subs_i^0, corresponding to prior, posterior with component j intact, and posterior with component j damaged respectively. For simplicity, we will say that the central agent provides subsidy conditional on inspected state of component j, y_j=k for k∈{0,1}, to denote that subs_i^k is the only non-zero function in the conditional scheme, and conditional on inspection to denote that subs_i is a zero function and subs_i^1=subs_i^0.

We will now illustrate how subsidy can be used to avoid negative Value of Information, again in a 2-series component inspection game.


    Consider the two component series system from <cit.>. Suppose that the
components are independent and the failure probabilities for c_1 and c_2 are 0.6 and 0.9
respectively, and the repair cost is C_1 = C_2 = 0.3. Then the cost matrix for the game
(both prior, and posterior cost when component c_1 is inspected) is given in Table <ref>. Without any subsidy, for the highlighted Nash equilibria, when component c_1 is inspected and revealed to be broken (y_1=0), the value of information is negative (0.3-1.0=-0.7) for both agents.
If the central authority gives agent 1 an incentive of 0.2 + ϵ for any ϵ > 0, then it
would incentivize agent 1 to switch their action from DN to RE in the posterior game
y_1 = 0 (which will cost 1.0 - ϵ after the subsidy) and negative VoI can be avoided in
this example. The expected VoI is 0.3-(0.6*1.0+0.4*0.0)=-0.3 for agent 1 and 0.3-(0.6*1.0+0.4*0.3)=-0.42 for agent 2, and the same subsidy works to ensure the expected VoI is non-negative as well.






Cost-sharing game. In the cost-sharing game,  the central agent can subsidize the cost of some actions in . That is, the subsidy can be specified as an allocation of the subsidy budget to actions, c^:→_≥ 0. The corresponding subsidy scheme is given by {subs_i}_i, where subs_i(s_1,…,s_N)=c^(s_i)/k, with k=∑_j=1^N[s_j=s_i]. This corresponds to the subsidy being equally enjoyed by all the agents that select a given subsidized action. Subsidy can again be used to reduce Price of Anarchy in this game <cit.>. We will here show an example where subsidy can be used to avoid negative Value of Information.


Consider a two-agent cost-sharing game where the action set is ={A,B,C,D} with associated subsets f(A)={1,2}, f(B)={2}, f(C)={2}, and f(D)={1}. For example, in a commuting game, A could correspond to a shared public transport, and B,C,D could correspond to private modes of transport. We assume the cost function c is a random function such that with probability 1/2, c(A)=5, c(B)=2, c(C)=6, and c(D)=4, and with probability 1/2, c(A)=5, c(B)=6, c(C)=2, and c(D)=4. In the commute example, for agent 2, B could be a bike and C could be a car, and w_i could be unknown world state that impacts the cost of actions B and C for agent 2. We call these posterior worlds w_1 and w_2 respectively (see Tables <ref> and <ref>). Thus the prior cost for agent 2 (i.e. probability weighted cost of the worlds w_1 and w_2) is 4 for actions B and C. A Nash equilibrium in the prior game is (A,A) with a cost of (2.5,2.5) for both agents. In world w_1, the only NE is (D,B) and in world w_2 the only NE is (D,C), both with cost (4,2). Thus the knowledge of the state of the world leads to negative VoI for agent 1. Specifically, the knowledge of the cheaper option among B and C causes agent 2 to drop out of the cost-shared option A, increasing social cost and cost for agent 1.     In this example, using a subsidy of 3+ϵ for ϵ>0 for the option A guarantees that agent 2 will always prefer option A, and is sufficient to ensure that negative Value of Information 
is avoided.






We conclude this section with a simple remark that PoA(𝕊)≥ 1 for any subsidy scheme 𝕊 since the amount of subsidized cost is added back in the numerator for any state s in the definition of PoA(𝕊), and the dependence on the subsidy scheme 𝕊 is governed by the corresponding set of Nash Equilibria _NE(𝕊).
 



    For any subsidy scheme 𝕊, 1≤PoA(𝕊) and PoA(𝕊)≤PoA(𝕊).


    Let 𝕊={subs_i} denote the subsidy scheme. By definition,
    
    PoA(𝕊)   =max_s∈_NE(𝕊)cost^(s)+subs(s)/
       =max_s∈_NE(𝕊)∑_i(cost_i(s)-subs_i(s))+subs_i(s)/
       =max_s∈_NE(𝕊)cost(s)/≥min_s∈_NE(𝕊)cost(s)/≥ 1.

Also, PoA(𝕊)≥PoA(𝕊) since min_s∈_NEcost(s)≥min_s∈ Scost(s)=.


Addition of subsidy effectively changes the set of states that correspond to a Nash equilibrium. The goal of a central agent is to ensure suboptimal (local) Nash equilibria are not included in the set _NE when the subsidy is applied. The subsidy provided by the central agent could for example come from taxes collected from the agents, and therefore it makes sense to add the   total subsidy provided by the central agent to the social cost in the definition of PoA(𝕊). 

The central agent designing the subsidy scheme can have several different objectives for the scheme. In this work, we consider the following three objectives:


    
  1. PoA() is minimized. This means that the social cost in the worst-case Nash equilibrium after the subsidy is provided (with the total subsidy added) is not much worse than the social cost of the best joint action (or the best Nash equilibrium if we minimize PoA(𝕊)) when no subsidy is offered. As the result, the harmful effects of selfish behavior and lack of coordination among the agents is minimized.
    
  2. The value of information for each agent is non-negative when a single component is inspected. This corresponds to minimizing the tendency of agents to avoid seeking freely available information about the state of their component to avoid an increase in their personal cost, potentially at the expense of the social cost.
    
  3. The system is guaranteed to work in any Nash equilibrium in the component maintenance game. This is desirable if the central agent is keen on guaranteeing system functionality and willing to provide the needed subsidy for it. This can differ from minimizing the price of anarchy as the optimal social cost could correspond to doing nothing and letting the system stay broken, for example when the repair costs are too large.


summarize in a table


For a fixed game, the appropriate subsidy scheme could vary depending on the objective of the central agent. We will illustrate this for a two agent series game in Section <ref>, where we will  obtain the optimal subsidy schemes for different objectives below. Similarly, optimal schemes can be derived for the two-agent parallel game, the interested reader is directed to Appendix <ref>. However, for  general n-agent games, we  show in Section <ref> that computing the optimal total subsidy is NP hard, under each of the various objectives.

optional TODO: Write more generally for any game and information. Add more intuition/example for definition. We could also skip Defn 3 for SAGT submission.


Let 𝕊={subs_i} denote the subsidy scheme. Consider the  component inspection game for inspection of component j. Let _NE
(𝕊),_NE^0(𝕊),_NE^1(𝕊)⊆ S denote the subset of states corresponding to Nash equilibria when the cost for agent i is cost_i-subs_i for prior, posteriors y_j=0 and y_j=1 respectively. Let VoI_j(𝕊)=min_i,s∈_NE(𝕊),s'∈_NE^0(𝕊)∪_NE^1(𝕊)VoI_i,j(s_i,s'_i) denote the least value of information for any agent i for equilibria under 𝕊.  Then the Price of Information Avoidance  is given by 


    PoIA(j)=min_𝕊|VoI_j(𝕊)≥0max_s∈_NE
    (𝕊)cost(s)/min_𝕊max_s∈_NE(𝕊)cost(s)=min_𝕊|VoI_j(𝕊)≥0PoA(𝕊)/min_𝕊PoA(𝕊).



Recall that Price of Anarchy captures the 
effect of selfish behavior on social cost, relative to best centralized (co-ordinated) action under unselfish behavior, and is minimized (equals 1) when selfish behavior does not impact social cost. Similarly, Price of Information Avoidance corresponds to the 
effect of information avoidance, relative to the best centralized action when agents do not avoid information for selfish reasons. Also, it equals 1 if there is never any negative value of information under any subsidizing policy. Otherwise it is at least 1, and captures the sacrifice in social cost to avoid negative VoI. 




 §.§ Optimal subsidy design in two-agent series component maintenance game

This section aims to provide a working intuition for what an optimal subsidy scheme looks like for simple two-agent component maintenance games for the different objectives of the central agent, including Price of Anarchy and Value of Information. The key insights are that subsidy can be greatly beneficial, but exactly optimal subsidy allocation is a complicated function of the game's cost matrix and objective of interest. In the two-agent series game, the goal is typically to provide just enough subsidy to ensure that both agents prefer to repair (and the series system functions as a result), but the smallest amount of subsidy needed depends on repair costs and component failure probabilities.

Suppose we have two agents N={1,2} with components c_1,c_2 connected in series. Let p_1,p_2 denote the (prior) probability that the components c_1,c_2 will work (respectively). 
We will use the notation p:=1-p for conciseness. 
This corresponds to the prior game in Table <ref>, where DN denotes “do nothing” (s_i=0) and RE denotes “repair” (s_i=1). 
We will now consider the above three objectives. For each objective, we will note that subsidy helps and we will obtain the optimal subsidy in the two-agent series game.-1



  §.§.§ Minimizing the price of anarchy with subsidy.

To demonstrate the significance of subsidy for reducing the social cost in the two-agent series games, we will first show a lower bound on the Price of Anarchy in the absence of subsidy. The following proposition indicates that the Price of Anarchy can be very high when the probabilities of the components functioning (p_1,p_2) are small. Moreover, for n agents connected in series, the price of anarchy can increase exponentially with number of agents n.

 In the two-agent series prior game (defined above and cost matrix noted in the first row of Table <ref>), the Price of Anarchy in the absence of subsidy is at least PoA≥2/p_1+p_2, 
for some repair costs C_1,C_2. More generally, for n agents, PoA≥H̃/G̃^n for some repair costs C_1,…,C_n, where H̃ and G̃ are the harmonic and geometric means, respectively, of the prior probabilities p_1,…,p_n.


    We set C_1=p_1p_2 and C_2=p_2p_1. Observe that DN-DN is an equilibrium since[In our notation, p_1p_2:=1-p_1p_2,  while p_1·p_2:=(1-p_1)·(1-p_2).] p_1p_2=p_1+p_2p_1≤p_1+C_2, and similarly p_1p_2≤p_2+C_1. Also, RE-RE is an equilibrium since C_1=p_1p_2≤p_1 and C_2=p_2p_1≤p_2. Clearly,
    
    PoA≥cost(DN,DN)/cost(RE,RE)=2p_1p_2/C_1+C_2≥2/p_1+p_2,

    where the last inequality follows from the observations
    
    p_1p_2(p_1+p_2)=p_1+p_2-(p_1+p_2)p_1p_2≥ p_1+p_2-2p_1p_2 = C_1+C_2.

    For the n agent series game, we set the costs C_i=p_iΠ_j ip_j. DN^n (i.e., s=0^n) is a Nash equilibrium, since 
    C_i+Π_j ip_j=(1-p_i)Π_j ip_j+1-Π_j ip_j≥Π_jp_j.
 Moreover, RE^n is also an equilibrium as C_i≤p_i for all i∈[n]. Therefore,
    
    PoA   ≥cost(DN^n)/cost(RE^n)=nΠ_ip_i/∑_iC_i
       =n(1-Π_ip_i)/∑_iΠ_j ip_j - nΠ_ip_i
       ≥n(1-Π_ip_i)/∑_iΠ_j ip_j - (∑_iΠ_j ip_j)Π_ip_i
       =n/∑_iΠ_j ip_j
       =n/Π_ip_i·∑_i1/p_i,

    and the claim follows by noting H̃=n/∑_i1/p_i and G̃=(Π_ip_i)^1/n.
    




By Proposition <ref>, if probabilities of component working p_1=p_2=ϵ≪ 1, then Price of Anarchy can be as large as 1/ϵ (or as large as ϵ^-(n-1) for general n). We remark that our lower bounds also apply to the ratio PoA/PoS, i.e. when we compare the worst-case Nash equilibrium with the global Nash equilibrium instead of . We will now show that a constant price of anarchy can be achieved in this game using subsidy, more precisely, that PoA()=1 for some subsidy scheme . In fact, we characterize the total subsidy needed to guarantee this for any game parameters. The proof involves carefully considering cases for the parameters resulting in different sets of Nash equilibria and computing necessary and sufficient amounts of subsidy in each case (see Appendix <ref>).



    Consider the two-agent series component maintenance game with C_1,C_2>0 and 0<p_1,p_2<1. Let s^*={(C_1,C_2)∈ [p_1p_2,p_1]× [p_2p_1,p_2]}·min{C_1-p_1p_2, C_2-p_2p_1}, where {·} denotes the 0-1 valued indicator function. Then there exists a subsidy scheme   with total subsidy s for any s>s^* such that PoA(𝕊)=1. Moreover, a total subsidy of at least s^* is necessary for any subsidy scheme  that guarantees PoA(𝕊)=1. 
































































 We will characterize the set of values of C_1,C_2 for which there are multiple Nash equilibria and design subsidy schemes that achieve PoA(𝕊)=1. We consider the following cases.


    
  Case 0: C_1<p_1p_2,C_2>p_2. In this case the only NE is RE-DN (Table <ref>). Thus, PoA =1 even in the absense of subsidy and s^*=0 in this case.
    
  Case 1: C_1=p_1p_2,C_2>p_2. Both RE-DN and DN-DN are Nash equilibria, and 
    cost(RE,DN)=C_1+2p_2=p_1p_2+2p_2=2-p_1p_2-p_2<2p_1p_2=cost(DN,DN).
 An arbitrarily small subsidy to agent 1 is sufficient to guarantee PoA(𝕊)=1 (therefore s^*=0 works) as DN-DN would no longer be a NE.
    
  Case 2: C_1>p_1p_2,C_2>p_2. In this case the only NE is DN-DN. Thus, PoA =1 even in the absense of subsidy.
    
  Case 3: C_1<p_1p_2,C_2=p_2. Both RE-DN and RE-RE are Nash equilibria, and 
    cost(RE,DN)=C_1+2p_2>C_1+p_2=C_1+C_2=cost(RE,RE).
 An arbitrarily small subsidy to agent 2 is sufficient to guarantee PoA(𝕊)=1 (therefore s^*=0 works)  as RE-DN would no longer be a NE.
    
  Case 4: C_1<p_1p_2,C_2<p_2. In this case the only NE is RE-RE. Thus, PoA =1 even in the absense of subsidy.
    
  Case 5: (C_1,C_2)∈ [p_1p_2,p_1]× [p_2p_1,p_2]. Both RE-RE and DN-DN are Nash equilibria, and OPT corresponds to RE-RE. A subsidy greater than C_1-p_1p_2 to agent 1, or a subsidy greater than C_2-p_2p_1 to agent 2 guarantees that the only NE is RE-RE. Further, in either case PoA(𝕊)=1 as the subsidy equals the reduction in the repair cost of the respective agent.

    Further suppose a subsidy of s^*=s^*_1+s^*_2 is sufficient to ensure PoA(𝕊)=1 in this case. Now if subsidy to agent 1 s_1^*≤ C_1-p_1p_2 and subsidy to agent 2 s_2^*≤ C_2-p_2p_1. Then both DN-DN and RE-RE are NE and PoA(𝕊)>1 since the worst-case equilibrium (i.e. DN-DN) cost does not depend on the subsidy. Therefore either s_1^*> C_1-p_1p_2 or s_2^*> C_2-p_2p_1, establishing that a subsidy of at least s^* is necessary in this case to ensure PoA(𝕊)=1.

    

    
  Case 6: Otherwise. By symmetry, the case is similar to one of  C0 through C4 with agents 1 and 2 switched. s^*=0 and price of anarchy of 1 is achieved by no or arbitrarily small subsidy as above.

Note that s^* is non-zero only in case C5, in which case we have established both sufficiency and necessity of a total subsidy of s^* to ensure PoA(𝕊)=1.
    





  §.§.§ Guaranteeing that the system functions in any NE
 As seen in Example <ref>, the agents may be in an equilibrium (e.g. DN-DN) such that the system is not guaranteed to function. This problem can also be remedied using subsidy.
We will quantify the optimal subsidy needed to guarantee that the system functions, i.e. ϕ(')=1, where ' denotes the component states after the agents' actions. 


    Consider the two-agent series component maintenance game with C_1,C_2>0 and 0<p_1,p_2<1. Define R⊂^+×^+ as the set of cost pairs that satisfy C_1≤p_1 C_2≤p_2 (C_1≤p_1p_2 C_2≤p_2p_1), depicted in Figure <ref>. Let s^*=min_(x,y)∈ R||(C_1,C_2)-(x,y)||_1, where ||·||_1 denotes the L_1-norm. Then there exists a subsidy scheme   with total subsidy s for any s>s^* such that the system functions in any NE. Moreover, a total subsidy of at least s^* is necessary for any subsidy scheme   that guarantees that the system functions in any NE.

    


    (Sufficiency of s^*). We do this by cases on the cost vector (C_1,C_2), as follows.

    
        
  Case 0:  (C_1,C_2) lies in the interior of R. In this case it is easy to see that PoA=1 and s^*=0. In particular, the conditions C_1< p_1, C_2< p_2 rule out DN-RE, RE-DN as candidate equilibria respectively, and since C_1< p_1p_2 or C_2< p_2p_1,  DN-DN  cannot be a NE either (agent 1 or agent 2 will prefer to repair).
        
  Case 1: C_1≤p_1p_2, C_2≥p_2. In this case, a  subsidy more than s^*=C_2-p_2 to agent 2 is sufficient to bring the cost vector to the interior of R.
        
  Case 2:C_2≤p_2p_1, C_1≥p_1. Symmetric to C1.
        
  Case 3: p_1p_2<C_1≤p_1, p_2p_1< C_2≤p_2. A subsidy more than min_i{C_i-p_ip_3-i} to agent _i{C_i-p_ip_3-i} is sufficient to bring the cost vector to the interior of R.
        
  Case 4: Otherwise. It is straighforward to verify by direct calculation that a subsidy of s^*_1=max{C_1-p_1,0}+p_1·p_2 to agent 1 and a subsidy of s^*_2=max{C_2-p_2,0}+p_1·p_2 to agent 2 is sufficient.
    
    The necessity argument essentially follows by updating the cost matrix with conditional subsidies (s_1,s_2) and noting that the system is guaranteed to function in any NE if the costs (C_1,C_2) are in the interior of R.


The proof is deferred to Appendix <ref>. In constrast to Theorem <ref>, here the central agent needs to provide subsidy in the states where the price of anarchy may be 1 without subsidy but the system is not guaranteed to function as agents may choose to do nothing.



  §.§.§ Ensuring value of information is non-negative for each agent.
 <cit.> exhibit several examples, including 2-agent series games, where the value of information for certain agents can be negative, when actions in the prior and posterior games are selected according to some Nash equilibria. We will demostrate the use of subsidy in tackling this undesirable information avoidance behavior. 



In addition to the prior game, we will now consider posterior games where component c_1 is inspected, and its state y_1 is revealed on inspection (y_1=1 corresponds to c_1 is functioning, and y_1=0 corresponds to c_1 is broken). Table <ref> summarizes prior and posterior costs for the two agents for each action pair (recall that DN denotes “do nothing” or s_i=0, and RE denotes “repair” or s_i=1). <cit.> show that the expected value of information (VoI) is non-negative for all agents if 
a global NE is selected.




















In the two-agent series game described above, if component c_j,j∈{1,2} is inspected, and the prior and posterior actions s,s̃ are selected from global  equilibria, then the expected value of information VoI_i,j(s,s̃) is non-negative for each agent i∈{1,2}. 


Therefore, if we avoid suboptimal local equilibria in this setting then expected VoI is guaranteed to be non-negative. Combined with Theorem <ref> above, this implies that negative Value of Information may be avoided via subsidizing repair costs in the two-agent series game. In more detail, we can employ a conditional subsidy scheme, with prior subsidy subs_i according to the scheme  in Theorem <ref>, and posterior subsidy subs_i^y when agent 1 is inspected employs the subsidy scheme from Theorem <ref> by setting the parameter p_1=y. Theorem <ref> in Appendix <ref> characterizes the optimal unconditional subsidy for ensuring the Value of Information is non-negative for each agent.



In addition to expected VoI, we can also ensure posterior conditioned VoI_i,j when component c_j is inspected is non-negative for each agent i and each posterior y_j via subsidy. Compared to expected VoI, this is a more worst-case perspective as it includes the case when the component is broken which is typically when the agents are more likely to avoid the information about the component state. The following result gives the optimal value of subsidy to ensure this.


    Consider the two-agent series component inspection game with C_1,C_2>0 and 0<p_1,p_2<1. Then 
        
  (a) VoI_i,j(s_i,s^j,1)≥0 for any agents i,j, any  prior NE s_i and any posterior NE s^j,1, when the inspected component j is working, except when C_3-j=p_Rp_3-j and an arbitrarily small subsidy is sufficient to ensure VoI is non-negative in this case. 
        
  (b)
    
    
    



WLOG j=1. 
    
  (a)
    If y_1=1, the only candidate posterior equilibria are DN-DN if C_2≥ p_Rp_2 and DN-RE if C_2≤ p_Rp_2.

    If C_2> p_Rp_2, then the prior NE is either DN-DN or RE-DN. In either case both agents have a non-negative Value of Information (Table <ref>).
If C_2< p_Rp_2, then the prior NE is either DN-DN, RE-RE or DN-RE. In each case both agents can be readily verified to have a non-negative Value of Information. If C_2=p_Rp_2 and C_1≤ p_Rp_2, then VoI can be negative for agent 1 if the prior equilibrium is RE-RE and the posterior equilibrium is DN-DN. But in this case a (unconditional, or conditional on inspection) subsidy of s^*_2>0 to agent 2 ensures that DN-DN is not a posterior equilibrium and both agents have non-negative VoI. 
    
  (b) For y_1=0, we consider the following cases.
    

    
  Case 0: C_1≤ p_Rp_1p_2,C_2>p_Rp_2. If C_1<p_Rp_1p_2, the only prior NE is RE-DN and the only posterior NE is also RE-DN. Thus, VoI =0 for each agent even in the absense of subsidy and s^*=0 in this case. If C_1=p_Rp_1p_2, DN-DN is also a prior NE but VoI is still non-negative for each agent, since the poterior costs
    
    cost_1(RE,DN)=C_1+p_Rp_2≤ p_Rp_1p_2+p_Rp_2=p_Rp_1p_2,

    and 
    
    cost_2(RE,DN)=p_Rp_2<p_Rp_1p_2.

    
  Case 1: p_Rp_1p_2< C_1<p_Rp_2,C_2>p_Rp_2. DN-DN is the only prior NE and the only posterior equilibrium is RE-DN. and 
    cost_1(RE,DN)=C_1+p_Rp_2> p_Rp_1p_2.
 A subsidy of C_1-p_Rp_1p_2 to agent 1 is sufficient to ensure VoI is non-negative for agent 1 as noted in  case C0. Alternatively, a subsidy of C_2-p_Rp_1p_2 to agent 2  ensures that RE-RE is the only prior and posterior NE, and VoI is non-negative for each agent. The smaller of the two subsidies works and is necessary in this case.

    If we require the subsidy to be conditional on inspection, DN-DN remains the only prior NE as prior costs are not updated by the subsidy. A subsidy of C_1-p_Rp_1p_2 to agent 1 works as above. In the alternative case, if we provide a smaller subsidy of C_2-p_Rp_2 to agent 2, the posterior NE is switched to RE-RE but the prior remains  DN-DN and a 
    subsidy of C_1-p_Rp_1p_2 to agent 1 is still required to ensure non-negative VoI for agent 1.
    
    
    
    
    
  Case 2: C_1>p_1p_2,C_2>p_2. In this case the only NE is DN-DN. Thus, PoA =1 even in the absense of subsidy.
    
  Case 3: C_1<p_1p_2,C_2=p_2. Both RE-DN and RE-RE are Nash equilibria, and 
    cost(RE,DN)=C_1+2p_2>C_1+p_2=C_1+C_2=cost(RE,RE).
 An arbitrarily small subsidy to agent 2 is sufficient to guarantee PoA(𝕊)=1 (therefore s^*=0 works)  as RE-DN would no longer be a NE.
    
  Case 4: C_1<p_1p_2,C_2<p_2. In this case the only NE is RE-RE. Thus, PoA =1 even in the absense of subsidy.
    
  Case 5: (C_1,C_2)∈ [p_1p_2,p_1]× [p_2p_1,p_2]. Both RE-RE and DN-DN are Nash equilibria, and OPT corresponds to RE-RE. A subsidy greater than C_1-p_1p_2 to agent 1, or a subsidy greater than C_2-p_2p_1 to agent 2 guarantees that the only NE is RE-RE. Further, in either case PoA(𝕊)=1 as the subsidy equals the reduction in the repair cost of the respective agent.

    Further suppose a subsidy of s^*=s^*_1+s^*_2 is sufficient to ensure PoA(𝕊)=1 in this case. Now if subsidy to agent 1 s_1^*≤ C_1-p_1p_2 and subsidy to agent 2 s_2^*≤ C_2-p_2p_1. Then both DN-DN and RE-RE are NE and PoA(𝕊)>1 since the worst-case equilibrium (i.e. DN-DN) cost does not depend on the subsidy. Therefore either s_1^*> C_1-p_1p_2 or s_2^*> C_2-p_2p_1, establishing that a subsidy of at least s^* is necessary in this case to ensure PoA(𝕊)=1.

    

    
  Case 6: Otherwise. By symmetry, the case is similar to one of  C0 through C4 with agents 1 and 2 switched. s^*=0 and price of anarchy of 1 is achieved by no or arbitrarily small subsidy as above.












§ COMPUTATIONAL HARDNESS OF SUBSIDY DESIGN



We will now consider the problem of computing the best subsidy scheme  in  general component maintenance  and cost-sharing games. 
We will prove  computational hardness results in this section and assume familiarity with fundamental  concepts in complexity theory <cit.>. We will do this by reducing the Vertex-Cover problem (one of Karp's original NP-complete problems <cit.>) to the decision-problem version of computing the best subsidy for the component maintenance game and from the Min-Set-Cover problem for the cost-sharing game. 
Recall that  Vertex-Cover is the following decision problem, specified by a graph =(V,E) and an integer k.

Vertex-Cover: Does a given (undirected, unweighted) graph =(V,E) admit a vertex cover[A set of vertices such that all edges of the the graph have at least one endpoint in the set.] of size k?



We also consider the optimization version of the minimum subset cover problem (,,k) stated below, which will be useful in our hardness results for the cost-sharing game.


Min-Set-Cover: Given a finite set  of size n and a collection ⊆2^ of subsets of , does there exist a subset S of  of size k<n that covers , i.e. ∪_S_i∈ SS_i=?

In the next three subsections we will show computational hardness results for designing the optimal subsidy scheme for several different objectives of interest to the central agent,  including the Price of Anarchy under subsidy, guaranteeing the Value of Information is non-negative for all agents, and (in the component maintenance game) ensuring the system functions in any Nash equilibrium.



 §.§ Price of Anarchy under Subsidy
 

Component maintanence game. Finding the best  subsidy in a given component maintanence game (CMG) to minimize the price of anarchy is an optimization problem. Here we will study the hardness of a corresponding decision problem stated below.

CMG-PoAS: Given a CMG G and a subsidy budget  n^*, 
does there exist  subsidy scheme  with non-zero subsidy provided to  n^* agents such that PoA()=1?

Note that here we define the best subsidy scheme to be the one that provides subsidy to fewest agents (as opposed to providing the smallest total subsidy paid out by the central agent, which we also study subsequently). This meaningfully models situations when subsidy consists of allocation of indivisible resources, for example the central agent providing commitment to intervene and assist but with a bandwidth constraint on the number of agents that could receive the assistance. The question whether the same hardness result can be established when the subsidy budget is continuous is left open in this case (we do consider real-valued subsidy budgets for other objectives, see Sections <ref>, <ref>). As mentioned above, we will do a Karp reduction from the Vertex-Cover problem. 

The key idea is to construct a component maintenance game G given any graph , with agents corresponding to graph nodes, and the system state function ϕ corresponding to the graph edges. We show that the Nash equilibria of G roughly correspond to minimal vertex covers of . To ensure PoA()=1, we provide subsidy to the agents in a smallest vertex cover of .



    CMG-PoAS is NP-Hard.


We will reduce the Vertex-Cover problem to CMG-PoAS.  Given an instance ,k of the Vertex-Cover problem, we create a corresponding CMG-PoAS problem as follows. Introduce an agent i for every vertex  i∈ V and consider the (2-CNF) formula ϕ()=⋀_(i,j)∈ E(x_i x_j), where the clauses consist of component states x_i,x_j for all pairs i,j of agents corresponding to edges in E. Set the probability distribution θ to be the constant distribution with the entire probability mass on 0^n (i.e. all the components are guaranteed to fail without repair). Set repair cost C_i=1 for all components i. Then the cost function for agent i for joint action s=(s_i,s_-i) is given by-1

    l_i(s_i,s_-i,θ)=_∼θ[cost_i]   =C_is_i+P_ϕ(θ)
       =1· s_i+1-ϕ(')
       =s_i+1-ϕ(s),
 where x_i'=max{0,s_i}=s_i denotes the  component state after agent i takes action s_i.

We first proceed to characterize the set of Nash equilibria of this game. Note that  s=0^n is a NE for this game, since any repair action by any agent increases the agent's cost by 1 if the repair does not change the state ϕ of the system, and by 0 otherwise. This is because ϕ is monotonic, ϕ(s) can only change from 0 to 1 on repair. For the same reason, no agent has any incentive to switch from DN to RE. We will now show that the remaining NEs for the game correspond to minimal vertex covers of . 

Suppose K⊆[n] is a set of agents for which the corresponding nodes in  constitute a minimal vertex cover. Let s_K'=(s_1,…,s_n) where s_i=[i∈ K'], and [·] is the 0-1 valued indicator function, denote the joint action where agents in set K'⊆[n] choose repair. Clearly,  ϕ(s_K)=1. If i∈ K, agent i does not reduce cost by switching from RE to DN since K is a minimal cover therefore not repairing component i causes the system to fail. As noted above, switching from DN to RE never improves an agent's cost in this game. 
Further, if K is the set of agents corresponding to a non-minimal vertex cover, then there must be some agent that can reduce its cost by switching from RE to DN (and system continues to function). 
Finally, if  K' ∅ is the set of agents with one or more agents short of a vertex cover, then any agent in K'  can reduce its cost by switching from RE to DN. This establishes that besides 0^n, only possible NE must correspond to a minimal vertex cover. In particular, this implies that =k^*, where k^* is the size of the smallest vertex cover K^* of , and the corresponding NE is s_K^*. 

To complete the reduction, we consider the game defined above with subsidy budget n^*=k. We will show a bijection between the YES and NO instances of the two decision problems to complete the proof.

If there exists a vertex cover of size k, then the smallest vertex cover K^* has size k^*≤ k. We design a subsidy scheme with  subsidy allocated to k^*≤ n^* agents, allocating subsidy of 1+1/2n for repair (the total subsidy is no more than k^*+1/2) to all agents in the minimum cover K^*, a  and subsidy of 0 otherwise. 
As argued above, the only candidate NE without subsidy are 0^n and s_K corresponding to some minimal vertex cover K. The social cost for 0^n is n (except the trivial case k^*=0) and that for s_K^* is k^* which is smaller. If we provide subsidy in our scheme  to the agents in K^* then 0^n is no longer an NE. In particular, every subsidized agent in K^* would now always choose repair at subsidized cost -1/2n over doing nothing (even when the system stays broken after the repair). Thus, the social cost plus subsidy is k^*(-1/2n)+k^*(1+1/2n)=k^*, and the price of anarchy for the subsidy scheme is 1 (any agent outside of K^* will prefer to do nothing to reduce their cost).

On the other hand, suppose that  has no vertex cover of size k. Any minimal vertex cover of  therefore has size at least k+1. Suppose  is a subsidy scheme with  subsidy allocated to most k agents. We will show that PoA()>1. Indeed, let K be an arbitrary minimal  vertex cover of . By pigeonhole principle, at least one agent in K does not receive subsidy. Let K' denote the (possibly empty) set of agents that receive subsidy greater than 1. As argued above, these agents will always prefer the repair action. Thus, s_K' is a Nash equilibrium (agents without subsidy never have incentive to switch from DN to RE in this game) in the subsidized game. Note that ϕ(s_K')=0 since at least one vertex is missed in any minimal vertex cover K, and therefore we must have an uncovered edge. 
Now ≤cost(s_K)=|K|<n. Therefore, PoA()> 1 as total cost plus subsidy is at least n for s_K'.



    


We make a couple of remarks about the above result. Our proof implies a similar hardness result if the decision problem is stated for PoA() instead of PoA(). 
We further note that  our reduction from Vertex-Cover does not involve any negative literals in the boolean system function ϕ, i.e. applies to monotone boolean functions where  if a component is repaired from broken to a working state, then it cannot cause the overall system to go from working to broken. In fact, for monotone ϕ we can show an even stronger hardness result using parameterized complexity theory. Namely CMG-PoAS is W[2]-hard, by reduction from the Dominating-Set problem, i.e. deciding whether given a graph  and integer k, does there exist a subset X of vertices of size k such that each vertex is either in the subset X or has an edge connecting it to a vertex in X. The Dominating-Set problem is  known to be  W[2]-complete (<cit.>, Lemma 23.3.1). This implies that it is unlikely that the problem is even fixed-parameter tractable (FPT), i.e. it is plausible that there is no computationally efficient algorithm for CMG-PoAS even for a fixed small subsidy budget. Further details and formal proofs are located in Appendix <ref>.

Cost-sharing game. We will now give a similar result for cost-sharing games. While it is known that computing OPT is NP-Hard in cost-sharing games <cit.> and approximation algorithms are known for subsidy design <cit.>, we further show that designing a  subsidy scheme to guarantee that PoA=1  is also NP-hard.

CSG-PoAS: Given a cost-sharing game G and a subsidy budget  n^*, 
does there exist  subsidy scheme  with non-zero subsidy provided to  n^* actions such that PoA()=1?

The key idea is to construct a cost-sharing game G given an instance of the minimum set cover problem, with agents corresponding to set elements, and the actions  corresponding to subsets available for covering plus some additional actions uniquely available to each agent. When there exists a set cover of size k, assigning subsidies to actions in the cover guarantees that the only possible NEs correspond to assigning actions from the set cover and the subsidized cost plus the subsidy equals cost of OPT. Conversely, we use the additional actions to show that the Price of Anarchy is greater than 1 when a subsidy smaller than the size of the minimum set cover is available.



    CSG-PoAS is NP-Hard.


Consider the cost-sharing game G with n agents that correspond to elements of  via a bijection ζ:→[n], set of actions =⊎⊎ with ={{1},…,{n}} and ={{1,2,…,n}} being two distinct collections of actions available uniquely to each agent and all agents simultaneously respectively, function f:S↦{ζ(s)| s∈ S} which assigns action S to agents corresponding its elements, and cost function c given by


    c(S)=
            1     if S∈⊎,
    
            n-ϵ    if S∈.

for some ϵ∈(0,1). 
We set n^*=k.

Given a YES instance of Min-Set-Cover, we show that the above contruction yields a YES instance of CSG-PoAS. Indeed, let k^* denote the size of the smallest set cover of (,).  In the YES instance this means k^*≤ k<n, and we provide subsidy of value 1 to all actions corresponding the sets in the smallest set cover.  Now any assignment of the actions to agents consistent with the set cover (i.e. each agent is assigned an action corresponding to one of the sets in the cover that include the agent) is a Nash Equilibrium with social cost 0. This is because each agent has (subsidized) cost 0 and therefore no incentive to switch actions. Moreover, any other state is not an NE as at least one agent will have non-zero cost and would switch to an action in the cover. Therefore, social cost plus subsidy is k^* for the only NE in this case. Next we argue that the social cost OPT is k^* in this case, which would imply PoA()=1 for the above subsidy scheme. If possible, let there be a state s=(a_1,…,a_n) with social cost less than k^*. Let  s_={i| a_i∈} and s_={i| a_i∈}. Now the smallest set cover of ∖ s_∖ s_ has size at least k^*-|s_|-|s_| since each set in the optimal cover must cover at least one element. We consider cases based on |s_|. If s_=0, cost(s)≥ (k^*-|s_|) +|s_|= k^*, a contradiction. If s_=n, then cost(s)=n-ϵ>k^*, again contradicting the assumption that cost of s is less than k^*. Else 1≤|s_|≤ n-1. But then, cost(s)≥ (k^*-|s_|-|s_|) +|s_|+n-ϵ≥ k^*+1-ϵ>k^*. Thus, cost(OPT)=k^* and we have PoA()=1 in this case.


Conversely, consider a NO instance of Min-Set-Cover. The smallest set cover of (,) has size k^*>k. Consider any subsidy scheme  assigning subsidy of value 1 to at most k actions. Clearly, all the agents that have at least one of their actions subsidized will select the subsidized action in any NE. Since the smallest set cover has size greater than k, there exists at least one agent  with no subsidized action. Let A⊂[n] denote the set of these agents. We will show the existence of two Nash equilibria with different social costs, implying that PoA()>1 in this case. Consider states s_ and s_ for which agents in A are assigned the corresponding actions from  and  respectively, and agents in [n]∖ A are assigned one of the subsidized actions in either case. The social cost plus subsidy cost(s_)+k=|A|+k for s_ and  cost(s_)+k=n-ϵ+k for s_. Thus, PoA()>1. 





 §.§ Value of Information
 We also show NP-hardness of the problem of determining the minimal subsidy needed to avoid negative Value of Information in the component inspection game. Formally, the decision problem is stated below.



CIG-VoI: Given a component inspection game (CIG) and subsidy budget s^*, does some subsidy scheme  with total subsidy at most s^* guarantee that no agent has negative value of information when a single component j is inspected (i.e. for fixed inspected component j, VoI_i,j(s,s̃^j,y_j)≥0 for any s∈_NE(𝕊), s̃^j,y_j∈_NE^y_j(𝕊), for each agent i∈ [n], and each posterior component state y_j∈{0,1})?

Our proof (Appendix <ref>) again involves a reduction from the Vertex-Cover problem, but we use a different  subsidy budget and examine the non-negativity of VoI when potentially different equilibria are selected in the prior and posterior games.


    CIG-VoI is NP-Hard.



We also establish a similar hardness result for designing the optimal subsidy allocation in cost-sharing games to ensure that the value of information is non-negative for all agents.


CSG-VoI: Given a cost sharing  game (CSG) and subsidy budget s^*, does some subsidy scheme  with total subsidy at most s^* guarantee that no agent has negative value of information when a single action j is inspected (i.e. for fixed inspected action j, VoI_i,j(s,s̃^j,c_j)≥0 for any s∈_NE(𝕊), s̃^j,c_j∈_NE^c_j(𝕊), for each agent i∈ [n], and any posterior action cost c_j)?

We have the following hardness result, again using a reduction from  the min set cover problem.


    CSG-VoI is NP-Hard.






 §.§ Guaranteeing that the system functions in any NE

Here we consider a more challenging optimization objective applicable only to the component maintenance game. We seek  the optimal subsidy scheme with the least total value across all agents that receive the subsidy, and the goal of the central agent is to disburse sufficient subsidy to guarantee that the system functions in any Nash equilibrium. The decision problem in this case is stated as follows.

CMG-System: Given a component maintenance game (CMG) and subsidy budget s^*, does some subsidy scheme  with total subsidy at most s^* guarantee that the system functions in any  NE (i.e. ϕ(s)=1 for any s∈_NE(𝕊))? 

The reduction is similar to the proof of Theorem <ref>. We give a Karp mapping from any vertex cover instance ,k to a CMG-System instance and use a slightly different game instance for the reduction. We show that the system is guaranteed to function in any NE iff the subsidy budget is one less than the size of a smallest vertex cover. See Appendix <ref> for a proof of the following result.




    CMG-System is NP-Hard.


We will reduce the Vertex-Cover problem to CMG-System.  Given an instance ,k of the Vertex Cover problem, we create a corresponding CMG-System problem as follows. Introduce an agent i for every vertex  i∈ V and consider the (2-CNF) formula ϕ()=⋀_(i,j)∈ E(x_i x_j), where the clauses consist of states x_i,x_j for all pairs i,j of agents/components corresponding to edges in E. Set the probability distribution θ to be the constant distribution with the entire probability mass on 0^n (i.e. all the components are guaranteed to fail without repair). Set repair cost C_i=1-ϵ for 0<ϵ<1/n for all components i.

Observe that, 

    l_i(s_i,s_-i,θ)   =_∼θ[cost_i]
       =C_is_i+P_ϕ(θ)
       =(1-ϵ)s_i+1-ϕ(')
       =(1-ϵ)s_i+1-ϕ(s),
 where x_i'=max{0,s_i}=s_i denotes the state of component i after agent i takes action s_i. Note that WLOG s=0^n is a NE for this game, since any repair action by any agent increases the agent's cost by (1-ϵ) if the repair does not change the state ϕ of the system, and 0 otherwise (since ϕ is monotonic, it can only change from 0 to 1). We will now show that the remaining NEs for the game correspond to vertex covers of . 

Suppose K⊆[n] be a set of agents for which the corresponding nodes in  constitute a minimal vertex cover. Let s_K'=(s_1,…,s_n) where s_i=[i∈ K'], where [·] is the 0-1 valued indicator function and K'⊂ K with |K'|=|K|-1. Similarly, s_K:=(s_1,…,s_n) where s_i=[i∈ K]. Clearly, ϕ(s_K')=0 and ϕ(s_K)=1. If i∈ K, agent i does not reduce cost by switching from RE to DN since K is a minimal cover therefore not repairing component i causes the system to fail. If j∉ K, agent j does not reduce cost by switching from DN to RE as the system was already functioning. Further, if K is the set of agents corresponding to a non-minimal vertex cover, then there must be some agent that can reduce its cost by switching from RE to DN. 
Finally, if  K' ∅ is the set of agents with one or more agents short of a vertex cover, then any agent in K'  can reduce its cost by switching from RE to DN. This establishes that besides 0^n, only possible NE must correspond to a minimal vertex cover. 

To complete the reduction, we consider the game defined above and subsidy budget s^*=k-1. If there exists a vertex cover of size k, then a minimal cover K' has size k'≤ k. We design a subsidy scheme with total subsidy s'=k'-1≤ s^*, allocating subsidy of 1 for repair to all but one agent in the minimal cover K' and subsidy of 0 otherwise. Clearly the only agent not given subsidy will choose repair since cost of repair 1-ϵ is more than compensated by the change due to system state. As argued above, the only candidate NE are 0^n and s_K corresponding to some minimal vertex cover K. Without the subsidy, the social cost for 0^n is n (except the trivial case k=0) and that for s_K' is k'(1-ϵ) which is smaller. If we provide subsidy in our scheme  to the agents in K' except one then 0^n is no longer an NE. In particular, every subsidized agent in K' would now choose repair at cost 1-ϵ over doing nothing (even when the system stays broken after the repair) and the remaining agent in K' will choose repair if the system is broken. Thus, the system functions in all NEs.


Conversely, suppose there exists a subsidy scheme  with total subsidy at most s^*=k-1, such that the system functions in any  NE. Then either the system functions in 0^n and there is a 0-cover for graph , or the  NE corresponds to a minimal vertex-cover K' of size k' as the repaired components (in the subsidized game). In the latter case, we seek to show k'≤ k to complete the proof. Since the system is not assumed to function for s=s_κ for repair actions by agents in any κ⊂ K' with κ=k'-1, we
need to provide subsidy at least 1-ϵ to all but one agent in K'. That is, k-1=s^*≥ (1-ϵ)(k'-1)>k'-1-(k'-1)/n (since ϵ<1/n), or  k≥ k' since both k,k' are integers.



For the more general game where ϕ need not be monotone, a very similar argument as above can be used to show an even stronger hardness result. Namely CMG-System (with general boolean functions) is W[2]-hard, by reduction from Weighted CNF-SAT, i.e. deciding whether a CNF formula has a satisfying assignment with k variables assigned 1 (<cit.>, Lemma 23.3.1). This implies that it is unlikely that the problem is even fixed-parameter tractable (FPT), i.e. it is plausible that there is no computationally efficient algorithm for CMG-System even for a fixed small subsidy budget.



We will reduce Vertex-Cover to CIG-VoI. Recall that  Vertex-Cover is the following decision problem—given a graph =(V,E) and integer k, does there exist a vertex cover of size k? 

In  contrast to proof of Theorem <ref>, we will need to set a slightly higher subsidy and carefully adapt the argument to the value of information computation. 

We will create an instance of the CIG-VoI problem with n=|V|+1 agents, an agent each for vertices in  and an additional agent j=|V|+1. The construction of the instance and several arguments are similar to the proof of Theorem <ref>. The key difference is that we have an additional agent j that does not correspond to a vertex in . We will consider the inspection of the component c_j corresponding to this agent.  


Consider the (2-CNF) formula ϕ()=⋀_(u,v)∈ E(x_u x_v), where the clauses consist of states x_u,x_v for all pairs u,v of agents/components corresponding to edges in E. Set the probability distribution θ to be the constant distribution with the entire probability mass on 0^n (i.e. all the components are guaranteed to fail without repair). Set repair cost C_i=1-ϵ for 0<ϵ<1/n for all components i∈[|V|] and C_j=1. 
Therefore, 
l_i(s_i,s_-i,θ)=(1-ϵ)s_i+1-ϕ(s) for i∈[|V|] and l_j(s_j,s_-j,θ)=2-ϕ(s). Note that WLOG s=0^n is a NE for this game, since any repair action by any agent increases the agent's cost by (1-ϵ) if the repair does not change the state ϕ of the system, and 0 otherwise (since ϕ is monotonic, it can only change from 0 to 1). As shown in the proof of Theorem <ref>, the remaining NEs for the game correspond to minimal vertex covers of . Moreover, since ϕ(s) does not depend on s_j by definition, agent j will always prefer action DN for any s_-j. Let s_K:=(s_1,…,s_n) where s_i=[i∈ K] for any K⊆ V.

Notice that the prior and posterior games (for inspection of c_j) have identical cost matrices and equilibria for this component inspection game. To complete the reduction, we consider the game defined above and subsidy budget s^*=k. Suppose there exists a vertex cover of  of size k, then there exists a minimal vertex cover, say K' of size k'≤ k. We design a subsidy scheme with total subsidy s'=k'≤ s^*, allocating subsidy of 1 for repair to exactly the agents in K'. Clearly, all subsidized agents will always choose repair. We claim that the only NE after subsidy is s_K'. Indeed, by the above observation, any NE must be s_K for some K⊇ K'. But if K K', then any agent in K∖ K' will choose to do nothing as the system would function without their repair action. Since there is exactly one NE in prior and posterior games, Value of Information is exactly zero for all agents. 

Conversely, if there is no vertex cover of size k, then we show that no subsidy scheme with s^*≤ k may guarantee that no agent has negative value of information when a single component j is inspected. In this case the any vertex cover K' has |K'|>k. We consider two cases:

    
  Case 0: |K'|>k+1. Observe that if the subsidy provided to an agent is less than the repair cost 1-ϵ, then the agent will prefer to do nothing, except when repairing their component (given other players actions) changes the system state from 0 to 1. However, with a budget of s^*=k, the maximum number of agents that can receive a subsidy of at least 1-ϵ is at most k/1-ϵ<k+1, since ϵ<1/n and k<n WLOG. Thus, at least two agents are without subsidy at least 1-ϵ in K', and these agents will prefer to do nothing if only the agents K^*={i∈[|V|]| s^*_i>1-ϵ} with sufficient subsidy choose repair. Observe that both s_K' and s_K^* are Nash equilibria in the subsidized game. If s_K' is chosen as the prior equilibrium and s_K^* a posterior equilibrium, then the value of information for agents in K'∖ K^* is (1-ϵ)-1<0 since the system does not work in s_K^*.
    
  Case 1: |K'|=k+1. In this case, the only new possibility is if at least 1-ϵ subsidy is provided to all but one agent (say k') in K', then the remaining agent will choose repair. Without loss of generality, we assume k+1<n, and that K' is a minimal vertex cover. Now if v_k' denotes the vertex corresponding to agent k' in , and let E' denote the set of edges incident on vertices  V'⊆ V∖ K' with one end at v_k'. E' is non-empty, as otherwise K'∖{v_K'} would constitute a vertex cover for  contradicting minimality of K'. Observe that K_1=K'∖{v_K'}∪ V' is a vertex cover. Let K_2 denote a minimal vertex cover which is a subset of K_1. Now both s_K_2 and s_K' are NEs in the subsidized game. If the former is set as the prior equilibrium, and the latter a posterior equilibrium then, the value of information is negative (equals 0-(1-ϵ)=ϵ-1) for agent k'. 













Thus in either case, some agent has a negative value of information when the subsidy budget is k. This completes the reduction.






We consider an extension of the two agents connected in series, with additional components connected in series which are assumed to be uncontrolled by agents, and cannot be inspected or repaired. Let p_R denote the probability that all remaining components connected in series will all work. In addition to the prior game, we will now consider posterior games where component c_1 is inspected, and its state y_1 is revealed on inspection (y_1=1 corresponds to c_1 is functioning, and y_1=0 corresponds to c_1 is broken). Table <ref> summarizes prior and posterior costs for the two agents for each action pair (recall that DN denotes “do nothing” or s_i=0, and RE denotes “repair” or s_i=1). <cit.> show that value of information (VoI) is non-negative for all agents if only one component is inspected, and if a global  equilibrium is selected.






In the two-agent series game described above, if component c_j,j∈{1,2} is inspected, and actions are selected from global  equilibria, then VoI_i,j is non-negative for each agent i∈{1,2}. 


Therefore, if we avoid suboptimal local equilibria in this setting then VoI is guaranteed to be non-negative. Combined with Theorem <ref> above, this implies that negative Value of Information may be avoided via subsidizing repair costs in the two-agent series game. 


Suppose C_1>0 and C_2 p_Rp_2. For y_1=1 (component c_1 is inspected and found to be functioning), any Nash equilibrium is global.


Note that RE-RE cannot be a Nash equilibrium as agent 1 can reduce its cost by switching action from RE to DN. Similarly, RE-DN cannot be a Nash equilibrium either. If further C_2 p_Rp_2, or equivalently p_Rp_2p_R+C_2, then exactly one of DN-DN and DN-RE constitutes the unique Nash equilibrium, depending on the cost-minimizing action for agent 2. 




Suppose C_1∉{p_Rp_2}, and C_2∉{0, p_Rp_2}. For y_1=0 (component c_1 is inspected and found to be broken), if a Nash equilibrium is not global, it must be DN-DN.



DN-RE cannot be a Nash equilibrium if C_2>0. Now if RE-DN is a Nash equilibrium, it must be the only Nash equilibrium (since 1p_Rp_2+C_1 and p_Rp_2p_R+C_2) and therefore global.

If possible let RE-RE be a Nash equilibrium and not be global. Since RE-RE is a Nash equilibrium, we have p_R+C_1≤ 1 and p_R+C_2≤p_Rp_2. Therefore, p_R+C_1+p_R+C_2≤ 1+p_Rp_2≤ 2. Since p_Rp_2p_R+C_2, the only candidate for global equilibrium is DN-DN. Since RE-RE is not global, we must have p_R+C_1+p_R+C_2>2, a contradiction.


Now suppose there is a central authority which provides incentive/subsidy s for repairing the component. We can potentially have a targeted subsidy only available to a subset of agents, or a uniform subsidy available to all agents. Effectively this changes the cost parameters for the game, and can potentially enable the central authority to avoid negative VoI for the agents. We can also potentially consider conditional subsidy where the subsidy may be conditional on inspection results.


Suppose C_1∉{0,p_Rp_2}, and C_2∉{0, p_Rp_2}. A targeted subsidy s^*_1=C_1-p_Rp_2+ϵ for ϵ>p_Rp_1p_2 for agent 1 conditional on y_1=0 is sufficient to ensure that no agent has negative VoI when component 1 is inspected.



By Lemmas <ref> and <ref>, the only  possible posterior suboptimal Nash equilibrium is DN-DN for y_1=0.
With a subsidy s=C_1-p_Rp_2+ϵ, agent 1 has  cost  p_Rp_2+C_1-s=1-ϵ in RE-DN and p_R+C_1-s=1-ϵ-p_Rp_2 in RE-RE. Thus DN-DN is no longer an equilibrium, and the unique global equilibrium is either RE-DN if C_2>p_Rp_2, or RE-RE if C_2<p_Rp_2. If the prior is also a global equilibrium, by Theorem
<ref>, we have that no agent has negative VoI.

It only remains to consider possible prior suboptimal (local) equilibria. We consider four cases w.r.t. choice of prior suboptimal equilibria:

    
  Case 1: DN-DN is a local equilibrium. If y_1=1, the cost of each agent is only reduced for posterior actions DN-DN for both agents and hence VoI is non-negative. For posterior equilibrium  DN-RE agent 1's VoI is non-negative for the same reason. Agent 2 has VoI given by p_Rp_1p_2-(p_R+C_2)=p_Rp_1p_2-C_2≥ p_Rp_2-C_2 which is non-negative if DN-RE is a Nash equilibrium since
    
    p_R+C_2≤p_Rp_2 C_2≤ p_Rp_2

    
    By Lemma <ref> we only have above two cases if y_1=1. If y_1=0, after subsidy, only candidate posterior NEs are RE-DN and RE-RE. VoI for agent 2 is non-negative if it continues to DN, and the expression for RE-RE is identical to the DN-RE case for y_1=1 above. Cost for agent 1 cannot increase if ϵ>p_Rp_1p_2.
    
  Case 2: RE-RE is a local equilibrium, implying C_2≤ p_Rp_2. If y_1=1, Lemma <ref> now implies that DN-RE is the unique posterior NE. Cost for each can only decrease in this case. For y_1=0, only posterior NE is RE-RE where again cost cannot increase for any agent.
    
  Case 3: RE-DN is a local equilibrium. If y_1=1, agent 1's action is DN, and cost can only decrease. Agent 2's cost is at most p_Rp_2 for the candidate equilibria DN-DN and DN-RE. If y_1=0, cost of agent 1 can only decrease for posterior NEs RE-DN and RE-RE. Cost of agent 2 is again at most p_Rp_2 by similar reasoning as above. 
    
  Case 4: DN-RE is a local equilibrium, implying C_2≤ p_Rp_1p_2≤ p_Rp_2. If y_1=1, the only candidate posterior is DN-RE for which both agents have VoI p_Rp_1≥ 0. If y_1=0, the condition on C_2 implies that the only possibile posterior NE is RE-RE. For agent 2 VoI is again p_Rp_1≥ 0. For agent 1, the subsidized cost is 1-ϵ-p_Rp_2<1-p_Rp_1p_2-p_Rp_2=1-p_R(p_1p_2+1-p_2)=1-p_R(p_1+(1-p_1)(1-p_2))≤p_Rp_1.








The cost matrix for a two-agent parallel game is summarized in Table <ref>. For this case as well, 
the Value of Information may be negative if a local equilibrium is selected for some parameter settings. In the following we will show a dichotomy—if the repair costs are small then  a central agent using subsidy must subsidize the full costs of repair to avoid negative Value of Information of component inspection for the agents. Otherwise, the central agent can partially subsidize to avoid negative VoI.






Suppose C_1,C_2∉{0,p_R·p_2,p_R·p_1·p_2}. A subsidy scheme with s_1^*>max{C_1-p_R·p_1·p_2,min{C_1,p_R·p_2}} and s_2^*>max{C_2-p_R·p_1·p_2,min{C_2,p_R·p_2}}, conditional on inspection, is sufficient to avoid negative VoI for both agents when component 1 is inspected.


Note that RE-RE cannot be an equilibrium since C_1,C_2>0. Also negative VoI is not possible when the posterior is y_1=1 as the only Nash equilibrium is DN-DN with zero cost for each agent. 

First suppose min{C_1,C_2}≥p_R·p_1·p_2. This implies DN-DN is the prior equilibrium. In this case, the conditional subsidies of s_i^*=C_i-p_R·p_1·p_2 are sufficient to ensure that posterior repair costs for each agent is less than p_R·p_1·p_2≤p_R·p_2. Thus, DN-DN cannot be a posterior NE for y_1=0. For DN-RE and RE-DN, the subsidy ensures that VoI is non-negative for both agents.

Otherwise, we have three cases to consider w.r.t. relative choice values of repair costs and failure probabilities,


    
  Case 1: C_1< p_R·p_1·p_2≤ C_2. In this case, RE-DN is the prior equilibrium. 
    Moreover, since C_1< p_R·p_1·p_2≤p_R·p_2, agent 1 would prefer action RE over DN and so DN-DN cannot be a posterior NE for y_1=0. If RE-DN is the posterior NE, then by Table <ref> clearly VoI is non-negative for both agents. So it only remains to consider the posterior equilibrium DN-RE. If C_2>p_R·p_2, DN-RE cannot be an equilibrium, and we are done. If C_2≤p_R·p_2, then the subsidy s_2^*>min{C_2, p_R·p_2} ensures that VoI of agent 2 is non-negative even if DN-RE is the posterior equilibrium.  
    
    
  Case 2: C_2< p_R·p_1·p_2≤ C_1. The argument for this case is symmetric to the previous case, with DN-RE as the only possible prior equilibrium.
    
  Case 3: max{C_1,C_2}< p_R·p_1·p_2. In this case DN-RE as well as RE-DN can be prior Nash equilibria. Since max{C_1,C_2}< p_R·p_1·p_2≤p_R·p_2, DN-RE and RE-DN are the only candidate posterior NE. The setting of subsidies s_i^*>p_R·p_2≥p_R·p_1·p_2 > max{C_1,C_2} ensures that VoI is non-negative for both agents in this case.  
    





















 


 §.§ Games with incomplete information


In a game of incomplete information, there are n players. Player i has a type space T_i and an action space S_i. We write T = T_1 ×…× T_n and S = S_1 ×…× S_n. We assume that the type vector t is drawn from a distribution D (prior) over T that is common knowledge. The distribution D may or may not be a product distribution — that is, players’ types may or may not be stochastically independent. The cost c_i(t_i;s) of player i is determined by its type t_i and by the actions s chosen by all of the players. For example, in the component inspection game, each agent have two types, corresponding to the binary state of their component.

The expected cost of action s_i to agent i is c_i(s_i,D)=_t∼ D[c_i(t_i;s_i)].  Suppose the inspection of agent j reveals their type t_j. Denote posterior belief after the inspection of agent j by D^j,t_j. If agent i switches action from s_i to s_i^j,t_j after the inspection, the value of information about inspection of agent j for agent i is given by VoI_i,j(s_i,s_i^j,t_j) := l_i(s_i,D)-l_i(s_i^j,t_j,D^j,t_j). Typically we will assume that the actions s_i^j,t_j are Nash equilibria. We want this to be non-negative for each agent i.

We can extend the definition of PoIA to the more general setting.

TODO: extend to multiple inspections?


Let 𝕊={subs_i} denote the subsidy scheme. Consider the single agent inspection in an incomplete information game (T,S,D)  for inspection of agent j. Let _NE
(𝕊),_NE^t_j(𝕊)⊆ S (for t_j∈ T_j) denote the subset of states corresponding to Nash equilibria when the cost for agent i is cost_i-subs_i for prior, posteriors y_j=0 and y_j=1 respectively. Let VoI_j(𝕊)=min_i,s∈_NE(𝕊),s'∈∪_t_j∈ T_j_NE^t_j(𝕊)VoI_i,j(s_i,s'_i) denote the least value of information for any agent i for equilibria under 𝕊.  Then the Price of Information Avoidance  is given by 


    PoIA(j)=min_𝕊|VoI_j(𝕊)≥0max_s∈_NE
    (𝕊)cost(s)/min_𝕊max_s∈_NE(𝕊)=min_𝕊|VoI_j(𝕊)≥0PoA(𝕊)/min_𝕊PoA(𝕊).





 §.§ Subsidies can help avoid negative VoI in two-agent series component inspection game


Suppose we have two agents N={1,2} with components c_1,c_2 connected in series. Let p_1,p_2 denote the (prior) probability that the components c_1,c_2 will work (respectively) and p_R denote the probability that all remaining components (assumed uncontrolled by agents, and cannot be inspected or repaired) connected in series will all work. We will use the notation p:=1-p for simplicity. Table <ref> summarizes prior and posterior costs for the two agents for each action pair, where DN denotes “do nothing” (s_i=0) and RE denotes “repair” (s_i=1).



<cit.> show that value of information (VoI) is non-negative for all agents if only one component is inspected, and if a global equilibrium is selected.


If component c_j,j∈{0,1} is inspected, and actions are selected from global equilibria, then VoI_i,j is non-negative for each agent i∈{1,2}. 


Therefore, if we avoid suboptimal local equilibria in this setting then VoI is guaranteed to be non-negative. 


Suppose C_1>0 and C_2 p_Rp_2. For y_1=1 (component c_1 is inspected and found to be functioning), any Nash equilibrium is global.


Note that RE-RE cannot be a Nash equilibrium as agent 1 can reduce its cost by switching action from RE to DN. Similarly, RE-DN cannot be a Nash equilibrium either. If further C_2 p_Rp_2, or equivalently p_Rp_2p_R+C_2, then exactly one of DN-DN and DN-RE constitutes the unique Nash equilibrium, depending on the cost-minimizing action for agent 2. 




Suppose C_1∉{p_Rp_2}, and C_2∉{0, p_Rp_2}. For y_1=0 (component c_1 is inspected and found to be broken), if a Nash equilibrium is not global, it must be DN-DN.



DN-RE cannot be a Nash equilibrium if C_2>0. Now if RE-DN is a Nash equilibrium, it must be the only Nash equilibrium (since 1p_Rp_2+C_1 and p_Rp_2p_R+C_2) and therefore global.

If possible let RE-RE be a Nash equilibrium and not be global. Since RE-RE is a Nash equilibrium, we have p_R+C_1≤ 1 and p_R+C_2≤p_Rp_2. Therefore, p_R+C_1+p_R+C_2≤ 1+p_Rp_2≤ 2. Since p_Rp_2p_R+C_2, the only candidate for global equilibrium is DN-DN. Since RE-RE is not global, we must have p_R+C_1+p_R+C_2>2, a contradiction.


Now suppose there is a central authority which provides incentive/subsidy s for repairing the component. We can potentially have a targeted subsidy only available to a subset of agents, or a uniform subsidy available to all agents. Effectively this changes the cost parameters for the game, and can potentially enable the central authority to avoid negative VoI for the agents. We can also potentially consider conditional subsidy where the subsidy may be conditional on inspection results.


Suppose C_1∉{0,p_Rp_2}, and C_2∉{0, p_Rp_2}. A targeted subsidy s^*_1=C_1-p_Rp_2+ϵ for ϵ>p_Rp_1p_2 for agent 1 conditional on y_1=0 is sufficient to ensure that no agent has negative VoI when component 1 is inspected.



By Lemmas <ref> and <ref>, the only  possible posterior suboptimal Nash equilibrium is DN-DN for y_1=0.
With a subsidy s=C_1-p_Rp_2+ϵ, agent 1 has  cost  p_Rp_2+C_1-s=1-ϵ in RE-DN and p_R+C_1-s=1-ϵ-p_Rp_2 in RE-RE. Thus DN-DN is no longer an equilibrium, and the unique global equilibrium is either RE-DN if C_2>p_Rp_2, or RE-RE if C_2<p_Rp_2. If the prior is also a global equilibrium, by Theorem
<ref>, we have that no agent has negative VoI.

It only remains to consider possible prior suboptimal (local) equilibria. We consider four cases w.r.t. choice of prior suboptimal equilibria:

    
  Case 1: DN-DN is a local equilibrium. If y_1=1, the cost of each agent is only reduced for posterior actions DN-DN for both agents and hence VoI is non-negative. For posterior equilibrium  DN-RE agent 1's VoI is non-negative for the same reason. Agent 2 has VoI given by p_Rp_1p_2-(p_R+C_2)=p_Rp_1p_2-C_2≥ p_Rp_2-C_2 which is non-negative if DN-RE is a Nash equilibrium since
    
    p_R+C_2≤p_Rp_2 C_2≤ p_Rp_2

    
    By Lemma <ref> we only have above two cases if y_1=1. If y_1=0, after subsidy, only candidate posterior NEs are RE-DN and RE-RE. VoI for agent 2 is non-negative if it continues to DN, and the expression for RE-RE is identical to the DN-RE case for y_1=1 above. Cost for agent 1 cannot increase if ϵ>p_Rp_1p_2.
    
  Case 2: RE-RE is a local equilibrium, implying C_2≤ p_Rp_2. If y_1=1, Lemma <ref> now implies that DN-RE is the unique posterior NE. Cost for each can only decrease in this case. For y_1=0, only posterior NE is RE-RE where again cost cannot increase for any agent.
    
  Case 3: RE-DN is a local equilibrium. If y_1=1, agent 1's action is DN, and cost can only decrease. Agent 2's cost is at most p_Rp_2 for the candidate equilibria DN-DN and DN-RE. If y_1=0, cost of agent 1 can only decrease for posterior NEs RE-DN and RE-RE. Cost of agent 2 is again at most p_Rp_2 by similar reasoning as above. 
    
  Case 4: DN-RE is a local equilibrium, implying C_2≤ p_Rp_1p_2≤ p_Rp_2. If y_1=1, the only candidate posterior is DN-RE for which both agents have VoI p_Rp_1≥ 0. If y_1=0, the condition on C_2 implies that the only possibile posterior NE is RE-RE. For agent 2 VoI is again p_Rp_1≥ 0. For agent 1, the subsidized cost is 1-ϵ-p_Rp_2<1-p_Rp_1p_2-p_Rp_2=1-p_R(p_1p_2+1-p_2)=1-p_R(p_1+(1-p_1)(1-p_2))≤p_Rp_1.




Some observations from the proof:


  * Above proof in particular implies that a targeted conditional subsidy of s=C_1-p_rp_2 to agent 1 when component 1 is inspected is sufficient to avoid local equilibria when the component is inspected. Thus, a PoA of 1 is achievable in this case with the help of subsidy. 


    
    
  * Uniform/unconditional Subsidy. Note that if the subsidy is uniformly applied for all repair actions, subsidy plus social cost can exceed the social cost of global equilibrium in the absence of any subsidy. The subsidy to agent 2 is not necessary to avoid bad local equilibrium. The social cost s' for RE-RE is 2p_R+C_1+C_2. We have s+s'/s'< 1+C_1/C_1+C_2< 2. Can we also lower bound the PoA?


TODO. Discuss bounds on PoA and PoIA based on above theorem.



 §.§ Subsidies can help avoid negative VoI in two-agent parallel component inspection game


The cost matrix for a two-agent parallel game is summarized in Table <ref>. For this case as well, 
the value of information may be negative if a local equilibrium is selected for some parameter settings. In the following we will show a dichotomy. If the repair costs are small then  a central agent using subsidy must subsidize the full costs of repair to avoid negative value of information of component inspection for the agents. Otherwise, the central agent can partially subsidize to avoid negative VoI.






Suppose C_1,C_2∉{0,p_R·p_2,p_R·p_1·p_2}. A subsidy scheme with s_1^*>max{C_1-p_R·p_1·p_2,min{C_1,p_R·p_2}} and s_2^*>max{C_2-p_R·p_1·p_2,min{C_2,p_R·p_2}}, conditional on inspection, is sufficient to avoid negative VoI for both agents when component 1 is inspected.


Note that RE-RE cannot be an equilibrium since C_1,C_2>0. Also negative VoI is not possible when the posterior is y_1=1 as the only Nash equilibrium is DN-DN with zero cost for each agent. 

First suppose min{C_1,C_2}≥p_R·p_1·p_2. This implies DN-DN is the prior equilibrium. In this case, the conditional subsidies of s_i^*=C_i-p_R·p_1·p_2 are sufficient to ensure that posterior repair costs for each agent is less than p_R·p_1·p_2≤p_R·p_2. Thus, DN-DN cannot be a posterior NE for y_1=0. For DN-RE and RE-DN, the subsidy ensures that VoI is non-negative for both agents.

Otherwise, we have three cases to consider w.r.t. relative choice values of repair costs and failure probabilities,


    
  Case 1: C_1< p_R·p_1·p_2≤ C_2. In this case, RE-DN is the prior equilibrium. 
    Moreover, since C_1< p_R·p_1·p_2≤p_R·p_2, agent 1 would prefer action RE over DN and so DN-DN cannot be a posterior NE for y_1=0. If RE-DN is the posterior NE, then by Table <ref> clearly VoI is non-negative for both agents. So it only remains to consider the posterior equilibrium DN-RE. If C_2>p_R·p_2, DN-RE cannot be an equilibrium, and we are done. If C_2≤p_R·p_2, then the subsidy s_2^*>min{C_2, p_R·p_2} ensures that VoI of agent 2 is non-negative even if DN-RE is the posterior equilibrium.  
    
    
  Case 2: C_2< p_R·p_1·p_2≤ C_1. The argument for this case is symmetric to the previous case, with DN-RE as the only possible prior equilibrium.
    
  Case 3: max{C_1,C_2}< p_R·p_1·p_2. In this case DN-RE as well as RE-DN can be prior Nash equilibria. Since max{C_1,C_2}< p_R·p_1·p_2≤p_R·p_2, DN-RE and RE-DN are the only candidate posterior NE. The setting of subsidies s_i^*>p_R·p_2≥p_R·p_1·p_2 > max{C_1,C_2} ensures that VoI is non-negative for both agents in this case.  
    














 §.§ Beyond two agents



We extend the above results to beyond two agent component inspection games (prior work does not have general results for beyond two component inspection games.

We first consider a series connection of N={1,2,…,n} agents. We will extend the above results to this setting by providing a subsidy scheme to avoid negative value of information for all agents. We use the notation p_-A:=Π_j∈ [n]∖ Ap_j to denote that probability that all components other than components in set A are working. We will write p_-{i} as p_-i and p_-{i,j} as p_-ij for conciseness, given agents i,j∈[n].


Suppose C_i∉{0,p_-i}∪{p_-ijp_i}_j for each agent i∈[n]. A subsidy scheme s^*_i>C_i-p_-i+p_∅ conditional on y_i=0 for each agent i is sufficient to ensure that no agent has negative VoI when a single component is inspected.


Suppose  component c_i is inspected.  The given assumption implies that C_i∉{0,p_-i}, and C_j∉{0, p_-ijp_j}. By Theorem <ref>, a targeted subsidy s^*_i>C_i-p_-i+p_∅ for agent i conditional on y_i=0 is sufficient to ensure that no agent has negative VoI when component i is inspected. Thus, the proposed subsidy scheme works when any arbitrary component c_i is inspected.



We now consider a parallel connection of N={1,2,…,n} agents. We will again extend the above results to this setting by providing a subsidy scheme to avoid negative value of information for all agents. We use the notation p_-A:=Π_j∈ [n]∖ Ap_j to denote that probability that all components other than components in set A are not working. We will write p_-{i} as p_-i and p_-{i,j} as p_-ij for conciseness, given agents i,j∈[n]. 


Suppose C_i∉{0,p_∅}∪{p_-{j}}_j. A subsidy scheme with s_i^*>max{C_i-p_∅,min{C_i,p_-{i}}}, conditional on inspection, is sufficient to avoid negative VoI for all agents when a single component is inspected.



We use Theorem <ref> together with the observation that the probability that all components in a given set of components fails is no larger than at least one component in that set fails.

[Above expression for subsidy is somewhat loose; we could probably get a tighter but more complicated expression].


Above results can be used to obtain sufficient subsidies for mixed series-parallel connections to avoid negative value of information. Can we handle arbitrary binary functions relating component status to system status? What about real-valued status with goodness thresholds?





 §.§ General series-parallel game

In this case prior work <cit.> notes that agents can have negative VoI even when a global equilibrium is selected. TODO. We show that a central agent can still use subsidy to ensure negative VoI is avoided. The key idea is to express a general binary function ϕ of individual components using the Disjunctive Normal Form (DNF), and extend the above arguments to compute a bound on the subsidy sufficient to ensure at least one of the series of components corresponding to clauses containing the inspected component has all components working.



§ NEGATIVE VOI WHEN SHARING UNCERTAIN COSTS


Cost-sharing games are well-studied in the algorithm game theory literature <cit.>. Possible actions ={a_j} correspond to a subset of agents, i.e. there is a function f:→ 2^N such that 
agent i may use any action for which i∈ f(a_j). Note that there may be multiple options corresponding to the same subset of N. Under uniform cost-sharing, all agents that use an action a_j in some state s∈ S equally share its cost. That is, typically there is a deterministic function c:→_≥0 such that if k agents from f(a_j) use an action a_j in some state s, then cost_i(s) for each of these agents is c(a_j)/k. Here, we will consider a Bayesian extension where the costs of some actions in  are associated with some uncertainty. In this setting we will show that negative VoI is possible.

Example 1. Consider a two-agent cost-sharing game where the action set is ={A,B,C,D} with associated subsets f(A)={1,2}, f(B)={2}, f(C)={2}, and f(D)={1}. For example, in a commuting game, A could correspond to a shared public transport, and B,C,D could correspond to private modes of transport. We assume the cost function c is a random function such that with probability 1/2, c(A)=5, f(B)=2, f(C)=6, and f(D)=4, and with probability 1/2, c(A)=5, f(B)=6, f(C)=2, and f(D)=4. In the commute example, for agent 2, B could be a bike and C could be a car, and w_i could be unknown world state that impacts the cost of actions B and C for agent 2. We call these worlds w_1 and w_2 respectively (see Tables <ref> and <ref>). Thus the prior cost for agent 2 (i.e. probability weighted cost of the worlds w_1 and w_2) is 4 for actions B and C. Thus the only Nash equilibrium in the prior game is (A,A) with a cost of (2.5,2.5) for both agents. In world w_1, the only NE is (D,B) and in world w_2 the only NE is (D,C), both with cost (4,2). Thus the knowledge of the state of the world leads to negative VoI for agent 2. Specifically, the knowledge of the cheaper option among B and C causes agent 1 to drop out of the cost-shared option A, increasing social cost and cost for agent 2.



In the above example, the public knowledge of the world state of a simple uniform cost-sharing game results in negative VoI for one of the agents. It is possible to consider simple realistic extensions where VoI is negative for both agents, for example by adding additional cost when both agents use a “private mode” in the commuting example
. For example if an additional cost of 0.75 is charged to both agents for states (D,B) and (D,C) then it is easy to verify that prior and posterior equilibria remain the same but the posterior cost is increased to (4.75,2.75) causing negative VoI for both agents. 

In Example 1, using a subsidy of 3+ϵ for ϵ>0 for the option A guarantees that agent 2 will always prefer option A, and is sufficient to ensure that negative VoI (as well as suboptimal local equilibrium) is avoided.

TODO. Add sufficient condition on subsidy for this game similar to above results for component inspection games.





  §.§.§ Beyond pure series and pure parallel systems

For 3 agents, there are only two systems not covered by above, up to symmetry. For both these systems, one can work out how much subsidy is sufficient to avoid negative VoI but it involves tediously many cases to verify directly.

An alternative idea is to cover these cases by providing algorithms instead of general closed expressions for computing sufficient subsidy to avoid negative VoI, possibly by some lemmas to relate VoI in a system to a simpler system. 

A concrete next direction is to try to prove a hardness result for a large number of agents.





§ DATA-DRIVEN SUBSIDY IN REPEATED GAMES

The above computational hardness results for optimal subsidy design under vaious objectives motivate us to consider a beyond worst-case approach to finding a good subsidy for a given game. Specifically, we will consider the data-driven algorithm design paradigm introduced by <cit.>, and further studied by <cit.>. In this framework, we will assume access to multiple games coming from  the same  domain (e.g. infrastructure management in similar counties) and determine a good value of subsidy for unseen game instances from the same domain. We will consider 
games drawn i.i.d.  from an (arbitrary, unknown) game distribution, or games arriving in an online sequence. 
In the former we 
and will be interested in having a small sample complexity of the number of game samples needed to generalize well to an unseen sample from the same distribution. For the latter, we will study regret relative to the best possible subsidy scheme over the online sequence, in hindsight. We leave open questions related to computational complexity, some recently proposed techniques are applicable to our setting <cit.>.



 §.§ Sample complexity for subsidy schemes


In this section, we define the notion of sample complexity for designing sample-based subsidy schemes for cost minimization games. The sample complexity for (uniform convergence of) a given set of subsidy schemes measures how many samples are sufficient to ensure the expected social cost of any subsidy scheme in the set approximately matches its average cost over the game samples with high probability, for any given approximation and confidence level. 
In particular, if there is a subsidy scheme in the set with small social cost over a sufficiently large set of game samples, then that scheme will almost certainly have low cost in expectation over the distribution over games from which the samples are generated. Guarantees on sample complexity are a central topic in computational learning theory <cit.>. 

 The sample complexity for a class  of subsidy schemes is a function : _≥0×(0,1) →ℤ_≥1 defined such that for any ϵ>0, any δ∈ (0,1), any sample size N∈ℤ_≥1, and any distribution  over the games, with probability at least 1 -δ over the draw of a set S ∼^N, for any scheme  in , the difference between the average cost of  over 
S and the expected cost of  over  is at most ϵ, whenever N≥(ϵ,δ). In other words, 

    _S∼^N[∃∈ s.t. |1/N∑_v∈ Scost_ (v)-  [cost_ (v)]|> ϵ]< δ.





Note that the existence of a single ∈ that violates the ϵ-approximation for its expected cost is sufficient to cause the “failure” event which happens with probability δ. In other words, with probability 1-δ, all schemes  must observe uniform convergence of sample cost to expected cost (for sufficiently large sample). The 1 -δ high probability condition is needed because it is always possible that (with a very small but non-zero probability) the set of samples S, no matter how large, is completely unrepresentative of the distribution  over the games. 
Clearly, (ϵ,δ) should grow as δ or ϵ shrinks since we need to ensure that the difference between the average and expected cost of each subsidy in  is at most (ϵ,δ) with probability at least 1 -δ. 
The sample complexity (ϵ,δ) of class  of course also depends on the specific subsidy class . According to classic computational learning theory, the more “complex” the subsidy class  is, the more challenging it is to bound the difference between the average and expected cost of every subsidy in , i.e. richer subsidy classes  have larger sample camplexity (ϵ,δ). 


For an arbitrary class , a bound on the sample complexity allows the subsidy scheme designer to relate the expected cost of a scheme in  which achieves minimum average cost over the set of samples to the expected cost of an optimal scheme in , using classic arguments from learning theory <cit.>. More precisely, for a set of samples S from the distribution over buyers’ values, let Ŝ be the scheme in  that minimizes average cost over the set of samples and let ^* be the scheme in  that minimizes expected cost over . Finally, let P be the minimum cost achievable by any scheme in  over the support of the distribution . For any δ∈ (0,1), with probability at least 1 -δ over the draw of a set of N≥(ϵ,δ) samples S from , the difference between the expected cost of Ŝ over  and the expected cost of ^* over  is at most 2ϵ. 
Therefore, so long as there is a good sample complexity (ϵ,δ) bound for subsidy scheme class , the scheme designer can be confident that an optimal scheme over the set of observed samples competes with an optimal scheme in .



  
Pseudo-dimension. Pseudo-dimension <cit.> is a well-known learning theoretic measure of complexity of a class of functions (it generalizes the Vapnik-Chervonenkis  or VC dimension to real-valued functions), and is useful in obtaining bounds on the sample complexity of fitting functions from that class to given data.  
 Let  be a set of real valued functions from input space . We say that
C = (x_1, …, x_m)∈^m is pseudo-shattered by  if there exists a vector
r = (r_1, …, r_m)∈^m (called “witness”) such that for all
b= (b_1, …, b_m)∈{± 1}^m there exists h_b∈ such that sign(h_b(x_i)-r_i)=b_i. Pseudo-dimension of   is the cardinality of the largest set
pseudo-shattered by .


For a function class with  range [0,H] and pseudo-dimension d, a sample complexity bound of (ϵ,δ)=O(H^2/ϵ^2(d+log1/δ)) is well-known <cit.>. We conclude this section with a  useful general lemma from data-driven algorithm design, restated in the specific context of games, for giving upper bounds on the pseudo-dimension of certain loss function classes. 

 (Lemma 2.3, <cit.>)
     Suppose that for every game G ∈, the objective function L_G(σ) : → which maps game parameter σ (e.g. subsidy allocation) to the objective value (e.g. cost of worst-case equilibrium) is piecewise
constant with at most N pieces. Then the dual class family {L_σ(·):→| L_σ(G)= L_G(σ)} defined on games in  has pseudo-dimension O(log N). 




 §.§ Sample complexity for subsidizing games drawn from a distribution



Learning uniform subsidies. We start with some initial results on learning a good value of the subsidy even in the absence of considerations about value of information, or possible equilibria in posterior games. We will consider uniform subsidy σ∈_≥ 0 conditional on repair (i.e. reduces cost of repair for all agents that choose to repair).
A simple loss objective in this uniform subsidy setting is given by


    L_prior(σ):=  max_s∈_NE(σ)cost^σ(s)+n_sσ,

where n_s is the number of agents that choose repair in joint state s, _NE(σ) and cost^σ(s) denote the set of Nash equilibria and (respectively) the updated total cost, when a uniform  subsidy of σ is applied. We further assume all the repair costs as well as subsidy budget is no more than H, i.e. σ, C_i≤ H for each i∈[n]. Therefore, L_prior(σ)≤ (2H+1)n.


Suppose the central agent (learner) who needs to set the subsidy has repeated instances of this game (e.g. cost matrices) drawn from a distribution. Can we learn a good value of uniform subsidy σ^*, that has small expected loss over the distribution?
Our proof involves a bound on the number of critical subsidy values at which the set of Nash equilibria could possibly change by examining the subsidy values at which the preferred actions of an individual agent i conditional on any fixed joint action s_-i of the remaining agents, and use of Lemma <ref> <cit.>. Add more details/sketch on tools used.


For any ϵ,δ>0 and any distribution  over component maintenance games with n agents, O(n^2H^2/ϵ^2(n+log1/δ)) samples of the game drawn from  are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the best value of uniform subsidy σ̂^̂*̂ over the sample  has expected loss L_prior(σ̂^̂*̂) that is at most ϵ larger than the expected loss of the best value of subsidy over .


Consider any fixed component maintenance game G. Observe that if actions of all agents except agent i i.e. s_-i' is fixed (2^n-1 possibilities), then the agent i will repair their component provided the  cost under subsidy C_i-σ^*+1-_θϕ('(1,s_-i')) is smaller than 1-_θϕ('(0,s_-i')). That is we have at most 2^n-1 critical values of σ^* where the preferred action of agent i may change. Over n agents, we have at most n2^n-1 such points. Moreover, the loss is piecewise constant in any fixed piece.

Given the piecewise-constant structure with a bound on the total number of pieces, the sample complexity bound follows from standard learning theoretic arguments. In more detail, by Lemma <ref>, this implies that the pseudo-dimension of the loss function class parameterized by the subsidy value is at most O(log(n2^n-1))=O(n) and   classic bounds <cit.> imply the sample complexity result.








Note that a naive bound of O(2^n) could be derived on the pseudo-dimension of any n player game, where each player has 2 possible actions. This is because there are 2^n distinct states and therefore at most 2^2^n possible distinct state subsets which could correspond to a Nash Equilibrium. The critical subsidy values σ^* correspond to values at which the set of NE changes, and for any pair of state subsets exactly one could be the set of NE for all values of subsidy above (respectively below) some critical value σ^*. The loss is again piecewise constant, and by Lemma <ref> we have that the pseudo-dimension is O(2^n). The above proof makes use of cost matrix of the component maintenance game to obtain the exponentially better upper bound of O(n).


Learning non-uniform subsidies. We are further able to obtain a sample complexity bound even for the non-uniform subsidy scheme defined above, where the central agent can provide a different subsidy to each agent depending on their component cost, failure probability and how critical the component is to overall system functionality. The subsidy scheme consists of a vector of  multiple real-valued parameters, one for each agent.-1 


    L_prior():=  max_s∈_NE()cost^(s)+subs(s).


We assume that subs_i(s), C_i≤ H for each i∈[n], and therefore L_prior()≤ (2H+1)n. Again, we are able to give a polynomial sample complexity for the number of games needed to learn a good value of subsidy with high probability over the draw of game samples coming from some fixed but unknown distribution (proof in Appendix <ref>).




For any ϵ,δ>0 and any distribution  over component maintenance games with n agents, O(n^2H^2/ϵ^2(n^2+log1/δ)) samples of the game drawn from  are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the best vector of subsidies over the sample σ̂^̂*̂ has expected loss L_prior that is at most ϵ larger than the expected loss of the best vector of subsidies over .


Consider any fixed game G. Given any joint action s=(s_i,s_-i), an agent i's decision for switching their action from s_i to s_i:=1-s_i is determined by the inequality  (C_i-σ^*_i)s_i+1-Φ(s_i,s_-i')≤ (C_i-σ^*_i)(s_i)+1-Φ(s_i,s_-i'), where Φ(s):=_θ[ϕ('(s))], which is linear in s_i^*, the subsidy provided to agent i. Thus, for each agent i, we have at most 2^n-1 axis-parallel hyperplanes in the parameter space in ^n, or a total of n2^n-1 hyperplanes overall. Moreover, the loss function as a function of the parameters is piecewise constant in any fixed piece. Therefore the loss function class is (n,n2^n-1)-delineable in the sense of <cit.>, that is the subsidy parameter space is Euclidean in n dimensions and is partitioned by at most n2^n-1 hyperplanes into regions where the loss is linear (in this case constant) in the parameters.better bound?




By using a general result from <cit.> which states add stmt to appendix? that a (d,t)-delineable function class has pseudo-dimension O(dlog(dt)), the above structural argument implies that the pseudo-dimension of the loss function class parameterized by the subsidy value is at most O(nlog(n^22^n-1))=O(n^2) and the sample complexity result follows <cit.>.




Learning conditional subsidies. We will now obtain a sample complexity bound for  non-uniform subsidy schemes in component inspection games, where the central agent provides subsidy only in posterior games. Let  denote the subsidy scheme. Let _NE^0(𝕊) (resp. _NE^1(𝕊)) denote the subset of states in S corresponding to Nash equilibria when the cost for agent i is the subsidized cost cost_i^,0 (resp. cost_i^,1) for posterior y_j=0 (resp. y_j=1). For component inspection game of component c_1 (wlog), define 


    L_posterior():=  p_1L_posterior^1()+p_1L_posterior^0(),



where L_posterior^i():=max_s∈_NE^i()cost^,i(s)+subs^i(s). We assume that subs_i^j(s)≤ H, C_i≤ H for each i∈[n], j∈{0,1}, thus  L_posterior()≤ (2H+1)n. In this case too, we are able to give a polynomial sample complexity for the number of games needed to learn a good value of subsidy with high probability over the draw of game samples coming from some fixed but unknown distribution (proof in Appendix <ref>).


For any ϵ,δ>0 and any distribution  over component inspection games with n agents, O(n^2H^2/ϵ^2(n^2+log1/δ)) samples of the component inspection game drawn from  are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the best vector of subsidies over the sample σ̂^̂*̂ has expected loss L_posterior that is at most ϵ larger than the expected loss of the best vector of subsidies over .



Consider any fixed game G. Given any joint action s=(s_i,s_-i), an agent i's decision for switching their action from s_i to s_i:=1-s_i in posterior game y_1=y is determined by the inequality  (C_i-s^y_i)s_i+1-Φ(s_i,s_-i')≤ (C_i-s^y_i)(s_i)+1-Φ(s_i,s_-i') (with  Φ(s):=_θ^1,y[ϕ('(s))]), which is linear in s_i^y, the subsidy provided to agent i conditional on y_1=y. Thus, for each agent i, we have at most 2· 2^n-1 axis-parallel hyperplanes in the parameter space in ^2n, or a total of n2^n hyperplanes overall. Moreover, the loss function as a function of the parameters is piecewise constant in any fixed piece. Therefore the loss function class is (2n,n2^n)-delineable in the sense of <cit.>. The rest of the argument is similar to the proof of Theorem <ref>, differing only in some multiplicative constants.






A similar sample complexity bound can also be given for learning conditional subsidies from game samples, by minimizing a loss based on the social cost in the posterior game. See Theorem <ref> in Appendix <ref>. Note that minimization of L_prior corresponds to minimization of PoA(). To guarantee that the system functions, we can simply add a regularization term λ (1-ϕ(s)), for sufficiently large λ > (2H+1)n. 

In learning terminology, our results imply a bound on the number of sample games in the “training set” to do well on an unseen “test” game instance from the same distribution. We note that optimization over the training set is still computationally hard, but we can avoid solving the hard problem over and over again for repeated test instances.

Our techniques extend beyond losses that are based on worst case equilibria in the subsidized game. We define the following loss that considers average case Nash Equilibrium, and obtain similar same complexity guarantees as in Theorem <ref> above. 


    L̃_prior():= 1/|_NE()|∑_s∈_NE()cost^(s)+subs(s).


We remark that, generally speaking, average case NE are known to be hard to analyze and give any useful guarantees for <cit.>. Our result below indicates the potential of data-driven algorithm design to handle such challenging objectives and obtain meaningful learning guarantees. In particular, given a sufficiently large sample of games, we can compute near-optimal subsidy schemes with high confidence for minimizing the average cost of Nash equilibria, not just the worst case Nash equilibrium.


Suppose subs_i(s), C_i≤ H for each i∈[n]. For any ϵ,δ>0 and any distribution  over component maintenance games with n agents, O(n^2H^2/ϵ^2(n^2+log1/δ)) samples of the game drawn from  are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the best vector of subsidies over the sample σ̂^̂*̂ has expected loss L̃_prior that is at most ϵ larger than the expected loss L̃_prior of the best vector of subsidies over .


Cost-sharing games. We first consider the problem of learning a good value of subsidy in the prior game. The subsidy scheme consists of a vector of  multiple real-valued parameters, one for each action. We define the loss of the central agent in a game G as the total social cost in the worst-case Nash Equilibrium under the subsidy scheme , plus the total subsidy paid out by the central agent in the scheme , i.e.,


    L_prior():=  max_s∈_NE()cost^(s)+subs(s).


 We assume that c^(a), c(a)≤ H for each a∈, and therefore L_prior()≤ 2H||.


  
For any ϵ,δ>0 and any distribution  over fair cost sharing games with N agents and || actions, O(||^2H^2/ϵ^2(||log ||N+log1/δ)) samples of the game drawn from  are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the best vector of subsidies over the sample σ̂^̂*̂ has expected loss L_prior that is at most ϵ larger than the expected loss of the best vector of subsidies over .







        










    Another goal of the central agent is to avoid an increase in the social cost due to knowledge of the true costs. We denote the true costs by c̃:→_≥0, which are assumed to be known in the posterior game, and the corresponding social costs by cost(·). Let _NE denote the corresponding set of Nash Equilibria. We have

    
    L_VoI():=  max_s∈_NE()cost^(s) -  max_s∈_NE()cost^(s).


This corresponds to the increase in the social cost relative to the prior game, when the true costs are known. The central agent would like to minimize this “VoI” loss.


 
For any ϵ,δ>0 and any distribution  over fair cost sharing games with N agents and || actions, O(||^2H^2/ϵ^2(||log ||N+log1/δ)) samples of the game drawn from  are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the best vector of subsidies over the sample σ̂^̂*̂ has expected loss L_VoI that is at most ϵ larger than the expected loss of the best vector of subsidies over .






TODO: Extensions for VoI?

add cost-sharing results



 §.§ No-regret when subsidizing in an online sequence of games


In the online setting, we receive a sequence of games at times (rounds) t=1,…, T. In each round t, the central agent must set a value of the (say uniform) subsidy σ_t, with potentially some feedback on previous rounds but no knowledge of the game parameters (costs/priors) of the current or future rounds. This is more pessimistic (but potentially also more realistic) than the distributional setting above. In particular, the sequence of games may be adversarially picked. The performance of the algorithm is measured by the difference in the cumulative loss for the selected subsidy values and the cumulative loss of the best fixed value of subsidy in hindsight, also known as regret (R_T).


    R_T:= ∑_t=1^TL_prior(σ_t)-min_σ∈[0,H]L_prior(σ).


“No-regret” corresponds to R_T being sublinear in T, and the average regret R_T/T approaches zero for large T in this case. We will impose a mild assumption on the repair costs C_i to obtain good results in the online setting. We will assume that the costs are not known exactly, but come from some smooth distribution. Formally, 


    We assume that the probability distributions generating the costs have κ-bounded probability density, i.e. max_x∈f_i(x)≤κ for some κ∈^+, where f_i denotes the probability density function for cost C_i.

 The adversary designing the sequence of games may  select any bad distribution as long as it is smooth. Under this assumption, our analysis above and  tools from <cit.> can be used to show that the online sequence of loss functions is dispersed <cit.>. Dispersion, informally speaking, captures how amenable a non-Lipschitz function is to online learning. As noted in <cit.>, dispersion is a sufficient condition for learning piecewise Lipschitz functions online, even in changing environments. A formal definition is included below.-1



The sequence of random loss functions L_1, …,L_T is β-dispersed for the Lipschitz constant ℓ if, for all T and for all ϵ≥ T^-β, we have that, in expectation, at most
O(ϵ T) functions (here Õ suppresses dependence on quantities beside ϵ,T and β, as well as logarithmic terms)
are not ℓ-Lipschitz for any pair of points at distance ϵ in the domain . That is, for all T and  ϵ≥ T^-β, 


    [
    max_ρ,ρ'∈
    ||ρ-ρ'||_2≤ϵ|{ t∈[T] | |L_t(ρ)-L_t(ρ')|>ℓ||ρ-ρ'||_2}|]
    ≤O(ϵ T).









Under Assumption <ref>, we have the following guarantee about online learning of uniform subsidy in a sequence of games, namely one can predict good values of subsidy (with Õ(√(n/T)) average expected regret over T online rounds). We establish 1/2-dispersion of the sequence of loss functions under the above assumption and use results from <cit.> to obtain the regret bound (proof in Appendix <ref>). 




Suppose Assumption <ref> holds. Let L_1,…, L_T:[0,H]→[0,(2H+1)N] denote an independent sequence of losses L_prior(σ) as a function of the uniform subsidy value σ, in an online sequence of T component maintenance games. 
Then the sequence of functions is 1/2-dispersed and there is an online algorithm with O(√(nT)) expected regret.




    The key idea is to observe that each loss function L_t has  at most K=n2^n-1 discontinuities (as in proof of Theorem <ref> above). Further, any interval of length ϵ has at most O(κϵT)  functions that are non-Lipschitz in that interval, in expectation. This uses Assumption <ref>, and the observation that critical values of s^* are linear in some cost C_i. Indeed, as shown in the proof of Theorem <ref>, the critical values of subsidy are given by s^*=C_i+_θϕ(0,s_-i')-_θϕ(1,s_-i') for some agent i and joint action s_-i'.
    By <cit.> then the expected number of non-Lipschitz losses on the worst interval of length ϵ is at most Õ(Tϵ+√(Tlog(TK)))=Õ(√((n+log T)T)) for ϵ≥1/√(T).
    
    This implies 1/2-dispersion of the sequence of loss functions in the sense of Definition <ref>. 
    Then Theorem 5 from <cit.> with M=1 implies the desired regret bound. 



The online algorithm which achieves the above regret guarantee is the Exponential Forecaster algorithm of <cit.>, a continuous version of the well-known exponential weights update algorithm <cit.>. We can further extend the result to learning a non-uniform subsidy scheme under Assumption <ref>, with a Õ(√(nT)) regret bound, using the same online algorithm. 


Suppose Assumption <ref> holds. Let L_1,…, L_T:[0,H]^n→[0,(2H+1)N] denote an independent sequence of losses L_prior() as a function of the  subsidy scheme  parameterized by subsidy values {σ_i}, in an online sequence of T component maintenance games. 
Then the sequence of functions is 1/2-dispersed and there is an online algorithm with O(√(nT)) expected regret.



TODO: Add algo for semi-bandit feedback set computation?




For components connected in pure series or pure parallel games, we can further improve the above bound on the sample complexity of learning the best subsidy from game samples.


For any ϵ,δ>0 and any distribution  over component inspection games with n agents, connected either all in parallel or all in series, O(1/ϵ^2(log nlog1/ϵ+1/δ)) samples of the component inspection game drawn from  are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the best value of subsidy over the sample ŝ^̂*̂ has expected loss that is at most ϵ larger than the expected loss of the best value of subsidy over .


We first consider the all parallel case. In this setting, an agent i could possible prefer RE only if all the other agents choose DN, i.e. for exactly one possible s'_-i. That is we have at most one critical values of s^* where the preferred action of agent i may change. Over n agents, we have at most n such points. The loss is piecewise constant in any fixed piece, and a similar argument as above (i.e. Lemma 2.3 of <cit.> and standard generalization guarantees) imply the pseudo-dimension is O(log n) and hence the claimed sample complexity result.

We will now consider the all series case. This case is  more interesting, as the preferred action of an agent i could change for multiple possible s_-i'. However, we note that across any possible critical s^* the preferred action can only change from DN to RE as we increase the subsidy from just below s^* to just above it. Therefore, there is at most one relevant breakpoint in the loss function for any agent i. Adding up over n agents, we have at most n breakpoints and the rest of the argument is the same as above. 






§ DISCUSSION


We study the problem of resource allocation for infrastructure maintenance in systems with privately owned components, and in classical cost-sharing games. The former captures the typical organization of engineering systems, computer networks, or project pipelines, and the latter corresponds to typical market systems. We identify useful metrics related to the well-studied price of anarchy, as well as the recently introduced value of information metric that a central agent may care about, and examine the challenge in optimally allocating resources to optimize these metrics. 


Our work employs a data-driven approach, which has not been previously employed in the literature of subsidy or taxation design where the focus has largely been on designing approximations for worst-case game parameters. An interesting further question is to extend this idea of analyzing “typical” games to potentially obtain better domain-specific subsidy schemes in other interesting games. Also our learning-based approach allows modeling more realistic settings, where the game parameters or even set of agents may change over time.












§ TABLES


The “” document class includes the “”
package — <https://ctan.org/pkg/booktabs> — for preparing
high-quality tables.

Table captions are placed above the table.

Because tables cannot be split across pages, the best placement for
them is typically the top of the page nearest their initial cite.  To
ensure this proper “floating” placement of tables, use the
environment table to enclose the table's contents and the
table caption.  The contents of the table itself must go in the
tabular environment, to be aligned properly in rows and
columns, with the desired horizontal and vertical rules.  Again,
detailed instructions on tabular material are found in the
 User's Guide.

Immediately following this sentence is the point at which
Table <ref> is included in the input file; compare the
placement of the table here with the table in the printed output of
this document.



To set a wider table, which takes up the whole width of the page's
live area, use the environment table* to enclose the table's
contents and the table caption.  As with a single-column table, this
wide table will “float” to a location deemed more
desirable. Immediately following this sentence is the point at which
Table <ref> is included in the input file; again, it is
instructive to compare the placement of the table here with the table
in the printed output of this document.



Always use midrule to separate table header rows from data rows, and
use it only for this purpose. This enables assistive technologies to
recognise table headers and support their users in navigating tables
more easily.



§ MATH EQUATIONS

You may want to display math equations in three distinct styles:
inline, numbered or non-numbered display.  Each of the three are
discussed in the next sections.



 §.§ Inline (In-text) Equations

A formula that appears in the running text is called an inline or
in-text formula.  It is produced by the math environment,
which can be invoked with the usual
 construction or with
the short form . You can use any of the symbols
and structures, from α to ω, available in
 <cit.>; this section will simply show a few
examples of in-text equations in context. Notice how this equation:

  lim_n→∞x=0
,
set here in in-line math style, looks slightly different when
set in display style.  (See next section).



 §.§ Display Equations

A numbered display equation—one set off by vertical space from the
text and centered horizontally—is produced by the equation
environment. An unnumbered display equation is produced by the
displaymath environment.

Again, in either environment, you can use any of the symbols and
structures available in ; this section will just give a couple
of examples of display equations in context.  First, consider the
equation, shown as an inline equation above:

    lim_n→∞x=0

Notice how it is formatted somewhat differently in
the displaymath
environment.  Now, we'll enter an unnumbered equation:

  ∑_i=0^∞ x + 1

and follow it with another numbered equation:

    ∑_i=0^∞x_i=∫_0^π+2 f

just to demonstrate 's able handling of numbering.



§ CITATIONS AND BIBLIOGRAPHIES


The use of  for the preparation and formatting of one's
references is strongly recommended. Authors' names should be complete
— use full first names (“Donald E. Knuth”) not initials
(“D. E. Knuth”) — and the salient identifying features of a
reference should be included: title, year, volume, number, pages,
article DOI, etc.

The bibliography is included in your source document with these two
commands, placed just before the  command:

where “” is the name, without the “”
suffix, of the  file.

Citations and references are numbered by default. A small number of
ACM publications have citations and references formatted in the
“author year” style; for these exceptions, please include this
command in the preamble (before the command
“”) of your  source:



  Some examples.  A paginated journal article <cit.>, an
  enumerated journal article <cit.>, a reference to an entire
  issue <cit.>, a monograph (whole book) <cit.>, a
  monograph/whole book in a series (see 2a in spec. document)
  <cit.>, a divisible-book such as an anthology or compilation
  <cit.> followed by the same example, however we only output
  the series if the volume number is given <cit.> (so
  Editor00a's series should NOT be present since it has no vol. no.),
  a chapter in a divisible book <cit.>, a chapter in a
  divisible book in a series <cit.>, a multi-volume work as
  book <cit.>, a couple of articles in a proceedings (of a
  conference, symposium, workshop for example) (paginated proceedings
  article) <cit.>, a proceedings article with
  all possible elements <cit.>, an example of an enumerated
  proceedings article <cit.>, an informally published work
  <cit.>, a couple of preprints <cit.>, a doctoral dissertation <cit.>, a
  master's thesis: <cit.>, an online document / world wide web
  resource <cit.>, a video game
  (Case 1) <cit.> and (Case 2) <cit.> and <cit.>
  and (Case 3) a patent <cit.>, work accepted for
  publication <cit.>, 'YYYYb'-test for prolific author
  <cit.> and <cit.>. Other cites might
  contain 'duplicate' DOI and URLs (some SIAM articles)
  <cit.>. Boris / Barbara Beeton:
  multi-volume works as books <cit.> and <cit.>. A
  couple of citations with DOIs:
  <cit.>. Online
  citations: <cit.>.
  Artifacts: <cit.> and <cit.>.













§ ACKNOWLEDGEMENT

We thank Chaochao Lin for helpful initial discussions, and are grateful to Avrim Blum, Hedyeh Beyhaghi, Siddharth Prasad, Keegan Harris and Rattana Pukdee for useful comments. This material is based on work supported by the National Science Foundation under grants CCF1910321, IIS 1901403, and SES 1919453.











alpha



























§ APPENDIX



§ PROOFS FROM SECTION <REF>


Proposition <ref> (restated). In the two-agent series prior game (defined above and cost matrix noted in the first row of Table <ref>), the Price of Anarchy in the absence of subsidy is at least PoA≥2/p_1+p_2, 
for some repair costs C_1,C_2. More generally, for n agents, PoA≥H̃/G̃^n for some repair costs C_1,…,C_n, where H̃ and G̃ are the harmonic and geometric means, respectively, of the prior probabilities p_1,…,p_n.


    We set C_1=p_1p_2 and C_2=p_2p_1. Observe that DN-DN is an equilibrium since[In our notation, p_1p_2:=1-p_1p_2,  while p_1·p_2:=(1-p_1)·(1-p_2).] p_1p_2=p_1+p_2p_1≤p_1+C_2, and similarly p_1p_2≤p_2+C_1. Also, RE-RE is an equilibrium since C_1=p_1p_2≤p_1 and C_2=p_2p_1≤p_2. Clearly,
    
    PoA≥cost(DN,DN)/cost(RE,RE)=2p_1p_2/C_1+C_2≥2/p_1+p_2,

    where the last inequality follows from the observations
    
    p_1p_2(p_1+p_2)=p_1+p_2-(p_1+p_2)p_1p_2≥ p_1+p_2-2p_1p_2 = C_1+C_2.

    For the n agent series game, we set the costs C_i=p_iΠ_j ip_j. DN^n (i.e., s=0^n) is a Nash equilibrium, since 
    C_i+Π_j ip_j=(1-p_i)Π_j ip_j+1-Π_j ip_j≥Π_jp_j.
 Moreover, RE^n is also an equilibrium as C_i≤p_i for all i∈[n]. Therefore,
    
    PoA   ≥cost(DN^n)/cost(RE^n)=nΠ_ip_i/∑_iC_i
       =n(1-Π_ip_i)/∑_iΠ_j ip_j - nΠ_ip_i
       ≥n(1-Π_ip_i)/∑_iΠ_j ip_j - (∑_iΠ_j ip_j)Π_ip_i
       =n/∑_iΠ_j ip_j
       =n/Π_ip_i·∑_i1/p_i,

    and the claim follows by noting H̃=n/∑_i1/p_i and G̃=(Π_ip_i)^1/n.
    


Theorem <ref> (restated). 
    Consider the two-agent series component maintenance game with C_1,C_2>0 and 0<p_1,p_2<1. Let s^*={(C_1,C_2)∈ [p_1p_2,p_1]× [p_2p_1,p_2]}·min{C_1-p_1p_2, C_2-p_2p_1}, where {·} denotes the 0-1 valued indicator function. Then there exists a subsidy scheme   with total subsidy s for any s>s^* such that PoA(𝕊)=1. Moreover, a total subsidy of at least s^* is necessary for any subsidy scheme  that guarantees PoA(𝕊)=1. 


 We will characterize the set of values of C_1,C_2 for which there are multiple Nash equilibria and design subsidy schemes that achieve PoA(𝕊)=1. We consider the following cases.


    
  Case 0: C_1<p_1p_2,C_2>p_2. In this case the only NE is RE-DN (Table <ref>). Thus, PoA =1 even in the absense of subsidy and s^*=0 in this case.
    
  Case 1: C_1=p_1p_2,C_2>p_2. Both RE-DN and DN-DN are Nash equilibria, and 
    cost(RE,DN)=C_1+2p_2=p_1p_2+2p_2=2-p_1p_2-p_2<2p_1p_2=cost(DN,DN).
 An arbitrarily small subsidy to agent 1 is sufficient to guarantee PoA(𝕊)=1 (therefore s^*=0 works) as DN-DN would no longer be a NE.
    
  Case 2: C_1>p_1p_2,C_2>p_2. In this case the only NE is DN-DN. Thus, PoA =1 even in the absense of subsidy.
    
  Case 3: C_1<p_1p_2,C_2=p_2. Both RE-DN and RE-RE are Nash equilibria, and 
    cost(RE,DN)=C_1+2p_2>C_1+p_2=C_1+C_2=cost(RE,RE).
 An arbitrarily small subsidy to agent 2 is sufficient to guarantee PoA(𝕊)=1 (therefore s^*=0 works)  as RE-DN would no longer be a NE.
    
  Case 4: C_1<p_1p_2,C_2<p_2. In this case the only NE is RE-RE. Thus, PoA =1 even in the absense of subsidy.
    
  Case 5: (C_1,C_2)∈ [p_1p_2,p_1]× [p_2p_1,p_2]. Both RE-RE and DN-DN are Nash equilibria, and OPT corresponds to RE-RE. A subsidy greater than C_1-p_1p_2 to agent 1, or a subsidy greater than C_2-p_2p_1 to agent 2 guarantees that the only NE is RE-RE. Further, in either case PoA(𝕊)=1 as the subsidy equals the reduction in the repair cost of the respective agent.

    Further suppose a subsidy of s^*=s^*_1+s^*_2 is sufficient to ensure PoA(𝕊)=1 in this case. Now if subsidy to agent 1 s_1^*≤ C_1-p_1p_2 and subsidy to agent 2 s_2^*≤ C_2-p_2p_1. Then both DN-DN and RE-RE are NE and PoA(𝕊)>1 since the worst-case equilibrium (i.e. DN-DN) cost does not depend on the subsidy. Therefore either s_1^*> C_1-p_1p_2 or s_2^*> C_2-p_2p_1, establishing that a subsidy of at least s^* is necessary in this case to ensure PoA(𝕊)=1.

    

    
  Case 6: Otherwise. By symmetry, the case is similar to one of  C0 through C4 with agents 1 and 2 switched. s^*=0 and price of anarchy of 1 is achieved by no or arbitrarily small subsidy as above.

Note that s^* is non-zero only in case C5, in which case we have established both sufficiency and necessity of a total subsidy of s^* to ensure PoA(𝕊)=1.
    



Theorem <ref> (restated). 
    Consider the two-agent series component maintenance game with C_1,C_2>0 and 0<p_1,p_2<1. Define R⊂^+×^+ as the set of cost pairs that satisfy C_1≤p_1 C_2≤p_2 (C_1≤p_1p_2 C_2≤p_2p_1), depicted in Figure <ref>. Let s^*=min_(x,y)∈ R||(C_1,C_2)-(x,y)||_1, where ||·||_1 denotes the L_1-norm. Then there exists a subsidy scheme   with total subsidy s for any s>s^* such that the system functions in any NE. Moreover, a total subsidy of at least s^* is necessary for any subsidy scheme   that guarantees that the system functions in any NE.

    






















































    (Sufficiency of s^*). We do this by cases on the cost vector (C_1,C_2), as follows.

    
        
  Case 0:  (C_1,C_2) lies in the interior of R. In this case it is easy to see that PoA=1 and s^*=0. In particular, the conditions C_1< p_1, C_2< p_2 rule out DN-RE, RE-DN as candidate equilibria respectively, and since C_1< p_1p_2 or C_2< p_2p_1,  DN-DN  cannot be a NE either (agent 1 or agent 2 will prefer to repair).
        
  Case 1: C_1≤p_1p_2, C_2≥p_2. In this case, a  subsidy more than s^*=C_2-p_2 to agent 2 is sufficient to bring the cost vector to the interior of R.
        
  Case 2:C_2≤p_2p_1, C_1≥p_1. Symmetric to C1.
        
  Case 3: p_1p_2<C_1≤p_1, p_2p_1< C_2≤p_2. A subsidy more than min_i{C_i-p_ip_3-i} to agent _i{C_i-p_ip_3-i} is sufficient to bring the cost vector to the interior of R.
        
  Case 4: Otherwise. It is straighforward to verify by direct calculation that a subsidy of s^*_1=max{C_1-p_1,0}+p_1·p_2 to agent 1 and a subsidy of s^*_2=max{C_2-p_2,0}+p_1·p_2 to agent 2 is sufficient.
    
    The necessity argument essentially follows by updating the cost matrix with conditional subsidies (s_1,s_2) and noting that the system is guaranteed to function in any NE if the costs (C_1,C_2) are in the interior of R.





In addition to expected VoI, we can also ensure posterior conditioned VoI_i,j when component c_j is inspected is non-negative for each agent i and each posterior y_j via subsidy. Compared to expected VoI, this is a more worst-case perspective as it includes the case when the component is broken which is typically when the agents are more likely to avoid the information about the component state. The following result gives the optimal value of subsidy to ensure this.


    Consider the two-agent series component inspection game with C_1,C_2>0 and 0<p_1,p_2<1. Then 
        
  (a) VoI_i,j(s_i,s^j,1)≥0 for any agents i,j, any  prior NE s_i and any posterior NE s^j,1, when the inspected component j is working, except when C_3-j=p_3-j and an arbitrarily small subsidy is sufficient to ensure VoI is non-negative in this case. 
        
  (b) Define R_1⊂^+×^+ as the set of cost pairs that satisfy (C_j≤p_j C_3-j≤p_3-jp_j)  (C_j≤p_jp_3-j). Let s^*=min_(x,y)∈ R_1||(C_1,C_2)-(x,y)||_1, where ||·||_1 denotes the L_1-norm. Then there exists a subsidy scheme   with total (unconditional)  subsidy s for any s>s^* such that VoI_i,j(s_i,s^j,0)≥0 for any agents i,j, any  prior NE s_i and any posterior NE s^j,0, when the inspected component j is broken. Moreover, a total (unconditional) subsidy of at least s^* is necessary for any subsidy scheme   that guarantees that the system functions in any NE.
    
    
    










WLOG j=1. 
    
  (a)
    If y_1=1, the only candidate posterior equilibria are DN-DN if C_2≥p_2 and DN-RE if C_2≤p_2.

    If C_2> p_2, then the prior NE is either DN-DN or RE-DN. In either case both agents have a non-negative Value of Information (Table <ref>).
If C_2< p_2, then the prior NE is either DN-DN, RE-RE or DN-RE. In each case both agents can be readily verified to have a non-negative Value of Information. If C_2=p_2 and C_1≤p_2, then VoI can be negative for agent 1 if the prior equilibrium is RE-RE and the posterior equilibrium is DN-DN. But in this case a (unconditional, or conditional on inspection) subsidy of s^*_2>0 to agent 2 ensures that DN-DN is not a posterior equilibrium and both agents have non-negative VoI. 
    
  (b) For y_1=0, we consider the following cases.
    

    
  Case 0: C_1≤p_1p_2,C_2>p_2. If C_1<p_1p_2, the only prior NE is RE-DN and the only posterior NE is also RE-DN. Thus, VoI =0 for each agent even in the absense of subsidy and s^*=0 in this case. If C_1=p_1p_2, DN-DN is also a prior NE but VoI is still non-negative for each agent, since the posterior costs
    
    cost_1(RE,DN)=C_1+p_2≤p_1p_2+p_2=p_1p_2,

    and 
    
    cost_2(RE,DN)=p_2<p_1p_2.

    
  Case 1: p_1p_2< C_1≤ p_2,C_2>p_2. DN-DN is the only prior NE and the only posterior equilibrium is RE-DN (except if C_1=p_2, when DN-DN is also a posterior NE), and 
    cost_1(RE,DN)=C_1+p_2> p_1p_2.
 A subsidy of C_1-p_1p_2 to agent 1 is sufficient to ensure VoI is non-negative for agent 1 as noted in  case C0. Alternatively, a subsidy of C_2-p_1p_2 to agent 2  ensures that RE-RE is the only prior and posterior NE, and VoI is non-negative for each agent. The smaller of the two subsidies works and is necessary in this case.

    If we require the subsidy to be conditional on inspection, DN-DN remains the only prior NE as prior costs are not updated by the subsidy. A subsidy of C_1-p_1p_2 to agent 1 works as above. In the alternative case, if we provide a smaller subsidy of C_2-p_2 to agent 2, the posterior NE is switched to RE-RE but the prior remains  DN-DN and a 
    subsidy of C_1-p_1p_2 to agent 1 is still required to ensure non-negative VoI for agent 1.
    
    
    
    
    
  Case 2: C_1>p_2,C_2>p_2. In this case the only NE is DN-DN in both prior and posterior games. The value of information is negative for both agents in the absense of subsidy as the posterior costs are 1. Subsidy schemes described in case C1 above can be verified to be optimal in this case as well.
    
  Case 3: C_1<p_1p_2,C_2=p_2. Both RE-DN and RE-RE are prior and posterior Nash equilibria, and 
    cost(RE,DN)=C_1+2p_2>C_1+p_2=C_1+C_2=cost(RE,RE).
 An arbitrarily small subsidy to agent 2 is sufficient to guarantee non-negative VoI  as RE-DN would no longer be a NE.
    
    

    

    

    
  Case 4: Otherwise. Value of Information for agent 1 is negative since either DN-DN or DN-RE is a posterior NE with cost 1, and there is a prior NE with smaller cost to agent 1. It may be verified that the subsidy scheme from Theorem <ref> is optimal in ensuring non-negative VoI in this case. 









§ OPTIMAL SUBSIDY IN TWO AGENT PARALLEL GAME


The cost matrix for a two-agent parallel game is summarized in Table <ref>. Here we consider a slight generalization where there are two agents with reparable components connected in parallel, and there are additional components connected in parallel which are not maintained by any agent. Let p_R denote the probability that remaining components work. 



 §.§ Price of Anarchy




    Consider the two-agent parallel component maintenance game with C_1,C_2>0 and 0<p_1,p_2<1. Let s^*={(C_1,C_2)∈ [0,p_R·p_1·p_2]^2}·|C_1-C_2|, where {·} denotes the 0-1 valued indicator function. Then there exists a subsidy scheme   with total subsidy s for any s>s^* such that PoA(𝕊)=1. Moreover, a total subsidy of at least s^* is necessary for any subsidy scheme  that guarantees PoA(𝕊)=1. 


 We will characterize the set of values of C_1,C_2 for which there are multiple Nash equilibria and design subsidy schemes that achieve PoA(𝕊)=1. For convenience set p^*:=p_R·p_1·p_2. We consider the following cases. 


    
  Case 0: C_1<p^*,C_2>p^*. In this case the only NE is RE-DN (Table <ref>). Thus, PoA =1 even in the absense of subsidy and s^*=0 in this case.
    
  Case 1: C_1=p^*,C_2>p^*. Both RE-DN and DN-DN are Nash equilibria, and 
    cost(RE,DN)=C_1=p^*=1/2cost(DN,DN).
 An arbitrarily small subsidy to agent 1 is sufficient to guarantee PoA(𝕊)=1 (therefore s^*=0 works) as DN-DN would no longer be a NE.
    
  Case 2: C_1>p^*,C_2>p^*. In this case the only NE is DN-DN. Thus, PoA =1 even in the absense of subsidy.
    
  Case 3: C_1<p^*,C_2=p^*. Both RE-DN and DN-RE are Nash equilibria, and 
    cost(RE,DN)=C_1+2p_2>C_1+p_2=C_1+C_2=cost(RE,RE).
 An arbitrarily small subsidy to agent 2 is sufficient to guarantee PoA(𝕊)=1 (therefore s^*=0 works)  as RE-DN would no longer be a NE.
    
  Case 4: C_1<p_1p_2,C_2<p_2. In this case the only NE is RE-RE. Thus, PoA =1 even in the absense of subsidy.
    
  Case 5: (C_1,C_2)∈ [p_1p_2,p_1]× [p_2p_1,p_2]. Both RE-RE and DN-DN are Nash equilibria, and OPT corresponds to RE-RE. A subsidy greater than C_1-p_1p_2 to agent 1, or a subsidy greater than C_2-p_2p_1 to agent 2 guarantees that the only NE is RE-RE. Further, in either case PoA(𝕊)=1 as the subsidy equals the reduction in the repair cost of the respective agent.

    Further suppose a subsidy of s^*=s^*_1+s^*_2 is sufficient to ensure PoA(𝕊)=1 in this case. Now if subsidy to agent 1 s_1^*≤ C_1-p_1p_2 and subsidy to agent 2 s_2^*≤ C_2-p_2p_1. Then both DN-DN and RE-RE are NE and PoA(𝕊)>1 since the worst-case equilibrium (i.e. DN-DN) cost does not depend on the subsidy. Therefore either s_1^*> C_1-p_1p_2 or s_2^*> C_2-p_2p_1, establishing that a subsidy of at least s^* is necessary in this case to ensure PoA(𝕊)=1.

    

    
  Case 6: Otherwise. By symmetry, the case is similar to one of  C0 through C4 with agents 1 and 2 switched. s^*=0 and price of anarchy of 1 is achieved by no or arbitrarily small subsidy as above.

Note that s^* is non-zero only in case C5, in which case we have established both sufficiency and necessity of a total subsidy of s^* to ensure PoA(𝕊)=1.
    




 §.§ Guaranteeing system functions in any NE



    Consider the two-agent parallel component maintenance game such that C_1,C_2>0 and 0<p_1,p_2<1. 
    Let s^*={(C_1,C_2)∈ [p_R·p_1·p_2,∞)^2}·(min{C_1,C_2}-p_R·p_1·p_2), where {·} denotes the 0-1 valued indicator function. Then there exists a subsidy scheme   with total subsidy s for any s>s^* such that the system functions in any NE. Moreover, a total subsidy of at least s^* is necessary for any subsidy scheme   that guarantees that the system functions in any NE.



    Note that the system does not function only in DN-DN, for which to be a NE we must have (C_1,C_2)∈ [p_R·p_1·p_2,∞)^2. Now a subsidy s^*_i>C_i-p_R·p_1·p_2 to agent i guarantees that agent i chooses repair, establishing the first part of the theorem.

    Conversely, suppose (C_1,C_2)∈ [p_R·p_1·p_2,∞)^2 and a subsidy scheme with total subsidy s^* guarantees that the system functions in any NE. But if s^*_i≤ C_i-p_R·p_1·p_2 for i∈{1,2}, then DN-DN is still an NE, and the system does not function for this NE. By contradiction, the total subsidy must be at least s^* as claimed. 
    




 §.§ Value of Information
 For this case as well, 
the Value of Information may be negative if a local equilibrium is selected for some parameter settings. In the following we will show a dichotomy—if the repair costs are small then  a central agent using subsidy must subsidize the full costs of repair to avoid negative Value of Information of component inspection for the agents. Otherwise, the central agent can partially subsidize to avoid negative VoI.





Suppose C_1,C_2∉{0,p_R·p_2,p_R·p_1·p_2}. A subsidy scheme with s_1^*>max{C_1-p_R·p_1·p_2,min{C_1,p_R·p_2}} and s_2^*>max{C_2-p_R·p_1·p_2,min{C_2,p_R·p_2}}, conditional on inspection, is sufficient to avoid negative VoI for both agents when component 1 is inspected.


Note that RE-RE cannot be an equilibrium since C_1,C_2>0. Also negative VoI is not possible when the posterior is y_1=1 as the only Nash equilibrium is DN-DN with zero cost for each agent. 

First suppose min{C_1,C_2}≥p_R·p_1·p_2. This implies DN-DN is the prior equilibrium. In this case, the conditional subsidies of s_i^*=C_i-p_R·p_1·p_2 are sufficient to ensure that posterior repair costs for each agent is less than p_R·p_1·p_2≤p_R·p_2. Thus, DN-DN cannot be a posterior NE for y_1=0. For DN-RE and RE-DN, the subsidy ensures that VoI is non-negative for both agents.




Otherwise, we have three cases to consider w.r.t. relative choice values of repair costs and failure probabilities,


    
  Case 0: C_1< p_R·p_1·p_2≤ C_2. In this case, RE-DN is the prior equilibrium. 
    Moreover, since C_1< p_R·p_1·p_2≤p_R·p_2, agent 1 would prefer action RE over DN and so DN-DN cannot be a posterior NE for y_1=0. If RE-DN is the posterior NE, then by Table <ref> clearly VoI is non-negative for both agents. So it only remains to consider the posterior equilibrium DN-RE. If C_2>p_R·p_2, DN-RE cannot be an equilibrium, and we are done. If C_2≤p_R·p_2, then the subsidy s_2^*>min{C_2, p_R·p_2} ensures that VoI of agent 2 is non-negative even if DN-RE is the posterior equilibrium.  
    
    
  Case 1: C_2< p_R·p_1·p_2≤ C_1. The argument for this case is symmetric to the previous case, with DN-RE as the only possible prior equilibrium.
    
  Case 2: max{C_1,C_2}< p_R·p_1·p_2. In this case DN-RE as well as RE-DN can be prior Nash equilibria. Since max{C_1,C_2}< p_R·p_1·p_2≤p_R·p_2, DN-RE and RE-DN are the only candidate posterior NE. The setting of subsidies s_i^*>p_R·p_2≥p_R·p_1·p_2 > max{C_1,C_2} ensures that VoI is non-negative for both agents in this case.  
    





§ FIXED PARAMETER INTRACTABILITY OF DESIGNING SUBSIDY TO MINIMIZE THE PRICE OF ANARCHY


We  strengthen our hardness results from Section <ref> here, by showing that it is unlikely that the optimal subsidy design problem is even fixed parameter tractable with the subsidy budget as the fixed parameter. Formally, a problem is fixed parameter tractable (FPT) with respect to parameter k∈^+ if there exists an algorithm running in f(k)× n^O(1) time, where f is a function of k which is independent of the input size n. The W hierarchy is a sequence of computational complexity classes which, roughly speaking, indicate fixed parameter intractability in an increasing order of conjectured hardness. A parameterized problem L is in the class W[i], if every instance 
(x,k) can be transformed in FPT time to a combinatorial circuit that has weft at most i, such that 
(x,k)∈ L if and only if there is a satisfying assignment to the inputs that assigns true to exactly k inputs. The weft is the largest number of logical units with fan-in greater than two on any path from an input to the output. Note that W[i]⊆W[j] for each i≤ j ∈_≥ 0, and the inclusion is conjectured to be strict. We refer the reader to standard texts for further details on parameterized complexity including the W hierarchy <cit.>.

Our hardness result involves reduction from the Dominating-Set problem, which is known to be W[2]-complete. Formally, the problem may be stated as follows.

Dominating-Set: Does a given (undirected, unweighted) graph =(V,E) admit a dominating set[A subset X of vertices is said to be a dominating set if for every vertex v∈ V∖ X there is an edge (x,v)∈ E for some x∈ X.] of size k?

We will show W[2]-hardness of the subsidy design problem CMG-PoAS for optimizing the Price of Anarchy, stated in Section <ref>.


    CMG-PoAS is W[2]-Hard.


We will reduce the Dominating-Set problem to CMG-PoAS.  Given an instance ,k of the Dominating-Set problem, we create a corresponding CMG-PoAS problem as follows. Introduce an agent i for every vertex  i∈ V and consider the  formula ϕ()=⋀_i∈ V(x_i⋁_(i,j)∈ E x_j), where the clauses correspond to each vertex and consist of component states x_i for that vertex and x_j for all agents corresponding to the neighbors of node i. Set the probability distribution θ to be the constant distribution with the entire probability mass on 0^n (i.e. all the components are guaranteed to fail without repair). Set repair cost C_i=1 for all components i. Then the cost function for agent i for joint action s=(s_i,s_-i) is given by-1

    l_i(s_i,s_-i,θ)=_∼θ[cost_i]=C_is_i+P_ϕ(θ)=1· s_i+1-ϕ(')=s_i+1-ϕ(s),
 where x_i'=max{0,s_i}=s_i denotes the  component state after agent i takes action s_i.

We  proceed to characterize the set of Nash equilibria of this game. Note that  s=0^n is a NE for this game, since any repair action by any agent increases the agent's cost by 1 if the repair does not change the state ϕ of the system, and by 0 otherwise (since ϕ is monotonic, ϕ(s) can only change from 0 to 1 on repair). This also implies that no agent has any incentive to switch from DN to RE. Further note that if the components corresponding to a dominating set X are have their state x_i=1, then ϕ()=1 as each clause of ϕ will have a positive literal corresponding to some node in X (either the first literal is in X or the node in V∖ X has some neighbor in X) by definition of a dominating set. Moreover, if the set of states with x_i=1 does not correspond to a dominating set, then there is some vertex v∈ V such that x_v=0 and x_u=0 for all neighbors u of v in , and ϕ()=0 in this case as the clause corresponding to v is not satisfied. We remark that the rest of the proof is very similar to the proof of Theorem <ref>, and is included below for completeness.

We will now show that the remaining NEs for the game correspond to minimal dominating sets of . 
Suppose K⊆[n] be a set of agents for which the corresponding nodes in  constitute a minimal dominating set. Let s_K'=(s_1,…,s_n) where s_i=[i∈ K'], and [·] is the 0-1 valued indicator function, denote the joint action where agents in set K'⊆[n] choose repair. Clearly,  ϕ(s_K)=1. If i∈ K, agent i does not reduce cost by switching from RE to DN since K is a minimal dominating set therefore not repairing component i causes the system to fail. As noted above, switching from DN to RE never improves an agent's cost in this game. 
Further, if K is the set of agents corresponding to a non-minimal dominating set, then there must be some agent that can reduce its cost by switching from RE to DN with system still functioning. 
Finally, if  K' ∅ is the set of agents with one or more agents short of a dominating set, then any agent in K'  can reduce its cost by switching from RE to DN. This establishes that besides 0^n, only possible NE must correspond to a minimal dominating set. In particular, this implies that =k^*, where k^* is the size of the smallest dominating set K^* of , and the corresponding NE is s_K^*. 

To complete the reduction, we consider the game defined above with subsidy budget n^*=k. We will show a bijection between the YES and NO instances of the two decision problems to complete the proof.
If there exists a dominating set of size k, then the smallest dominating set K^* has size k^*≤ k. We design a subsidy scheme with  subsidy allocated to k^*≤ n^* agents, allocating subsidy of 1+1/2n for repair (the total subsidy is no more than k^*+1/2) to all agents in the minimum cover K^*, a  and subsidy of 0 otherwise. 
As argued above, the only candidate NE without subsidy are 0^n and s_K corresponding to some minimal dominating set K. The social cost for 0^n is n (except the trivial case k^*=0) and that for s_K^* is k^* which is smaller. If we provide subsidy in our scheme  to the agents in K^* then 0^n is no longer an NE. In particular, every subsidized agent in K^* would now always choose repair at subsidized cost -1/2n over doing nothing (even when the system stays broken after the repair). Thus, the social cost plus subsidy is k^*(-1/2n)+k^*(1+1/2n)=k^*, and the price of anarchy for the subsidy scheme is 1 (any agent outside of K^* will prefer to do nothing to reduce their cost).
On the other hand, suppose that  has no dominating set of size k. Any minimal dominating set of  therefore has size at least k+1. Suppose  is a subsidy scheme with  subsidy allocated to most k agents. We will show that PoA()>1. Indeed, let K be an arbitrary minimal  dominating set of . By pigeonhole principle, at least one agent in K does not receive subsidy. Let K' denote the (possibly empty) set of agents that receive subsidy greater than 1. As argued above, these agents will always prefer the repair action. Thus, s_K' is a Nash equilibrium (agents without subsidy never have incentive to switch from DN to RE in this game) in the subsidized game. Note that ϕ(s_K')=0 since at least one vertex is missed in any minimal dominating set K, and therefore we must have an uncovered edge. 
Now ≤cost(s_K)=|K|<n. Therefore, PoA()> 1 as total cost plus subsidy is at least n for s_K'.



    


We remark that a similar stronger hardness result can be proved for the other studied objectives for subsidy design as well, i.e.  the decision problems CMG-System and CIG-VoI are also W[2]-hard, by adapting the proofs of Theorem <ref> and <ref>
along the lines of the above.



§ ADDITIONAL PROOFS FROM SECTION <REF>



Theorem <ref> (restated).
    CMG-System is NP-Hard.


We will reduce the Vertex-Cover problem to CMG-System.  Given an instance ,k of the Vertex Cover problem, we create a corresponding CMG-System problem as follows. Introduce an agent i for every vertex  i∈ V and consider the (2-CNF) formula ϕ()=⋀_(i,j)∈ E(x_i x_j), where the clauses consist of states x_i,x_j for all pairs i,j of agents/components corresponding to edges in E. Set the probability distribution θ to be the constant distribution with the entire probability mass on 0^n (i.e. all the components are guaranteed to fail without repair). Set repair cost C_i=1-ϵ for 0<ϵ<1/n for all components i.

Observe that, 

    l_i(s_i,s_-i,θ)   =_∼θ[cost_i]
       =C_is_i+P_ϕ(θ)
       =(1-ϵ)s_i+1-ϕ(')
       =(1-ϵ)s_i+1-ϕ(s),
 where x_i'=max{0,s_i}=s_i denotes the state of component i after agent i takes action s_i. Note that WLOG s=0^n is a NE for this game, since any repair action by any agent increases the agent's cost by (1-ϵ) if the repair does not change the state ϕ of the system, and 0 otherwise (since ϕ is monotonic, it can only change from 0 to 1). We will now show that the remaining NEs for the game correspond to vertex covers of . 

Suppose K⊆[n] be a set of agents for which the corresponding nodes in  constitute a minimal vertex cover. Let s_K'=(s_1,…,s_n) where s_i=[i∈ K'], where [·] is the 0-1 valued indicator function and K'⊂ K with |K'|=|K|-1. Similarly, s_K:=(s_1,…,s_n) where s_i=[i∈ K]. Clearly, ϕ(s_K')=0 and ϕ(s_K)=1. If i∈ K, agent i does not reduce cost by switching from RE to DN since K is a minimal cover therefore not repairing component i causes the system to fail. If j∉ K, agent j does not reduce cost by switching from DN to RE as the system was already functioning. Further, if K is the set of agents corresponding to a non-minimal vertex cover, then there must be some agent that can reduce its cost by switching from RE to DN. 
Finally, if  K' ∅ is the set of agents with one or more agents short of a vertex cover, then any agent in K'  can reduce its cost by switching from RE to DN. This establishes that besides 0^n, only possible NE must correspond to a minimal vertex cover. 

To complete the reduction, we consider the game defined above and subsidy budget s^*=k-1. If there exists a vertex cover of size k, then a minimal cover K' has size k'≤ k. We design a subsidy scheme with total subsidy s'=k'-1≤ s^*, allocating subsidy of 1 for repair to all but one agent in the minimal cover K' and subsidy of 0 otherwise. Clearly the only agent not given subsidy will choose repair since cost of repair 1-ϵ is more than compensated by the change due to system state. As argued above, the only candidate NE are 0^n and s_K corresponding to some minimal vertex cover K. Without the subsidy, the social cost for 0^n is n (except the trivial case k=0) and that for s_K' is k'(1-ϵ) which is smaller. If we provide subsidy in our scheme  to the agents in K' except one then 0^n is no longer an NE. In particular, every subsidized agent in K' would now choose repair at cost 1-ϵ over doing nothing (even when the system stays broken after the repair) and the remaining agent in K' will choose repair if the system is broken. Thus, the system functions in all NEs.


Conversely, suppose there exists a subsidy scheme  with total subsidy at most s^*=k-1, such that the system functions in any  NE. Then either the system functions in 0^n and there is a 0-cover for graph , or the  NE corresponds to a minimal vertex-cover K' of size k' as the repaired components (in the subsidized game). In the latter case, we seek to show k'≤ k to complete the proof. Since the system is not assumed to function for s=s_κ for repair actions by agents in any κ⊂ K' with κ=k'-1, we
need to provide subsidy at least 1-ϵ to all but one agent in K'. That is, k-1=s^*≥ (1-ϵ)(k'-1)>k'-1-(k'-1)/n (since ϵ<1/n), or  k≥ k' since both k,k' are integers.



Theorem <ref> (restated). 
    CIG-VoI is NP-Hard.


We will reduce Vertex-Cover to CIG-VoI. Recall that  Vertex-Cover is the following decision problem—given a graph =(V,E) and integer k, does there exist a vertex cover of size k? 

In  contrast to proof of Theorem <ref>, we will need to set a slightly higher subsidy and carefully adapt the argument to the value of information computation. 

We will create an instance of the CIG-VoI problem with n=|V|+1 agents, an agent each for vertices in  and an additional agent j=|V|+1. The construction of the instance and several arguments are similar to the proof of Theorem <ref>. The key difference is that we have an additional agent j that does not correspond to a vertex in . We will consider the inspection of the component c_j corresponding to this agent.  


Consider the (2-CNF) formula ϕ()=⋀_(u,v)∈ E(x_u x_v), where the clauses consist of states x_u,x_v for all pairs u,v of agents/components corresponding to edges in E. Set the probability distribution θ to be the constant distribution with the entire probability mass on 0^n (i.e. all the components are guaranteed to fail without repair). Set repair cost C_i=1-ϵ for 0<ϵ<1/n for all components i∈[|V|] and C_j=1. 
Therefore, 
l_i(s_i,s_-i,θ)=(1-ϵ)s_i+1-ϕ(s) for i∈[|V|] and l_j(s_j,s_-j,θ)=2-ϕ(s). Note that WLOG s=0^n is a NE for this game, since any repair action by any agent increases the agent's cost by (1-ϵ) if the repair does not change the state ϕ of the system, and 0 otherwise (since ϕ is monotonic, it can only change from 0 to 1). As shown in the proof of Theorem <ref>, the remaining NEs for the game correspond to minimal vertex covers of . Moreover, since ϕ(s) does not depend on s_j by definition, agent j will always prefer action DN for any s_-j. Let s_K:=(s_1,…,s_n) where s_i=[i∈ K] for any K⊆ V.

Notice that the prior and posterior games (for inspection of c_j) have identical cost matrices and equilibria for this component inspection game. To complete the reduction, we consider the game defined above and subsidy budget s^*=k. Suppose there exists a vertex cover of  of size k, then there exists a minimal vertex cover, say K' of size k'≤ k. We design a subsidy scheme with total subsidy s'=k'≤ s^*, allocating subsidy of 1 for repair to exactly the agents in K'. Clearly, all subsidized agents will always choose repair. We claim that the only NE after subsidy is s_K'. Indeed, by the above observation, any NE must be s_K for some K⊇ K'. But if K K', then any agent in K∖ K' will choose to do nothing as the system would function without their repair action. Since there is exactly one NE in prior and posterior games, Value of Information is exactly zero for all agents. 

Conversely, if there is no vertex cover of size k, then we show that no subsidy scheme with s^*≤ k may guarantee that no agent has negative value of information when a single component j is inspected. In this case the any vertex cover K' has |K'|>k. We consider two cases:

    
  Case 0: |K'|>k+1. Observe that if the subsidy provided to an agent is less than the repair cost 1-ϵ, then the agent will prefer to do nothing, except when repairing their component (given other players actions) changes the system state from 0 to 1. However, with a budget of s^*=k, the maximum number of agents that can receive a subsidy of at least 1-ϵ is at most k/1-ϵ<k+1, since ϵ<1/n and k<n WLOG. Thus, at least two agents are without subsidy at least 1-ϵ in K', and these agents will prefer to do nothing if only the agents K^*={i∈[|V|]| s^*_i>1-ϵ} with sufficient subsidy choose repair. Observe that both s_K' and s_K^* are Nash equilibria in the subsidized game. If s_K' is chosen as the prior equilibrium and s_K^* a posterior equilibrium, then the value of information for agents in K'∖ K^* is (1-ϵ)-1<0 since the system does not work in s_K^*.
    
  Case 1: |K'|=k+1. In this case, the only new possibility is if at least 1-ϵ subsidy is provided to all but one agent (say k') in K', then the remaining agent will choose repair. Without loss of generality, we assume k+1<n, and that K' is a minimal vertex cover. Now if v_k' denotes the vertex corresponding to agent k' in , and let E' denote the set of edges incident on vertices  V'⊆ V∖ K' with one end at v_k'. E' is non-empty, as otherwise K'∖{v_K'} would constitute a vertex cover for  contradicting minimality of K'. Observe that K_1=K'∖{v_K'}∪ V' is a vertex cover. Let K_2 denote a minimal vertex cover which is a subset of K_1. Now both s_K_2 and s_K' are NEs in the subsidized game. If the former is set as the prior equilibrium, and the latter a posterior equilibrium then, the value of information is negative (equals 0-(1-ϵ)=ϵ-1) for agent k'. 












Thus in either case, some agent has a negative value of information when the subsidy budget is k. This completes the reduction.



Theorem <ref> (restated). 
    CSG-VoI is NP-Hard.




Recall the minimum subset cover problem instance (,,k) is given as follows.


Min-Set-Cover: Given a finite set  of size n and a collection ⊆2^ of subsets of , does there exist a subset S of  of size k<n that covers , i.e. ∪_S_i∈ SS_i=?

Consider the cost-sharing game G with n+1 agents that correspond to elements of  via a bijection ζ:→[n] plus additional agent n+1, set of actions =⊎⊎⊎{{n+1}} with ={{1},…,{n}} and ={{1,…,n}} being two distinct collections of actions available uniquely to each agent and {n+1} corresponds to a unique action a_n+1 available to agent n+1. Function f:S↦{ζ(s)| s∈ S}  assigns action S to agents corresponding its elements, and cost function c is given by


    c(S)=
            1     if S∈⊎,
    
            n-ϵ    if S∈,
    ∞    if S={n+1},

for 0<ϵ<1. 
We set s^*=k.

Given a YES instance of Min-Set-Cover, we show that the above contruction yields a YES instance of CSG-VoI. Let k^* denote the size of the smallest set cover of (,). In the YES instance this means k^*≤ k, and we provide subsidy of value 1 to all actions corresponding the sets in the smallest set cover. The total subsidy used is k^*≤ k=s^*.  Any assignment of the actions to agents consistent with the set cover is a Nash Equilibrium with social cost 0 and, any other state is not an NE as in the proof of Theorem <ref>. Revealing the cost of action a_n+1 does not impact the choices of agents {1,…,n} as the action is not available to them, and agent n+1 either since the only available action is a_n+1. Thus, the cost of any agent in [n] is 0 in any prior or posterior equilibria and the value of information is zero. The cost of agent n+1 can only decrease when it is revealed, and therefore VoI is non-negative for agent n+1 as well.





Conversely, consider a NO instance of Min-Set-Cover. The smallest set cover of (,) has size k^*>k. Consider any subsidy scheme  assigning subsidy of value 1 to at most k actions. All the agents that have at least one of their actions subsidized will select a subsidized action in any NE. Since the smallest set cover has size greater than k, there exists at least one agent  with no subsidized action. Let A⊂[n] denote the set of these agents. We will show the existence of two Nash equilibria with different  costs for some agent in A, implying that VoI<0 for that agent by selecting the higher cost NE as the posterior equilibrium and the lower cost NE for the prior. Consider states s_ and s_ for which agents in A are assigned the corresponding actions from  and  respectively, and agents in [n]∖ A are assigned one of the subsidized actions in either case. We have for any agent i∈ A, cost_i(s_)=1 but cost_i(s_)=n-ϵ/|A|cost_i(s_).





§ ADDITIONAL PROOFS FROM SECTION <REF>


We include below  proof details for missing proofs for our sample complexity and online learning results.



 §.§ Sample complexity results


Theorem <ref> (restated). 
For any ϵ,δ>0 and any distribution  over component maintenance games with n agents, O(n^2H^2/ϵ^2(n^2+log1/δ)) samples of the component maintenance game drawn from  are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the best vector of subsidies over the sample σ̂^̂*̂ has expected loss L_prior that is at most ϵ larger than the expected loss of the best vector of subsidies over .


Consider any fixed game G. Given any joint action s=(s_i,s_-i), an agent i's decision for switching their action from s_i to s_i:=1-s_i is determined by the inequality  (C_i-σ^*_i)s_i+1-Φ(s_i,s_-i')≤ (C_i-σ^*_i)(s_i)+1-Φ(s_i,s_-i'), where Φ(s):=_θ[ϕ('(s))], which is linear in σ_i^*, the subsidy provided to agent i. Thus, for each agent i, we have at most 2^n-1 axis-parallel hyperplanes in the parameter space in ^n, or a total of n2^n-1 hyperplanes overall. Moreover, the loss function as a function of the subsidy parameters is piecewise constant in any fixed piece. Therefore the loss function class is (n,n2^n-1)-delineable in the sense of <cit.>, that is the subsidy parameter space is Euclidean in n dimensions and is partitioned by at most n2^n-1 hyperplanes into regions where the loss is linear (in this case constant) in the parameters.better bound?





By using a general result from <cit.> which states add stmt to appendix? that a (d,t)-delineable function class has pseudo-dimension O(dlog(dt)), the above structural argument implies that the pseudo-dimension of the loss function class parameterized by the subsidy value is at most O(nlog(n^22^n-1))=O(n^2) and the sample complexity result follows <cit.>.





Theorem <ref> (restated). 
Suppose subs_i(s), C_i≤ H for each i∈[n]. For any ϵ,δ>0 and any distribution  over component maintenance games with n agents, O(n^2H^2/ϵ^2(n^2+log1/δ)) samples of the game drawn from  are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the best vector of subsidies over the sample σ̂^̂*̂ has expected loss L̃_prior that is at most ϵ larger than the expected loss L̃_prior of the best vector of subsidies over .



Our proof of Theorem <ref> above establish a piecewise constant structure for  the L_prior loss given any fixed game G and a bound on the number of hyperplanes in the subsidy parameter space that demarcate the pieces. On a fixed side of each of these n2^n-1 hyperplanes, each agent i has a fixed preferred action given any s_-i, and therefore the set _NE() of Nash equilibria is fixed over any piece. Indeed any joint action s is a NE given subsidy scheme  if and only if s_i is preferred given s_-i for all agents i. Thus, L̃_prior is also piecewise constant over the pieces induced by the same hyperplanes. Therefore, the same upper bound on the sample complexity can be obtained following the arguments in the proof of Theorem <ref>.




Learning conditional subsidies. We will now obtain a sample complexity bound for  non-uniform subsidy schemes in component inspection games, where the central agent provides subsidy only in posterior games. Let  denote the subsidy scheme. Let _NE^0(𝕊) (resp. _NE^1(𝕊)) denote the subset of states in S corresponding to Nash equilibria when the cost for agent i is the subsidized cost cost_i^,0 (resp. cost_i^,1) for posterior y_j=0 (resp. y_j=1). For component inspection game of component c_1 (wlog), define 


    L_posterior():=  p_1L_posterior^1()+p_1L_posterior^0(),



where L_posterior^i():=max_s∈_NE^i()cost^,i(s)+subs^i(s). We assume that subs_i^j(s)≤ H, C_i≤ H for each i∈[n], j∈{0,1}, thus  L_posterior()≤ (2H+1)n. In this case too, we are able to give a polynomial sample complexity for the number of games needed to learn a good value of subsidy with high probability over the draw of game samples coming from some fixed but unknown distribution.


For any ϵ,δ>0 and any distribution  over component inspection games with n agents, O(n^2H^2/ϵ^2(n^2+log1/δ)) samples of the component inspection game drawn from  are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the best vector of subsidies over the sample σ̂^̂*̂ has expected loss L_posterior that is at most ϵ larger than the expected loss of the best vector of subsidies over .






Consider any fixed game G. Given any joint action s=(s_i,s_-i), an agent i's decision for switching their action from s_i to s_i:=1-s_i in posterior game y_1=y is determined by the inequality  (C_i-s^y_i)s_i+1-Φ(s_i,s_-i')≤ (C_i-s^y_i)(s_i)+1-Φ(s_i,s_-i') (with  Φ(s):=_θ^1,y[ϕ('(s))]), which is linear in s_i^y, the subsidy provided to agent i conditional on y_1=y. Thus, for each agent i, we have at most 2· 2^n-1 axis-parallel hyperplanes in the parameter space in ^2n, or a total of n2^n hyperplanes overall. Moreover, the loss function as a function of the parameters is piecewise constant in any fixed piece. Therefore the loss function class is (2n,n2^n)-delineable in the sense of <cit.>. The rest of the argument is similar to the proof of Theorem <ref>, differing only in some multiplicative constants.






Theorem <ref> (restated). For any ϵ,δ>0 and any distribution  over fair cost sharing games with N agents and || actions, O(||^2H^2/ϵ^2(||log ||N+log1/δ)) samples of the game drawn from  are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the best vector of subsidies over the sample σ̂^̂*̂ has expected loss L_prior that is at most ϵ larger than the expected loss of the best vector of subsidies over .



    Consider any fixed game G. Given any joint action s=(s_i,s_-i), an agent i's decision for switching their action from s_i to s_i s_i is given as follows.

    
    
        
        Let k=∑_j=1^N[s_j=s_i] and k=∑_j=1^N[s_j=s_i]. Clearly, k≥ 1 and k≥ 0. Agent i's decision to switch from action s_i to s_i is governed by the inequality
        
    c(s_i)-c^(s_i)/k≶c(s_i)-c^(s_i)/k+1.

    

    Thus, across all agents, we get at most ||^2N^2 distinct hyperplanes in the subsidy parameter space corresponding to c^, corresponding to choices for s_i,s_i,k,k.
    Moreover, the loss function as a function of the subsidy parameters is piecewise constant, since in any fixed piece induced by the above hyperplanes the set of NEs is fixed and the reduction in social cost cost^(s) is exactly compensated by the increase in subsidy subs(s) as the subsidy is varied within the piece. Therefore the loss function class is (||,||^2N^2)-delineable in the sense of <cit.>, that is the subsidy parameter space is Euclidean in || dimensions and is partitioned by at most ||^2N^2 hyperplanes into regions where the loss is linear (in this case constant) in the parameters.

    By using a general result from <cit.> which states  that a (d,t)-delineable function class has pseudo-dimension O(dlog(dt)), the above structural argument implies that the pseudo-dimension of the loss function class parameterized by the subsidy value is at most O(||log(||^3N^2))=O(||log(||N)) and the sample complexity result follows <cit.>.


Theorem <ref> (restated). 
For any ϵ,δ>0 and any distribution  over fair cost sharing games with N agents and || actions, O(||^2H^2/ϵ^2(||log ||N+log1/δ)) samples of the game drawn from  are sufficient to ensure that with probability at least 1-δ over the draw of the samples, the best vector of subsidies over the sample σ̂^̂*̂ has expected loss L_VoI that is at most ϵ larger than the expected loss of the best vector of subsidies over .


    The key arguments are similar to the proof of Theorem <ref>. We can show that the loss function class as a function of the subsidy is (||,2||^2N^2)-delineable and the result follows.





 §.§ Online subsidy design


A key tool is the following theorem due to <cit.>. We present a simplified version (setting M=1 in their general result) as it will suffice for us.

  Let ⊂^d be contained in a ball of radius R and l_1,  … , l_T: → [0, H] be piecewise ℓ-Lipschitz
functions that are 1/2-dispersed. Then there is an online learning algorithm with regret bound Õ(√(dT)+K_T), where  the soft-O notation suppresses terms in R,H and logarithmic terms, provided 
    [
    max_ρ,ρ'∈
    ||ρ-ρ'||_2≤1/√(T)|{ t∈[T] | |l_t(ρ)-l_t(ρ')|>ℓ||ρ-ρ'||_2}|]
    ≤  K_T.



Thus, it is sufficient to establish 1/2-dispersion of the sequence of loss functions, and provide a bound on the expected number of non-Lipschitz losses between worst-case pair of points in the domain, in order to establish our results in Section <ref>.

Theorem <ref> (restated). 
Suppose Assumption <ref> holds. Let L_1,…, L_T:[0,H]→[0,(2H+1)N] denote an independent sequence of losses as a function of the subsidy value σ, in an online sequence of T component maintenance games. 
Then sequence of functions is 1/2-dispersed and there is an online algorithm with O(√(nT)) expected regret.





    The key idea is to observe that each loss function L_t has  at most K=n2^n-1 discontinuities (as in proof of Theorem <ref> above). Further, any interval of length ϵ has at most O(κϵ)  discontinuities in that interval for any fixed loss function L_t, in expectation. This uses Assumption <ref>, and the observation that critical values of σ^* are linear in some cost C_i. Indeed, as shown in the proof of Theorem <ref>, the critical values of subsidy are given by σ^*=C_i+_θϕ(0,s_-i')-_θϕ(1,s_-i') for some agent i and joint action s_-i'.
    By Theorem 7 of <cit.> then the expected number of non-Lipschitz losses on the worst interval of length ϵ is at most K_T= Õ(Tϵ+√(Tlog(TK)))=Õ(√((n+log T)T)) for ϵ≥1/√(T).
    
    This implies 1/2-dispersion of the sequence of loss functions in the sense of Definition <ref>. 
    Now Theorem <ref> implies the desired regret bound. 



Theorem <ref> (restated). 
Suppose Assumption <ref> holds. Let L_1,…, L_T:[0,H]^n→[0,(2H+1)N] denote an independent sequence of losses L_prior() as a function of the  subsidy scheme  parameterized by subsidy values {σ_i}, in an online sequence of T component maintenance games. 
Then the sequence of functions is 1/2-dispersed and there is an online algorithm with O(√(nT)) expected regret.




    Each loss function L_t can be partitioned by at most K=n2^n-1 axis-parallel hyperplanes into pieces such that the loss function is constant over each piece (as in proof of Theorem <ref> above). Further, the offset of each of these hyperplanes is linear in some cost C_i and therefore along any σ^*_i-aligned line segment of length at most ϵ, there are at most O(κϵT)  functions that are non-Lipschitz on that segment, in expectation.
    Now for any pair of subsidy vectors σ,σ' such that ||σ-σ'||_2≤1/√(T), we can bound the expected number of non-Lipschitz functions for which |L_t(σ)-L_t(σ')|>0 by taking an axis aligned path connecting σ,σ' and adding up the number of non-Lipschitz functions along each segment. Suppose the segment lengths are ϵ_1,…,ϵ_n, then the above argument gives a bound O(κ T ∑_iϵ_i) on the expected number of non-Lipschitz functions. By Cauchy-Schwarz inequality, we have  ∑_iϵ_i≤√(n)√(∑_iϵ_i^2)≤√(n/T), and the bound simplifies to O(κ√(nT)).
    
    
    
    By Theorem 4 of <cit.>  the expected number of non-Lipschitz losses on the worst point-pair with separation 1/√(T) is at most K_T= O(κ√(nT)+√(Tlog(TK)))=Õ(√(nT)).
    
     Theorem <ref> now implies the claimed regret bound. 



