Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInformation Design in Large Games
136
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We define the notion of Bayes correlated Wardrop equilibrium for general nonatomic games with anonymous players and incomplete information. Bayes correlated Wardrop equilibria describe the set of equilibrium outcomes when a mediator, such as a traffic information system, provides information to the players. We relate this notion to Bayes Wardrop equilibrium. Then, we provide conditions -- existence of a convex potential and complete information -- under which mediation does not improve equilibrium outcomes. We then study full implementation and, finally, information design in anonymous games with a finite set of players, when the number of players tends to infinity.
rate research
Read More
We study contests where the designers objective is an extension of the widely studied objective of maximizing the total output: The designer gets zero marginal utility from a players output if the output of the player is very low or very high. We model this using two objective functions: binary threshold, where a players contribution to the designers utility is 1 if her output is above a certain threshold, and 0 otherwise; and linear threshold, where a players contribution is linear if her output is between a lower and an upper threshold, and becomes constant below the lower and above the upper threshold. For both of these objectives, we study (1) rank-order allocation contests that use only the ranking of the players to assign prizes and (2) general contests that may use the numerical values of the players outputs to assign prizes. We characterize the optimal contests that maximize the designers objective and indicate techniques to efficiently compute them. We also prove that for the linear threshold objective, a contest that distributes the prize equally among a fixed number of top-ranked players offers a factor-2 approximation to the optimal rank-order allocation contest.
When selling information products, the seller can provide some free partial information to change peoples valuations so that the overall revenue can possibly be increased. We study the general problem of advertising information products by revealing partial information. We consider buyers who are decision-makers. The outcomes of the decision problems depend on the state of the world that is unknown to the buyers. The buyers can make their own observations and thus can hold different personal beliefs about the state of the world. There is an information seller who has access to the state of the world. The seller can promote the information by revealing some partial information. We assume that the seller chooses a long-term advertising strategy and then commits to it. The sellers goal is to maximize the expected revenue. We study the problem in two settings. (1) The seller targets buyers of a certain type. In this case, we prove that finding the optimal advertising strategy is equivalent to finding the concave closure of a simple function. The function is a product of two quantities, the likelihood ratio and the cost of uncertainty. Based on this observation, we prove some properties of the optimal mechanism, which allow us to solve for the optimal mechanism by a finite-size convex program. The convex program will have a polynomial size if the state of the world has a constant number of possible realizations or the buyers face a decision problem with a constant number of options. For the general problem, we prove that it is NP-hard to find the optimal mechanism. (2) When the seller faces buyers of different types and only knows the distribution of their types, we provide an approximation algorithm when it is not too hard to predict the possible type of buyers who will make the purchase. For the general problem, we prove that it is NP-hard to find a constant-factor approximation.
Mechanism design has traditionally assumed that the set of participants are fixed and known to the mechanism (the market owner) in advance. However, in practice, the market owner can only directly reach a small number of participants (her neighbours). Hence the owner often needs costly promotions to recruit more participants in order to get desirable outcomes such as social welfare or revenue maximization. In this paper, we propose to incentivize existing participants to invite their neighbours to attract more participants. However, they would not invite each other if they are competitors. We discuss how to utilize the conflict of interest between the participants to incentivize them to invite each other to form larger markets. We will highlight the early solutions and open the floor for discussing the fundamental open questions in the settings of auctions, coalitional games, matching and voting.
In some games, additional information hurts a player, e.g., in games with first-mover advantage, the second-mover is hurt by seeing the first-movers move. What properties of a game determine whether it has such negative value of information for a particular player? Can a game have negative value of information for all players? To answer such questions, we generalize the definition of marginal utility of a good to define the marginal utility of a parameter vector specifying a game. So rather than analyze the global structure of the relationship between a games parameter vector and player behavior, as in previous work, we focus on the local structure of that relationship. This allows us to prove that generically, every game can have negative marginal value of information, unless one imposes a priori constraints on allowed changes to the games parameter vector. We demonstrate these and related results numerically, and discuss their implications.
Search has played a fundamental role in computer game research since the very beginning. And while online search has been commonly used in perfect information games such as Chess and Go, online search methods for imperfect information games have only been introduced relatively recently. This paper addresses the question of what is a sound online algorithm in an imperfect information setting of two-player zero-sum games. We argue that the~fixed-strategy~definitions of exploitability and $epsilon$-Nash equilibria are ill-suited to measure an online algorithms worst-case performance. We thus formalize $epsilon$-soundness, a concept that connects the worst-case performance of an online algorithm to the performance of an $epsilon$-Nash equilibrium. As $epsilon$-soundness can be difficult to compute in general, we introduce a consistency framework -- a hierarchy that connects an online algorithms behavior to a Nash equilibrium. These multiple levels of consistency describe in what sense an online algorithm plays just like a fixed Nash equilibrium. These notions further illustrate the difference between perfect and imperfect information settings, as the same consistency guarantees have different worst-case online performance in perfect and imperfect information games. The definitions of soundness and the consistency hierarchy finally provide appropriate tools to analyze online algorithms in repeated imperfect information games. We thus inspect some of the previous online algorithms in a new light, bringing new insights into their worst-case performance guarantees.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
