# fair_individually_rational_and_cheap_adjustment__eb6481a8.pdf

Fair, Individually Rational and Cheap Adjustment

Gleb Polevoy1 , Marcin Dziubi nski2

1Paderborn University 2University of Warsaw gpolevoy@mail.uni-paderborn.de, m.dziubinski@mimuw.edu.pl

Consider the practical goal of making a desired action profile played, when the planner can only change the payoffs, bound by stringent constraints. Applications include motivating people to choose the closest school, the closest subway station, or to coordinate on a communication protocol or an investment strategy. Employing subsidies and tolls, we adjust the game so that choosing this predefined action profile becomes strictly dominant. Inspired mainly by the work of Monderer and Tennenholtz, where the promised subsidies do not materialise in the not played profiles, we provide a fair and individually rational game adjustment, such that the total outside investments sum up to zero at any profile, thereby facilitating easy and frequent usage of our adjustment without bearing costs, even if some players behave unexpectedly. The resultant action profile itself needs no adjustment. Importantly, we also prove that our adjustment minimises the general transfer among all such adjustments, counting the total subsidising and taxation.

1 Introduction It is often important to motivate the players play a desired action profile. For example, in prisoner s dilemma or the tragedy of commons [Hardin, 1968], the strictly dominant behaviour is the opposite to the social good, thus pursuing own interests can bring upon a general failure. These games model crucial issues, important for environmental protection, encouraging benevolence, and opposing political oppression, so adjusting the interaction to make the socially beneficial behaviour strictly dominant would be immensely useful. In general, we consider rendering the preferred (for whatever reason) profile strictly dominant, for any private values of the players. Strict dominance means the profile is always strictly preferable to each agent, regardless of what the others do. Thus, in the rare case when such a profile exists, it is unique and any rational agent who wants to maximise her own utility should act according to that profile, regardless of the others preferences and actions. One natural approach employs subsidies and tolls to make the desired profile strictly dominant. This can motivate peo-

ple to choose the closest school to their home, to optimally use the public transportation, to coordinate on a certain side to drive, on a communication language or a protocol, etc. For example, constructing a socially best network can be motivated by subsidising some links, as described in [Augustine et al., 2015]. [Varakantham et al., 2013] approximate the desired outcomes described in an aggregate level (say, at most so many agents use a certain resource), where the edge subsidies are bounded by a budget. [Buchbinder et al., 2008] consider taxing the users to subsidise certain services, so as to eventually optimise the social welfare. In the works by [Buchbinder et al., 2008], [Varakantham et al., 2013] and [Augustine et al., 2015], any subsidy is allowed, up to a budget; but the applicability of these approaches would increase from restricting themselves to fair and individually rational schemes. The latter means that each player can only benefit from participating in the suggested changes. [Monderer and Tennenholtz, 2004] subsidise certain outcomes to make a certain profile hold in non-dominated strategies, such that that profile itself requires little, perhaps even zero, subsidising. Inspired by that approach, we additionally require fairness, individual rationality, and that the social planner never pays anything. We also strengthen the predictive power of the claim that the desired strategy profile will be played by making it strictly dominant; thus, any rational player should always play that, regardless of the others. All the presented approaches are useful, but the need for a budget for the subsidies hinders frequent applications. We solve this issue by constraining the subsidies to sum up to zero, not only at the non-dominated profiles, but everywhere. The game model is pre-Bayesian, each players being aware solely of her own values and forming no beliefs about others values, while the planner may know either everyone s values or only their distributions. Consider the following application examples.

Example 1 (School enrollment). Consider people registering their children to schools. Assuming the preferences of the people are determined by the location of the school, its teaching level and overall prestige, the preferences can be well estimated by the planner (the municipality). The municipality prefers to have people register their children to the closest school to their dwelling place, so that the burden on the transportation system and the environment is minimised. The law forbids coercing a school choice, but the municipality may motivate the registration of each student to the

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

closest school by tolls and subsidies or promises of free tutoring. Legal and social considerations require the bonuses to be fair, and no person should be expected to lose from the whole scheme. Budget considerations require that even if some people do not respond to the motivating actions as expected, the municipality should never have to invest extra costs, so the provided bonuses and subsidies should equal the levied tolls. It would be especially nice, if in case all the players do behave as expected, then no tolls or subsidies will need to be administered. Actually, this stems from fairness and the constraint that in any case, the total subsidies equal the total tolls.

