Arthur Dolgopolov

I characterize the outcomes of a class of model-free reinforcement learning algorithms, such as stateless Q-learning, in a prisoner's dilemma. The behavior is studied in the limit as players stop experimenting after sufficiently exploring their options. A closed form relationship between the learning rate and game payoffs reveals whether the players will learn to cooperate or defect. The findings have implications for algorithmic collusion and also apply to asymmetric learners with different experimentation rules.

(with Cesar Martinelli, Daniel Houser and Thomas Stratmann)

We experimentally test convergence to the core in two-sided markets for heterogeneous indivisible goods under different trading institutions. We use bargaining and strategic games as predictors that naturally generalize the core, accommodating non-equilibrium behavior. The performance of the competing theories reflects the differences in trading procedures - market outcomes are close to Nash equilibrium predictions under auction-like institutions and close to bargaining for institutions that feature decentralized negotiations. This difference may be driving the documented effect of fewer no-trade outcomes at the expense of a higher chance of suboptimal match under free-form bargaining.

(Job Market Paper)

I demonstrate that an efficient allocation of goods can be found in polynomial time if and only if a competitive equilibrium exists in the corresponding market. In other words, competitive markets solve precisely the class of all tractable optimization problems. This result holds under mild restrictions on allowable valuations and applies to markets involving both private and public goods. These findings build on a novel connection between competitive equilibria and valued constraint satisfaction problems from complexity theory. I illustrate how this approach can be employed to establish the existence or nonexistence of competitive prices across various classes of valuations.

(with Cesar Martinelli)

We show that strategic market games, the non-cooperative implementation of a matching with transfers or an assignment game, are weakly acyclic. This property ensures that many common learning algorithms will converge to Nash equilibria in these games, and that the allocation mechanism can therefore be decentralized. Convergence hinges on the appropriate price clearing rule and has different properties for better- and best-response dynamics. We tightly characterize the robustness of this convergence in terms of so-called schedulers for both types of dynamics.

(with Mikhail Freer)

The essential problem in the empirical analysis of the repeated games is to know what strategies are actually used by the players. We propose a simple algorithm to reconstruct strategies out of the observed sequence of play. The algorithm also accounts for the possibility of measurement and decision making errors and stays agnostic about equilibrium restrictions. We apply the algorithm to both experimental and observational data. Using the experimental data we conclusively show that players use strategies of memory no more than one period. Using the observational data we confirm that Australian gas stations learn to collude using day of the week as coordination device.

(with Mikhail Freer)

We use a revealed preference approach to develop tests for the observed behavior to be consistent with theories of social preferences. In particular, we provide nonparametric criteria for the observed set of choices to be generated by inequality averse preferences and increasing benevolence preferences. These tests can be applied to games commonly used to study social preferences: dictator, ultimatum, investment(trust) and carrot-stick games. We further apply these tests to experimental data on dictator and ultimatum games. Finally, we show how to identify the levels of altruism and fair outcomes using the developed revealed preference conditions.

The paper provides an automated approach to mechanism design problems without money for arbitrary discount factors using dynamic programming and promised utility. We illustrate the approach with problems from the literature - chore allocation or sharing an indivisible good or goods. Additionally, we discuss the relationships between different classes of mechanisms, and show that promised utility mechanisms are more general than mappings from histories of finite memory.

(with Mikhail Freer and Marco Castillo)

We study games of incomplete information from a revealed preference perspective and provide a nonparametric test for Bayesian Nash rationalization - existence of such expected utility representations for agents that observed choices are Bayesian Nash equilibria. In the basic setup we assume that everything, but the cardinal utility is known by the researcher (including beliefs of players over distribution of types). However, we discuss the possibility of relaxing several assumptions. In particular, we consider that researcher may be unaware of the distribution of types, or number of types. The test can also be applied with assumptions about rationality of agents that follow different theories of behavior under risk - cumulative propsect theory or rank-dependent expected utility.