Pure strategy equilibria of multidimensional and non-monotonic auctions

We give necessary and sufficient conditions for the existence of symmetric equilibrium without ties in interdependent values auctions, with multidimensional independent types and no monotonic assumptions. In this case, non-monotonic equilibria might happen. When the necessary and sufficient conditions are not satisfied, there are ties with positive probability. In such case, we are still able to prove the existence of pure strategy equilibrium with an all-pay auction tie-breaking rule. As a direct implication of these results, we obtain a generalization of the Revenue Equivalence Theorem. From the robustness of equilibrium existence for all-pay auctions in multidimensional setting, an interpretation of our results can give a new justification to the use of tournaments in practice.

Decentralized Computation of Pareto Optimal Pure Nash Equilibria of Boolean Games with Privacy Concerns

In Boolean games, agents try to reach a goal formulated as a Boolean formula. These games are attractive because of their compact representations. However, few methods are available to compute the solutions and they are either limited or do not take privacy or communication concerns into account. In this paper we propose the use of an algorithm related to reinforcement learning to address this problem. Our method is decentralized in the sense that agents try to achieve their goals without knowledge of the other agents’ goals. We prove that this is a sound method to compute a Pareto optimal pure Nash equilibrium for an interesting class of Boolean games. Experimental results are used to investigate the performance of the algorithm.

Existence of Pure Strategy Nash Equilibrium in Bertrand-Edgeworth Oligopolies

This article is searching for necessary and sufficient conditions which are to be imposed on the demand curve to guarantee the existence of pure strategy Nash equilibrium in a Bertrand-Edgeworth game with capacity constraints.

Bidding Dynamics of Rational Advertisers in Sponsored Search Auctions on the Web

In this paper, we address a key problem faced by advertisers in sponsored search auctions on the web: how much to bid, given the bids of the other advertisers, so as to maximize individual payoffs? Assuming the generalized second price auction as the auction mechanism, we formulate this problem in the framework of an infinite horizon alternative-move game of advertiser bidding behavior. For a sponsored search auction involving two advertisers, we characterize all the pure strategy and mixed strategy Nash equilibria. We also prove that the bid prices will lead to a Nash equilibrium, if the advertisers follow a myopic best response bidding strategy. Following this, we investigate the bidding behavior of the advertisers if they use Q-learning. We discover empirically an interesting trend that the Q-values converge even if both the advertisers learn simultaneously.

Essays on economics networks

This thesis belongs to the growing field of economic networks. In particular, we develop three essays in which we study the problem of bargaining, discrete choice representation, and pricing in the context of networked markets. Despite analyzing very different problems, the three essays share the common feature of making use of a network representation to describe the market of interest.

In Chapter 1 we present an analysis of bargaining in networked markets. We make two contributions. First, we characterize market equilibria in a bargaining model, and find that players' equilibrium payoffs coincide with their degree of centrality in the network, as measured by Bonacich's centrality measure. This characterization allows us to map, in a simple way, network structures into market equilibrium outcomes, so that payoffs dispersion in networked markets is driven by players' network positions. Second, we show that the market equilibrium for our model converges to the so called eigenvector centrality measure. We show that the economic condition for reaching convergence is that the players' discount factor goes to one. In particular, we show how the discount factor, the matching technology, and the network structure interact in a very particular way in order to see the eigenvector centrality as the limiting case of our market equilibrium.

We point out that the eigenvector approach is a way of finding the most central or relevant players in terms of the “global” structure of the network, and to pay less attention to patterns that are more “local”. Mathematically, the eigenvector centrality captures the relevance of players in the bargaining process, using the eigenvector associated to the largest eigenvalue of the adjacency matrix of a given network. Thus our result may be viewed as an economic justification of the eigenvector approach in the context of bargaining in networked markets.

As an application, we analyze the special case of seller-buyer networks, showing how our framework may be useful for analyzing price dispersion as a function of sellers and buyers' network positions.