Example 2 (Preventing import). Climate considerations suggest motivating restaurants and canteens consume local food can help in protecting the environment [Ivanova et al., 2020]. The preferences of each restaurant depend on the economical situation, such as food prices and transportation costs, and on the local preferences, which can be estimated. While adjusting the situation, legal and ethical consideration require fairness, it is useful to guarantee no restaurant will lose, and the budget constraints require the planner will never pay, while if the restaurants behave as expected, then neither taxes nor subsidies will apply.

In the above examples, the planner has complete information about the players utilities. The planner can be assumed to avail of complete information also when others objectives are possible to estimate values, such as wholesale purchases of raw material, anonymous hiring (excluding personal sentiments) and selecting saving or investment schemes by organisations with known policies. However, in some cases the planner lacks some information, such as in the next example and in situations like choosing collaborators, roommates, non-anonymous hiring, saving investments schemes by people or organisations with unknown policies, choosing holiday destinations, journal and gym subscriptions.

Example 3 (Subway stations). Consider commuters to a regular location. People often use the subway in combination with other means of transportation, such as trams of private cars. The best route for a given person depends on factors like weather, petrol prices, personal circumstances on a given day and personal taste. Some of these, such as personal circumstances and taste, can vary with time, unbeknownst to the planner (the municipality). For the sake of the transportation system and the environment, the municipality would like each person to board the subway at the station closest to her home and leave the subway at the station closest to her job. Unlike the other preferences, the locations of the residents home and their jobs are typically known to the municipality and remain constant for long periods of time. Each resident is aware solely of her own circumstances. Obviously, coercion is neither possible nor allowed, but the municipality may try to motivate the inhabitants to behave as described by monetary tolls and subsidies, even though it is oblivious to their exact preferences. Law and common sense demand that such a scheme be fair, and since no person may be coerced to participate in it, this scheme should be individually rational as well. We also want to keep the total tolls equal to the total subsidies in any case, so that no costs

are ever born by the city. Finally, we prefer to have no tolls or subsidies in the case where all the people behave as expected. In cases where we may not change the strategies, we make the desired profile strictly dominant by subsidies and tolls, while being fair, namely exercising equal treatment, making participation individually rational, and never requiring any costs from the planner, thereby facilitating frequent use of such adjustments. Individual rationality renders the (anyway costly and perhaps even immoral or illegal) coercion to participate irrelevant. Similarly to [Monderer and Tennenholtz, 2004] and unlike mechanism design, our planner adjusts only the payoffs, leaving the strategy sets and the outcome as they are, assuming the players value money quasi-linearly. The planner never asks for private values and knows in advance which action profile she wants to be played, regardless of her knowledge about the players preferences. Furthermore, unlike using a mediator in [Monderer and Tennenholtz, 2009], where the strategies of messaging the mediator are introduced, and the mediator acts based on the whole set of messages it receives, we only adjust the utilities. We thus assume the knowledge of the payoffs, but we also achieve an adjustment that is implementable, fair and individually rational, which is provably impossible to achieve when having to elicit the private information beforehand. This constellation of properties is useful theoretically and practically, in the above scenarios. Our adjustment also minimises the general transfer among such adjustments. For pre-Bayesian games, we still make the desired fixed strategy strictly dominant (with a certain probability), unlike [Monderer and Tennenholtz, 2004], who do not constraint themselves to fixed strategies, and then they prove that in general, no implementation is possible. We present the relevant literature in the next paragraph. Then, we provide the definitions in Section 2, following by a suggestion of an adjustment in Section 3, assuming the planner knows the players utilities. For ease of presentation, we model complete information in that section. This adjustment is fair, individually rational and always costs nothing to the planner. Interestingly, the payoffs in the resulting strictly dominant profile are not adjusted. In Section 4, we present what the planner that lacks knowledge about the players utilities can do. In Section 5, we describe the impossibility of eliciting the original payoffs from the players by a mechanism design-like approach, before adjusting the game; we finish by considering the usage of our results. Due to space constraints, we omit several proofs, the construction of an adjustment for infinite games, and the generalisations for n players.

