We introduce and study a PDL-style logic for reasoning about protocols, or plans, under imperfect information. Our paper touches on a number of issues surrounding the relationship between an agent’s abilities, available choices, and information in an interactive situation. The main question we address is under what circumstances can the agent commit to a protocol or plan, and what can she achieve by doing so?

Weakly acyclic games form a natural generalization of the class of games that have the finite improvement property. In such games one stipulates that from any initial joint strategy some finite improvement path exists. We classify weakly acyclic games using the concept of a scheduler introduced in Simon and Apt. We also show that finite games that can be solved by the iterated elimination of never best response strategies are weakly acyclic. Finally, we explain how the schedulers allow us to (...) improve the bounds on finding a Nash equilibrium in a weakly acyclic game. (shrink)

When we reason about strategic games, implicitly we need to reason about arbitrary strategy profiles and how players can improve from each profile. This structure is exponential in the number of players. Hence it is natural to look for subclasses of succinct games for which we can reason directly by interpreting formulas on the (succinct) game description rather than on the associated improvement structure. Priority separable games are one of such subclasses: payoffs are specified for pairwise interactions, and from these, (...) payoffs are computed for strategy profiles. We show that equilibria in such games can be described in Monadic Least Fixed Point Logic (MLFP). We then extend the description to games over arbitrarily many players, but using the monadic least fixed point extension of existential second order logic. (shrink)

We show that various paradoxes can arise in a natural class of social networks. They demonstrate that more services or products may have adverse consequences for all members of the network and conversely that restricting the number of choices may be beneficial for every member of the network. These phenomena have been confirmed by a number of empirical studies. In our analysis we use a simple threshold model of social networks introduced in Apt and Markakis, and more fully in Apt (...) and Markakis. In this model the agents, influenced by their neighbours, can adopt one out of several alternatives. We identify and analyze here four types of paradoxes that can arise in these networks. These paradoxes shed light on possible inefficiencies arising when one modifies the sets of products available to the agents forming a social network or the network structure. One of the paradoxes corresponds to the well-known Braess paradox in congestion games and shows that by adding more choices to a node, the network may end up in a situation that is worse for everybody. We exhibit a dual version of this, according to which removing a product available to an agent can eventually make everybody better off. The other paradoxes that we identify show that by adding or removing a product from the choice set of an agent may lead to permanent instability. Finally, we also identify conditions under which some of these paradoxes cannot arise. (shrink)