Finally, in Chapter 3 we study the problem of price competition and free entry in networked markets subject to congestion effects. In many environments, such as communication networks in which network flows are allocated, or transportation networks in which traffic is directed through the underlying road architecture, congestion plays an important role. In particular, we consider a network with multiple origins and a common destination node, where each link is owned by a firm that sets prices in order to maximize profits, whereas users want to minimize the total cost they face, which is given by the congestion cost plus the prices set by firms. In this environment, we introduce the notion of Markovian traffic equilibrium to establish the existence and uniqueness of a pure strategy price equilibrium, without assuming that the demand functions are concave nor imposing particular functional forms for the latency functions. We derive explicit conditions to guarantee existence and uniqueness of equilibria. Given this existence and uniqueness result, we apply our framework to study entry decisions and welfare, and establish that in congested markets with free entry, the number of firms exceeds the social optimum.

Implications of Selfish Neighbor Selection in Overlay Networks

In a typical overlay network for routing or content sharing, each node must select a fixed number of immediate overlay neighbors for routing traffic or content queries. A selfish node entering such a network would select neighbors so as to minimize the weighted sum of expected access costs to all its destinations. Previous work on selfish neighbor selection has built intuition with simple models where edges are undirected, access costs are modeled by hop-counts, and nodes have potentially unbounded degrees. However, in practice, important constraints not captured by these models lead to richer games with substantively and fundamentally different outcomes. Our work models neighbor selection as a game involving directed links, constraints on the number of allowed neighbors, and costs reflecting both network latency and node preference. We express a node's "best response" wiring strategy as a k-median problem on asymmetric distance, and use this formulation to obtain pure Nash equilibria. We experimentally examine the properties of such stable wirings on synthetic topologies, as well as on real topologies and maps constructed from PlanetLab and AS-level Internet measurements. Our results indicate that selfish nodes can reap substantial performance benefits when connecting to overlay networks composed of non-selfish nodes. On the other hand, in overlays that are dominated by selfish nodes, the resulting stable wirings are optimized to such great extent that even non-selfish newcomers can extract near-optimal performance through naive wiring strategies.

Cyclic Pursuit: Symmetry, Reduction and Nonlinear Dynamics

In this dissertation, we explore the use of pursuit interactions as a building block for collective behavior, primarily in the context of constant bearing (CB) cyclic pursuit. Pursuit phenomena are observed throughout the natural environment and also play an important role in technological contexts, such as missile-aircraft encounters and interactions between unmanned vehicles. While pursuit is typically regarded as adversarial, we demonstrate that pursuit interactions within a cyclic pursuit framework give rise to seemingly coordinated group maneuvers. We model a system of agents (e.g. birds, vehicles) as particles tracing out curves in the plane, and illustrate reduction to the shape space of relative positions and velocities. Introducing the CB pursuit strategy and associated pursuit law, we consider the case for which agent i pursues agent i+1 (modulo n) with the CB pursuit law. After deriving closed-loop cyclic pursuit dynamics, we demonstrate asymptotic convergence to an invariant submanifold (corresponding to each agent attaining the CB pursuit strategy), and proceed by analysis of the reduced dynamics restricted to the submanifold. For the general setting, we derive existence conditions for relative equilibria (circling and rectilinear) as well as for system trajectories which preserve the shape of the collective (up to similarity), which we refer to as pure shape equilibria. For two illustrative low-dimensional cases, we provide a more comprehensive analysis, deriving explicit trajectory solutions for the two-particle "mutual pursuit" case, and detailing the stability properties of three-particle relative equilibria and pure shape equilibria. For the three-particle case, we show that a particular choice of CB pursuit parameters gives rise to remarkable almost-periodic trajectories in the physical space. We also extend our study to consider CB pursuit in three dimensions, deriving a feedback law for executing the CB pursuit strategy, and providing a detailed analysis of the two-particle mutual pursuit case. We complete the work by considering evasive strategies to counter the motion camouflage (MC) pursuit law. After demonstrating that a stochastically steering evader is unable to thwart the MC pursuit strategy, we propose a (deterministic) feedback law for the evader and demonstrate the existence of circling equilibria for the closed-loop pursuer-evader dynamics.