1.1 Related Work In many practical scenarios, we need to motivate the players to play a certain action profile. This may be useful in interactions with positive externalities, such as adopting new standards [Chalker et al., 2009] or organisational and legal practices (see [Dybvig and Spatt, 1983]), such as international taxation [Radaelli, 1998]. [Mc Adams, 2009] presents many applications of the classical stag-hunt and the battle of sexes games, including investment banking and bargaining with prisoners. He also considers the hawk-dove game, which can model conflicts in prosecutorial bargaining. [Clemons

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

and Row, 1993] mention situations with negative externalities that could use adjustment, such as pollution and noncooperative behavior. Unlike the famous mechanism design [Nisan et al., 2007, Chapter 9] and implementation theory [Jackson, 2001], where the unknown preferences determine the desired outcome, our planner knows the desired outcome in advance, and the problem is steering the players there, like in [Monderer and Tennenholtz, 2004; Eidenbenz et al., 2007]. [Deng et al., 2016] study the hardness of the k-implementation in the sense of [Monderer and Tennenholtz, 2004] and provide an approximation algorithm. Similarly to 0-implementation [Monderer and Tennenholtz, 2004], the government can insure the adopters against a lower adoption level, insurance that is never expected to be claimed, as suggested by [Dybvig and Spatt, 1983]. Dybvig and Spatt need to know the distribution of the costs, rather than the exact costs, for their approach. Many works, such as [Buchbinder et al., 2008], study improving performance, that is the price of anarchy, rather than attaining a predefined profile like we do. [Caragiannis et al., 2010] improves the performance of linear congestion games. Unlike our work, they also constrain themselves to tolls only and achieve partial results. Similarly, improving efficiency through tolls appears in [Fleischer et al., 2004; Cole et al., 2003]. [Cole et al., 2006] also study improving equilibrium efficiency using taxes and also compare the effect of taxes with that of edge removal. [Swamy, 2007] considers both tolls and controlling a part of the flow as means to increase efficiency. Controlling some flow is called Stackelberg strategies, and analysed for example in [Korilis et al., 1997] for routing and in [Roughgarden, 2001] for scheduling. Another way to improve the price of anarchy is coordination mechanisms, which are scheduling policies that give rise to games with efficient equilibria. For example, [Caragiannis, 2012] studies coordination of scheduling, and [Christodoulou et al., 2012] consider coordination of routing. When no planner exists, but costless enforcement does, [Jackson and Wilkie, 2005] study when some side contracting can increase the efficiency of equilibria, assuming players know each other s payoffs and commit themselves to the payments before the game commences. [Levit et al., 2019] employ tolls or subsidies to create Nash equilibria in Boolean games, but they convert some (efficient) profile to an equilibrium, rather than making a predefined profile become an equilibrium.

Given players N = {1, . . . , n}, consider a pre-Bayesian game N, (Ai)i N, (Pi)i N, (ui)i N , where for each player i N, Ai is her action set and Pi = RA is her type set, containing i s payoff matrices. Let A = Q

i N Ai be the set

of action profiles and P = Q

i N Pi be the set of type profiles or the states of the world. Player i s utility is a function ui : A Pi R, defined as ui(a, pi) = pi(a). Player i s strategy si Si is a function si : Pi Ai, and the set of strategy profiles is S = Q i N Si. In other words, a player decides on her action based only on her own type matrix,

her utility being the corresponding entry in her type matrix. Given a strategy profile, s S, and a state of the world, p P, player i s utility is ui(s(p), pi) = pi(s(p)), where s(p) = (s1(p1), . . . , sn(pn)). We call such a game finite if |A| < . The infinity of P is immaterial for this definition. The paper concentrates on finite games, to conserve space. We now define the main solution concept of this paper. Definition 1. For any player i, strategy si Si is strictly dominant if playing that is strictly preferable to i for all payoffs pi Pi, regardless of how the others act, namely i N, pi Pi, a i A i, ai Ai \ {si(pi)} , ui(si(pi), a i, pi) > ui(ai, a i, pi). Since pi is the payoff matrix, this condition simply means pi(si(pi), a i) > pi(ai, a i). A player may have 1 or no strictly dominant strategies in a game. Since it is always strictly better for i to follow si, we assume that every player plays a strictly dominant strategy if she has one. Moreover, preferring si requires no knowledge about the utilities of the others on i s behalf. When we discuss incomplete information, planner s lack of knowledge will be crucial, but the players are never assumed to know the others utilities, befitting the pre-Bayesian approach. We will be interested in strategies that always yield the same action, modelling a practically preferable behaviour, such as enrolling to the closest school or entering the subway station that is the most proximate to work. Formally, Definition 2. Strategy si Si of player i is called fixed if ai A such that si(pi) ai, pi Pi. Naturally abusing notation, we call profile s S is strictly dominant if for any player i N, strategy si is strictly dominant. We call profile s S fixed if for any player i N, strategy si is fixed. The holy grail of this paper is the following. Given a game and any action profile a A, adjust the game to (ui+vi)i N, so that the fixed strategy si(pi) ai, pi Pi becomes strictly dominant for any player i N. The adjustment itself may depend on the type profile p P or on its distribution, when the planner knows it. Abusing notation, we sometimes call the fixed strategy si(pi) ai, pi Pi just ai and write s() a. In other words, we want to motivate every player to take her part in this profile, regardless of how the other players behave. The basic concept is the adjustment, being simply the side payments of any sign, added to the players. Definition 3 (Adjustment). An n-player adjustment is a (positive or not) subsidy function vector (vi)i N, vi : A R, i {1, . . . , n}. Now, given any pre-Bayesian game Γ = N, (Ai)i N, (Pi)i N, (ui)i N on n players N = {1, . . . , n}, the adjusted game (by (vi)i N) is Γ + (vi)i N = N, (Ai)i N, (Pi)i N, (ui + vi)i N , where (ui + vi)(a, pi) = ui(a, pi) + vi(a), i N, a A. We can consider an adjustment as a real matrix in RA, added to P in calculating the utility. Positive payments represent subsidies, while negative ones stand for tolls. In Example 1, an adjustment represents the tolls and subsidies, aiming to motivate registering to the closest school. We now define the properties such an adjustment should fulfill.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

Implementability. Given any k 0, we could require that the sum of the utilities of all the players is at most k, thereby ensuring the planner spends at most k. This kimplementability can be demanded for each action profile, or for the strictly dominant profile (resembling the notion of k-implementability that [Monderer and Tennenholtz, 2004] used for non-dominated profiles), or in total over all the profiles. We aim at guaranteeing no costs for the planner, regardless of whether the players behave as we expect, so that the adjustment will be widely applicable. Therefore, we require the strongest bound and additionally set the bound k = 0, strengthening the k-implementability of [Monderer and Tennenholtz, 2004]. We call this implementability. Formally, Definition 4 (Implementable). We call an adjustment (vi)i N implementable if a A, P i N vi(a) = 0. In other words, we require the multidimensional payoff adjustment matrix to be zero-sum. (Matrix M = M1 . . . Mn, Mi RA, is a zero-sum if Pn i=1 Mi(a) = 0, for any a A.) Namely, the total subsidies equal the total tolls, in any a A. Fairness. Fairness can be defined as the equality of the total payment added to each player. Another option is to concentrate on the additions in the fixed dominant strategy profile of the resulting game. The strictest approach of requiring equality of additions in every profile would force any zero-sum adjustment to be trivial, so it is not interesting here. Combining these considerations, after strengthening the second demand above to hold for any agent who plays a fixed strictly dominant strategy, regardless of the actions of the others, gives rise to the following notion. Definition 5 (Fairness). Adjustment (vi)i N of a pre Bayesian game Γ = N, (Ai)i N, (Pi)i N, (ui)i N , resulting in G + (vi)i N, is fair if 1. If |A| < + , then i, j N, P a A vi(a) = P a A vj(a), and no requirement exists for infinite A,

2. and having a strictly dominant fixed profile s() a A of (Γ + (vi)i N), vi(ai, b i) vj(ai, b i), i N, j = i, b i A i. This means that the overall adjustment is equal between the players, and when a player acts out her strategy in the fixed strictly dominant profile, she receives at least as much additional payoff as any other player does, regardless of how the others act. The first part of the definition of fairness is only a simple version of arithmetic average, used to simplify the presentation. This approach assumes that the number of actions of each player is normalised while transferring reality to the model. If this assumption does not hold, we simply replace sum by arithmetic average in the first requirement of fairness. The rest can be adapted in a straight-forward manner. Individual Rationality. Individual rationality means any player is at least as well off after the adjustment as she was before it. We could require this either in total or in the strictly dominant profiles, but not in every single profile, since that would imply no adjustment. This motivates the following. Definition 6 (General individual rationality). Adjustment of a pre-Bayesian game Γ = N, (Ai)i N, (Pi)i N, (ui)i N by (vi)i N is called individually rational if

1. if |A| < + , then i N, P a A vi(a) 0, with no requirement for an infinite A,

2. and given a strictly dominant fixed profile s() a A of (Γ + (vi)i N), vi(ai, b i) 0, i N, b i A i.

This means that the overall adjustment scheme is profitable to any player, and when a player acts according to the fixed strictly dominant profile, she is guaranteed a nonnegative additional payoff, independently of how the others act. Though requirements 1 (about sums) in the definitions of fairness and individual rationality might seem excessive when the players play as expected and insufficient if the actually played profile after the adjustment was not the strictly dominant one (say, the players behave irrationally), they are useful. Suppose we adjust the given game multiple times, while the agents play uniformly in random. Then, the 1st requirements imply the average will be fair and individually rational. This is a safety net against irrational or mistaken actions. The main point is the insistence on implementability, which protects the organisers regardless of the actual behavior at each play. For 2 players, assuming implementability, fairness becomes equivalent to individual rationality.