Théorie des jeux expérimentale & action motrice

How do sportspeople succeed in a non-collaborative game? An illustration of a perverse side effect of altruism Are team sports specialists predisposed to collaboration? The scientific literature on this topic is divided. The present article attempts to end this debate by applying experimental game theory. We constituted three groups of volunteers (all students aged around 20): 25 team sports specialists; 23 individual sports specialists (gymnasts, track & field athletes and swimmers) and a control group of 24 non-sportspeople. Each subgroup was divided into 3 teams that played against each other in turn (and not against teams from other subgroups). The teams played a game based on the well-known Prisoner's Dilemma (Tucker, 1950) - the paradoxical "Bluegill Sunbass Game" (Binmore, 1999) with three Nash equilibria (two suboptimal equilibria with a pure strategy and an optimal equilibrium with a mixed, egotistical strategy (p= 1/2)). This game also features a Harsanyi equilibrium (based on constant compliance with a moral code and altruism by empathy: "do not unto others that which you would not have them do unto you"). How, then, was the game played? Two teams of 8 competed on a handball court. Each team wore a distinctive jersey. The game lasted 15 minutes and the players were allowed to touch the handball ball with their feet or hands. After each goal, each team had to return to its own half of the court. Players were allowed to score in either goal and thus cooperate with their teammates or not, as they saw fit. A goal against the nominally opposing team (a "guardian" strategy, by analogy with the Bluegill Sunbass Game) earned a point for everyone in the team. For an own goal (a "sneaker" strategy), only the scorer earned a point - hence the paradox. If all the members of a team work together to score a goal, everyone is happy (the Harsanyi solution). However, the situation was not balanced in the Nashian sense: each player had a reason to be disloyal to his/her team at the merest opportunity. But if everyone adopts a "sneaker" strategy, the game becomes a free-for-all and the chances of scoring become much slimmer. In a context in which doubt reigns as to the honesty of team members and "legal betrayals", what type of sportsperson will score the most goals? By analogy with the Bluegill Sunbass Game, we recorded direct motor interactions (passes and shots) based on either a "guardian" tactic (i.e. collaboration within the team) or a "sneaker" tactic (shots and passes against the player's designated team). So, was the group of team sports specialist more collaborative than the other two groups? The answer was no. A statistical analysis (difference from chance in a logistic regression) enabled us to draw three conclusions: ?For the team sports specialists, the Nash equilibrium (1950) was stronger than the Harsanyi equilibrium (1977). ?The sporting principles of equilibrium and exclusivity are not appropriate in the Bluegill Sunbass Game and are quickly abandoned by the team sports specialists. The latter are opportunists who focus solely on winning and do well out of it. ?The most altruistic players are the main losers in the Bluegill Sunbass Game: they keep the game alive but contribute to their own defeat. In our experiment, the most altruistic players tended to be the females and the individual sports specialists

Théorie des jeux expérimentale & action motrice