Proposition 1. For any implementable adjustment (vi)i N, fairness implies individual rationality. For 2 players, the two notions are equivalent.

The omitted proof manipulates the definitions.

3 Adjustments

We now design fair, individually rational and implementable adjustments to pre-Bayesian games. In this section, the planner possesses complete knowledge of the realised types. Assuming complete information in this section simplifies the definitions as follows. Consider a normal-form game N, (Ai)i N, (ui)i N , where any player i N = {1, . . . , n} has the action set Ai and her utility is ui : A R, where A = Qn i=1 Ai. Here, action and strategy coincide. An action ai of i is strictly dominant if that action is strictly preferable to i, regardless of the others actions. Formally, ui(ai, b i) > ui(a i, b i), a i Ai \ {ai} , b i A i. Slightly abusing notation, we call a A strictly dominant if ai is strictly dominant, for each i N. The notions of adjustment, implementability, fairness and individual rationality remain unchanged. We obtain the following constructive result. We consider 2 players in the body of the paper; the general case is omitted for lack of space. The adjustment is illustrated in Figure 1.

Theorem 1. For any finite normal-form game G = N, (Ai)i N, (ui)i N and any profile a A, there exists a fair, individually rational and implementable adjustment G0 = (vi)i N, such that in game G + G0 = N, (Ai)i N, (ui + vi)i N , a is strictly dominant.

Proof. We arbitrarily order the actions of each player, such that the first actions comprise the desired profile a, and denote Ai = {ai,1, . . . , ai,mi}, where mi = |Ai|. By construction, a = (ai,1)i N. We will construct a fair zero-sum adjustment matrix G0(i, j) = (vk(i, j))k N.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

I : \II : 1 : 2 : . . . k : 1 : (0 0) (δ2 δ2) (δj δj) (δk δk) 2 : ( γ2 γ2) (0 0) (0 0) (0 0) ... ( γi γi) (0 0) (0 0) (0 0) m 1 ( γm 1 γm 1) (0 0) (0 0) (0 0) m ( γm γm) (0 0) (0 0) (0 0)

Figure 1: The adjustment for 2 players: we subsidise the player who plays the desired profile and fine the unique deviator.

In the special case of m k = 1 1, define G0 = ((0, 0)). This is fair, individually rational and zero-sum. For any m + k > 2, we set all G0 to zeros, besides the first row and column. There, we define v1(1, 1) = 0, v1(1, j) = δj, j = 2, . . . , k 1, k and v1(i, k) = γi, i = 2, . . . m 1, m. To keep G0 zero-sum, define v2 v1. Set each δj 0, j 2, as a real satisfying both following conditions:

(u1 + v1)(a1,1, a2,j) > (u1 + v1)(a1,i, a2,j), i > 1, (1) (u2 + v2)(a1,1, a2,1) > (u2 + v2)(a1,1, a2,j). (2)

Set each γi R+, i 2 satisfying both conditions below:

(u2 + v2)(a1,i, a2,j) < (u2 + v2)(a1,i, a2,1), j 1, (3) (u1 + v1)(a1,1, a2,1) > (u1 + v1)(a1,i, a2,1). (4)

Finally, we require Pm i=2 γi = Pk j=2 δj for fairness. Now, in G + G0, a is strictly dominant, because conditions Eq. (1) and Eq. (4) imply (u1 + v1)(a1,1, a2,j) > (u1+v1)(a1,i, a2,j), i > 1, j, while Eq. (3) and Eq. (2) imply (u2 + v2)(a1,i, a2,j) < (u2 + v2)(a1,i, a2,1), j > 1, i. Since v1(1, j) v2(1, j), v2(i, 1) v1(i, 1) and Pm i=2 γi = Pk j=2 δj, this adjustment is fair. Indeed, the total

subsidies to player 1 is Pk j=2 δj Pm i=2 γi, whereas the total

subsidies to player 2 sum up to Pk j=2 δj + Pm i=2 γi, so the above requirement implies both sums are zero. This adjustment is implementable by construction. Finally, since v1(1, j) 0, v2(i, 1) 0 and Pm i=2 γi = Pk j=2 δj, this adjustment is also individually rational. Alternatively, this follows from Proposition 1.

3.1 Transfer Minimisation Always taxing what we pay out never requires the planner to spend money, but we still prefer to tax as little as possible, to avoid interfering with the players. Thus, we now consider minimising the sum of the payments of both signs. Formally, given adjustment (vi)i N, vi : A R, we define its general transfer as GT = P

i N |vi(a)|. This is what we strive to minimise, subject to the other requirements. We now exemplify adjustments with small and with large general transfers. First, given the game

I : \II : 1 : 2 : 1 : (0, 0) (0, 0) 2 : (0, 0) (0, 0)

we can make (1, 1) strictly dominant using the adjustment

I : \II : 1 : 2 : 1 : (0, 0) (δ, δ) 2 : ( δ, δ) (0, 0)

δ > 0. This, GT = 4δ, δ > 0. Also intuitively, just a small adjustment is needed, because a small change of utilities suffices to make the desired profile strictly dominant. On the other hand, given the Prisoner s dilemma, making the strictly dominated (Coop, Coop) become strictly dominant intuitively requires a larger intervention. Indeed, given

1 : \2 : Coop : Defect : Coop : (3, 3) (0, 5) Defect : (5, 0) (1, 1)

we can make (Coop, Coop) strictly dominant by the following adjustment, δ > 2.

I : \II : 1 : 2 : 1 : (0, 0) (δ, δ) 2 : ( δ, δ) (0, 0)

This adjustment has GT of 4δ, where the δ has to exceed 2. Intuitively, if the adjustment minimises GT, then the higher GT it accrues, the further the original game is from preferring the desired profile by all the players. For n = 2, the adjustment suggested in the proof of Theorem 1 is the minimum general transfer adjustment that fulfills the conditions of the theorem. As the set of possible general transfers is not closed, we speak of its infimum.

Theorem 2. For n = 2, the adjustment suggested in the proof of Theorem 1 has the minimum infimum of their GT among all the adjustments fulfilling the conditions of that theorem.

4 Incomplete Information

The previous section assumed every player knew only her own utility, while the planner was fully aware of all the players utilities. Since the planner knew everything, we assumed w.l.o.g. this was a complete information game, though this works for the pre-Bayesian games defined in Section 2 (not even Bayesian, to avoid assuming a commonly known prior). In this section, however, the players keep knowing only their own utilities, but the planner s knowledge ceases being complete. Thus, his adjustment options shrink. This models situations of incomplete information, such as the one in Example 3 or in [Dybvig and Spatt, 1983]. We consider various degrees of the social planner s knowledge. We still assume finiteness. We aim to implement profiles where each player takes a given action, regardless of the state of the world. For example, in Example 3, we always want to make people enter the subway at the closest station to their home and to leave at the nearest station to their destination. Their own preferences may change, but we adjust the game to always make the above mentioned behavior strictly dominant, because that is what we consider to be the best for the society. First, assume that even though the planner is unaware of the exact preferences of the players, she does know some bounds on the distributions of each player s payoffs, as follows.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

1. The planner knows the size of the support of the payoffs of each player in the game. In the subway example, that fits the situation when the planner knows the possible extent to which the payoffs of a player can vary based on factors, such as her mood and personal circumstances.

2. The planner knows the possible changes to a player s utility that the player s unilateral deviation can cause. In the subway example, this can model the planner s knowledge to which extent a person can prefer one subway station to another one in given circumstances.

These cases are dealt with by the respective parts of the following theorem. Its proof follows the approach of Theorem 1.

Theorem 3. Given a pre-Bayesian game N, (Ai)i N, (Pi)i N, (ui)i N and any fixed profile s() = a, there exists a fair, individually rational and implementable adjustment G0 = (vi)i N independent of P, such that in game G + G0 = N, (Ai)i N, (Pi)i N, (ui + vi)i N , s is strictly dominant if one of the following holds:

1. The utilities p of each player i are distributed according to some distribution with a finite support [mi, Mi], which size Mi mi is known to the planner.

2. For every player i N and every pi Pi, the unilateral utility changes are bounded by Bi, namely |pi(ai, a i) pi(di, a i)| Bi, i N, ai, di Ai, a i A i, such a bound Bi being known to the planner, for every i N.

Next, we loosen the knowledge assumptions even further; namely, we assume that the planner is merely aware of the distribution of some relevant parameters of the players. Every player keeps being aware only of her own utilities, as usual. The following result models one of the following cases, each part of the theorem modelling the respective case.

1. The planner knows the distribution of the players utilities in the original game. In the subway example, the planner sees the mutual distributions of the random variables modelling the original preferences of the players.

2. Instead of knowing the size of the support of each player s values, the player only knows the distribution of the random variables delimiting this support. In the subway example, this means that the preference amplitude of each person regarding using each given subway station is known as a random variable.