How do sportspeople succeed in a non-collaborative game? An illustration of a perverse side effect of altruism Are team sports specialists predisposed to collaboration? The scientific literature on this topic is divided. The present article attempts to end this debate by applying experimental game theory. We constituted three groups of volunteers (all students aged around 20): 25 team sports specialists; 23 individual sports specialists (gymnasts, track & field athletes and swimmers) and a control group of 24 non-sportspeople. Each subgroup was divided into 3 teams that played against each other in turn (and not against teams from other subgroups). The teams played a game based on the well-known Prisoner's Dilemma (Tucker, 1950) - the paradoxical "Bluegill Sunbass Game" (Binmore, 1999) with three Nash equilibria (two suboptimal equilibria with a pure strategy and an optimal equilibrium with a mixed, egotistical strategy (p= 1/2)). This game also features a Harsanyi equilibrium (based on constant compliance with a moral code and altruism by empathy: "do not unto others that which you would not have them do unto you"). How, then, was the game played? Two teams of 8 competed on a handball court. Each team wore a distinctive jersey. The game lasted 15 minutes and the players were allowed to touch the handball ball with their feet or hands. After each goal, each team had to return to its own half of the court. Players were allowed to score in either goal and thus cooperate with their teammates or not, as they saw fit. A goal against the nominally opposing team (a "guardian" strategy, by analogy with the Bluegill Sunbass Game) earned a point for everyone in the team. For an own goal (a "sneaker" strategy), only the scorer earned a point - hence the paradox. If all the members of a team work together to score a goal, everyone is happy (the Harsanyi solution). However, the situation was not balanced in the Nashian sense: each player had a reason to be disloyal to his/her team at the merest opportunity. But if everyone adopts a "sneaker" strategy, the game becomes a free-for-all and the chances of scoring become much slimmer. In a context in which doubt reigns as to the honesty of team members and "legal betrayals", what type of sportsperson will score the most goals? By analogy with the Bluegill Sunbass Game, we recorded direct motor interactions (passes and shots) based on either a "guardian" tactic (i.e. collaboration within the team) or a "sneaker" tactic (shots and passes against the player's designated team). So, was the group of team sports specialist more collaborative than the other two groups? The answer was no. A statistical analysis (difference from chance in a logistic regression) enabled us to draw three conclusions: ?For the team sports specialists, the Nash equilibrium (1950) was stronger than the Harsanyi equilibrium (1977). ?The sporting principles of equilibrium and exclusivity are not appropriate in the Bluegill Sunbass Game and are quickly abandoned by the team sports specialists. The latter are opportunists who focus solely on winning and do well out of it. ?The most altruistic players are the main losers in the Bluegill Sunbass Game: they keep the game alive but contribute to their own defeat. In our experiment, the most altruistic players tended to be the females and the individual sports specialists

Théorie des jeux expérimentale & action motrice

How do sportspeople succeed in a non-collaborative game? An illustration of a perverse side effect of altruism Are team sports specialists predisposed to collaboration? The scientific literature on this topic is divided. The present article attempts to end this debate by applying experimental game theory. We constituted three groups of volunteers (all students aged around 20): 25 team sports specialists; 23 individual sports specialists (gymnasts, track & field athletes and swimmers) and a control group of 24 non-sportspeople. Each subgroup was divided into 3 teams that played against each other in turn (and not against teams from other subgroups). The teams played a game based on the well-known Prisoner's Dilemma (Tucker, 1950) - the paradoxical "Bluegill Sunbass Game" (Binmore, 1999) with three Nash equilibria (two suboptimal equilibria with a pure strategy and an optimal equilibrium with a mixed, egotistical strategy (p= 1/2)). This game also features a Harsanyi equilibrium (based on constant compliance with a moral code and altruism by empathy: "do not unto others that which you would not have them do unto you"). How, then, was the game played? Two teams of 8 competed on a handball court. Each team wore a distinctive jersey. The game lasted 15 minutes and the players were allowed to touch the handball ball with their feet or hands. After each goal, each team had to return to its own half of the court. Players were allowed to score in either goal and thus cooperate with their teammates or not, as they saw fit. A goal against the nominally opposing team (a "guardian" strategy, by analogy with the Bluegill Sunbass Game) earned a point for everyone in the team. For an own goal (a "sneaker" strategy), only the scorer earned a point - hence the paradox. If all the members of a team work together to score a goal, everyone is happy (the Harsanyi solution). However, the situation was not balanced in the Nashian sense: each player had a reason to be disloyal to his/her team at the merest opportunity. But if everyone adopts a "sneaker" strategy, the game becomes a free-for-all and the chances of scoring become much slimmer. In a context in which doubt reigns as to the honesty of team members and "legal betrayals", what type of sportsperson will score the most goals? By analogy with the Bluegill Sunbass Game, we recorded direct motor interactions (passes and shots) based on either a "guardian" tactic (i.e. collaboration within the team) or a "sneaker" tactic (shots and passes against the player's designated team). So, was the group of team sports specialist more collaborative than the other two groups? The answer was no. A statistical analysis (difference from chance in a logistic regression) enabled us to draw three conclusions: ?For the team sports specialists, the Nash equilibrium (1950) was stronger than the Harsanyi equilibrium (1977). ?The sporting principles of equilibrium and exclusivity are not appropriate in the Bluegill Sunbass Game and are quickly abandoned by the team sports specialists. The latter are opportunists who focus solely on winning and do well out of it. ?The most altruistic players are the main losers in the Bluegill Sunbass Game: they keep the game alive but contribute to their own defeat. In our experiment, the most altruistic players tended to be the females and the individual sports specialists