3. The planner knows the expectation of the maximal changes a player can achieve to herself by a unilateral deviation. In the subway example, the municipality knows the expectation of the extent to which choosing a station matters to the choosing player.

Theorem 4. Consider a pre-Bayesian game N, (Ai)i N, (Pi)i N, (ui)i N and a fixed profile s() a. Then, for any ϵ > 0, there exists a fair, individually rational and implementable adjustment G0 = (vi)i N independent of P, such that in game G + G0 = N, (Ai)i N, (Pi)i N, (ui + vi)i N , s is strictly dominant with probability greater than 1 ϵ if one of the following holds:

1. Utilities pi of every player i N are randomly distributed according to some distribution Fi, not necessarily I.I.D., and the planner knows the mutual distributions of pi(ai, a i) and pi(a i, a i) for each i N and for any ai, a i Ai and a i A i.

2. Utilities pi of every player i N all lie in the segment [mi, Mi], where the segment lengths Mi mi are randomly distributed, and the expected value of these lengths, namely E(Mi mi), are known to the planner.

3. For every player i N and every pi Pi, the unilateral utility changes are bounded by Bi, namely |pi(ai, a i) pi(di, a i)| Bi(pi), i N, ai, di Ai, a i A i, the bounds Bi(pi) are randomly distributed, and their expected values Epi(Bi(pi)) are known to the planner.

If the planner possesses exact knowledge about some players, less knowledge about some others, and the least knowledge about the rest, then she can still employ Theorem 4, simply the probabilities will sometimes become degenerate. The adjustment from Theorem 4 might fail with probability smaller than ϵ. If it fails, but the planner has time to re-adjust the game again, one could merely decrease the allowed error probability ϵ and re-adjust the game accordingly. However, the planner can learn from observing the failure. A failure means that at least one player, say i, has played a i = ai. Assuming every player plays a strictly dominant strategy, when it exists, we conclude that si() a was not strictly dominant after the adjustment, meaning that s i, S i, such that ui(s i, s i) ui(si, s i). We can now apply the techniques of choosing the adjustment from Theorem 4, after conditioning all the probabilistic assumptions on this event.

5 Discussion and Conclusions

We assume the planner knows the payoffs, exactly or probabilistically, because she can estimate those in some cases, such as in Examples 1, 2, and 3. This is thus not a mechanism design problem; nonetheless, let us consider whether we could design an implementable, fair and individually rational transfer minimising game form that asks for the private values and subsequently only adjusts the players payoffs, thereby rendering the desired profile the strictly dominant equilibrium. This is impossible even for 2 players, but we omit the proof for lack of space. The general transfer of our adjustment is linear in the planner s estimate of the players payoffs differences, be the estimate deterministic or probabilistic. Our adjustments also demonstrate which information a player should conceal to avoid being lured into a certain behavior. When profile-based taxes/subsidies are impossible, one may provide larger taxes/subsidies befitting multiple profiles, such that each individual action will fully determine the tax/subsidy. Using the maximum absolute value works also when missing other pieces of information.

Acknowledgements

This work was supported by Polish National Science Centre through grant 2018/29/B/ST6/00174.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