Nonatomic games on Loeb spaces

In the setting of noncooperative game theory, strategic negligibility of individual agents, or diffuseness of information, has been modeled as a nonatomic measure space, typically the unit interval endowed with Lebesgue measure. However, recent work has shown that with uncountable action sets, for example the unit interval, there do not exist pure-strategy Nash equilibria in such nonatomic games. In this brief announcement, we show that there is a perfectly satisfactory existence theory for nonatomic games provided this nonatomicity is formulated on the basis of a particular class of measure spaces, hyperfinite Loeb spaces. We also emphasize other desirable properties of games on hyperfinite Loeb spaces, and present a synthetic treatment, embracing both large games as well as those with incomplete information.

Strategic Information Acquisition: Applications to Herding and Auctions

The information that the economic agents have and regard relevant to their decision making is often assumed to be exogenous in economics. It is assumed that the agents either poses or can observe the payoff relevant information without having to exert any effort to acquire it. In this thesis we relax the assumption of ex-ante fixed information structure and study what happens to the equilibrium behavior when the agents must also decide what information to acquire and when to acquire it. This thesis addresses this question in the two essays on herding and two essays on auction theory. In the first two essays, that are joint work with Klaus Kultti, we study herding models where it is costly to acquire information on the actions that the preceding agents have taken. In our model the agents have to decide both the action that they take and additionally the information that they want to acquire by observing their predecessors. We characterize the equilibrium behavior when the decision to observe preceding agents' actions is endogenous and show how the equilibrium outcome may differ from the standard model, where all preceding agents actions are assumed to be observable. In the latter part of this thesis we study two dynamic auctions: the English and the Dutch auction. We consider a situation where bidder(s) are uninformed about their valuations for the object that is put up for sale and they may acquire this information for a small cost at any point during the auction. We study the case of independent private valuations. In the third essay of the thesis we characterize the equilibrium behavior in an English auction when there are informed and uninformed bidders. We show that the informed bidder may jump bid and signal to the uninformed that he has a high valuation, thus deterring the uninformed from acquiring information and staying in the auction. The uninformed optimally acquires information once the price has passed a particular threshold and the informed has not signalled that his valuation is high. In addition, we provide an example of an information structure where the informed bidder initially waits and then makes multiple jumps. In the fourth essay of this thesis we study the Dutch auction. We consider two cases where all bidders are all initially uninformed. In the first case the information acquisition cost is the same across all bidders and in the second also the cost of information acquisition is independently distributed and private information to the bidders. We characterize a mixed strategy equilibrium in the first and a pure strategy equilibrium in the second case. In addition we provide a conjecture of an equilibrium in an asymmetric situation where there is one informed and one uninformed bidder. We compare the revenues that the first price auction and the Dutch auction generate and we find that under some circumstances the Dutch auction outperforms the first price sealed bid auction. The usual first price sealed bid auction and the Dutch auction are strategically equivalent. However, this equivalence breaks down in case information is acquired during the auction.

Using Answer Set Programming for Solving Boolean Games

Boolean games are a framework for reasoning about the rational behaviour of agents, whose goals are formalized using propositional formulas. They offer an attractive alternative to normal-form games, because they allow for a more intuitive and more compact encoding. Unfortunately, however, there is currently no general, tailor-made method available to compute the equilibria of Boolean games. In this paper, we introduce a method for finding the pure Nash equilibria based on disjunctive answer set programming. Our method is furthermore capable of finding the core elements and the Pareto optimal equilibria, and can easily be modified to support other forms of optimality, thanks to the declarative nature of disjunctive answer set programming. Experimental results clearly demonstrate the effectiveness of the proposed method.