References [Augustine et al., 2015] John E. Augustine, I. Caragiannis, A. Fanelli, and C. Kalaitzis. Enforcing efficient equilibria in network design games via subsidies. Algorithmica, 72:44 82, 2015. [Buchbinder et al., 2008] N. Buchbinder, L. Lewin-Eytan, J. Naor, and A. Orda. Non-cooperative cost sharing games via subsidies. In B. Monien and U-P. Schroeder, editors, Algorithmic Game Theory, pages 337 349, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. [Caragiannis et al., 2010] I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos. Taxes for linear atomic congestion games. ACM Transactions on Algorithms, 7:13, 11 2010. [Caragiannis, 2012] I. Caragiannis. Efficient coordination mechanisms for unrelated machine scheduling. Algorithmica, 66:512 540, 2012. [Chalker et al., 2009] J. Chalker, A. Wagner, G. Tomson, R. Laing, K. Johnson, R. Wahlstr om, and D. Ross-Degnan. Urgent need for coordination in adopting standardized antiretroviral adherence performance indicators. Journ. of acqu. imm. def. synd. (1999), 53:159 61, 10 2009. [Christodoulou et al., 2012] George Christodoulou, Kurt Mehlhorn, and Evangelia Pyrga. Improving the price of anarchy for selfish routing via coordination mechanisms. Algorithmica, 69, 02 2012. [Clemons and Row, 1993] Eric K. Clemons and Michael C. Row. Limits to interfirm coordination through information technology: Results of a field study in consumer packaged goods distribution. J. of Man. Inf. Sys., 10(1):73 96, 1993. [Cole et al., 2003] R. Cole, Y. Dodis, and T. Roughgarden. Pricing network edges for heterogeneous selfish users. Conference Proceedings of the Annual ACM Symposium on Theory of Computing, 04 2003. [Cole et al., 2006] R. Cole, Y. Dodis, and T. Roughgarden. How much can taxes help selfish routing? Journ. of Comp. and Sys. Sc., 72(3):444 467, 2006. Net. Algorithms 2005. [Deng et al., 2016] Yuan Deng, Pingzhong Tang, and Shuran Zheng. Complexity and algorithms of k-implementation. In Proceedings of the 2016 International Conference on Autonomous Agents &amp; Multiagent Systems, AAMAS 16, page 5 13, Richland, SC, 2016. International Foundation for Autonomous Agents and Multiagent Systems. [Dybvig and Spatt, 1983] Philip H. Dybvig and Chester S. Spatt. Adoption externalities as public goods. Journal of Public Economics, 20(2):231 247, 1983. [Eidenbenz et al., 2007] R. Eidenbenz, Oswald. Y. A., S. Schmid, and R. Wattenhofer. Mechanism design by creditability. In A. W. M. Dress, Y. Xu, and B. Zhu, editors, Comb. Opt. and App., First Intern. Conf., COCOA 2007, Xi an, China, August 14-16, 2007, Proceedings, volume 4616 of LNCS, pages 208 219. Springer, 2007. [Fleischer et al., 2004] L. Fleischer, K. Jain, and M. Mahdian. Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In 45th IEEE Sym. on Found. of CS, pages 277 285, 2004.

[Hardin, 1968] Garrett Hardin. The tragedy of the commons. Science, 162(3859):1243 1248, 1968. [Ivanova et al., 2020] D. Ivanova, J. Barrett, D. Wiedenhofer, B. Macura, M. Callaghan, and F. Creutzig. Quantifying the potential for climate change mitigation of consumption options. Environmental Research Letters, 15(9):093001, aug 2020. [Jackson and Wilkie, 2005] Matthew O. Jackson and Simon Wilkie. Endogenous games and mechanisms: Side payments among players. The Review of Economic Studies, 72(2):543 566, 2005. [Jackson, 2001] Matthew O. Jackson. A crash course in implementation theory. Social Choice and Welfare, 18(4):655 708, 2001. [Korilis et al., 1997] Y.A. Korilis, A.A. Lazar, and A. Orda. Achieving network optima using stackelberg routing strategies. IEEE/ACM Tran. on Net., 5(1):161 173, 1997. [Levit et al., 2019] V. Levit, Z. Komarovsky, T. Grinshpoun, A. Bazzan, and A. Meisels. Incentive-based search for equilibria in boolean games. Constraints, 24, 10 2019. [Mc Adams, 2009] Richard Mc Adams. Beyond the prisoners dilemma: Coordination, game theory, and law. Southern California law review, 82:173 222, 10 2009. [Monderer and Tennenholtz, 2004] Dov Monderer and Moshe Tennenholtz. K-implementation. J. Artif. Intell. Res. (JAIR), 21:37 62, 01 2004. [Monderer and Tennenholtz, 2009] Dov Monderer and Moshe Tennenholtz. Strong mediated equilibrium. Artificial Intelligence, 173(1):180 195, 2009.

[Nisan et al., 2007] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007. [Radaelli, 1998] C. Radaelli. Game theory and institutional entrepreneurship: Transfer pricing and the search for coordination international tax policy. Policy Studies Journal, 26:603 619, 1998. [Roughgarden, 2001] Tim Roughgarden. Stackelberg scheduling strategies. SIAM Jour. on Comp., 33, 03 2001. [Swamy, 2007] Chaitanya Swamy. The effectiveness of stackelberg strategies and tolls for network congestion games. In Proceed. of the Eighteenth Ann. ACM-SIAM Sym. on Disc. Alg., SODA 07, page 1133 1142, USA, 2007. Society for Industrial and Applied Mathematics. [Varakantham et al., 2013] P. Varakantham, N. Fu, W. Yeoh, S.-F. Cheng, and H. C. Lau. Budgeted personalized incentive approaches for smoothing congestion in resource networks. In Proc. of the Third Int. Conf. on Alg. Decis. Th. - Vol. 8176, ADT 2013, page 375 386, Berlin, Heidelberg, 2013. Springer-Verlag.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)