This paper addresses the computational challenges of learning strong substitutes demand when given access to a demand (or valuation) oracle. Strong substitutes demand generalises the well-studied gross substitutes demand to a multi-unit setting. Recent work by Baldwin and Klemperer shows that any such demand can be expressed in a natural way as a nite list of weighted bid vectors. A simplified version of this bidding language has been used by the Bank of England. Assuming access to a demand oracle, we provide an algorithm that computes the unique list of weighted bid vectors corresponding to a bidder's demand preferences. In the special case where their demand can be expressed using positive bids only, we have an efficient algorithm that learns this list in linear time. We also show super-polynomial lower bounds on the query complexity of computing the list of bids in the general case where bids may be positive and negative. Our algorithms constitute the first systematic approach for bidders to construct a bid list corresponding to non-trivial demand, allowing them to participate in `product-mix' auctions.

Despite the emphases on computability issues in research of algorithmic game theory, the limited computational capacity of players have received far less attention. This work examines how different levels of players’ computational ability (or “rationality”) impact the outcomes of sequential scheduling games. Surprisingly, our results show that a lower level of rationality of players may lead to better equilibria. More specifically, we characterize the sequential price of anarchy (SPoA) under two different models of bounded rationality, namely, players with k-lookahead and simple-minded players. The model in which players have k-lookahead interpolates between the “perfect rationality” (k = n − 1) and “online greedy” (k = 0). Our results show that the inefficiency of equilibria (SPoA) increases in k the degree of lookahead: SPoA = O(k²) for two machines and SPoA = O(2^k min{mk, n}) for m machines, where n is the number of players. Moreover, when players are simple-minded, the SPoA is exactly m, which coincides with the performance of “online greedy”.

The paper investigates how the two key features of GDPR (EU's data protection regulation)—privacy rights and data security—impact personal data driven markets. First, GDPR recognizes that individuals own and control their data in perpetuity, leading to three critical privacy rights: (i) right to explicit consent (data opt-in), (ii) right to be forgotten (data erasure), and (iii) right to portability (switch data to competitor). Second, GDPR has data security mandates protection against privacy breaches through unauthorized access. The right to explicit opt-in allows goods exchange without data exchange. Erasure and portability rights discipline firms to provide ongoing value and reduces consumers' holdup using their own data. Overall, privacy rights restrict legal collection and use, while data security protects against illegal access and use. We develop a two-period model of forward-looking firms and consumers where consumers exercise data privacy rights balancing the cost (privacy breach, price discrimination) and benefits (product personalization, price subsidies) of sharing data with firms. We find that by reducing expected privacy breach costs, data security mandates increase opt-in, consumer surplus and firm profit. Privacy rights reduce opt-in and mostly increase consumer surplus at the expense of firm profits; interestingly they hurt firms more in competitive than in monopolistic markets. While privacy rights can reduce surplus for both firms and consumers, these conditions are unlikely to be realized when breach risk is endogenized. Further, by unbundling data exchange from goods exchange, privacy rights facilitate trade in goods that may otherwise fail to occur due to privacy breach risk.

We study the power and limits of optimal dynamic pricing in combinatorial markets; i.e., dynamic pricing that leads to optimal social welfare. Previous work by Cohen-Addad et al. [EC'16] demonstrated the existence of optimal dynamic prices for unit-demand buyers, and showed a market with coverage valuations that admits no such prices. However, finding the most general class of markets (i.e., valuation functions) that admit optimal dynamic prices remains an open problem. In this work we establish positive and negative results that narrow the existing gap. On the positive side, we provide tools for handling markets beyond unit-demand valuations. In particular, we characterize all optimal allocations in multi-demand markets. This characterization allows us to partition the items into equivalence classes according to the role they play in achieving optimality. Using these tools, we provide a poly-time optimal dynamic pricing algorithm for up to 3 multi-demand buyers. On the negative side, we establish a maximal domain theorem, showing that for every non-gross substitutes valuation, there exist unit-demand valuations such that adding them yields a market that does not admit an optimal dynamic pricing. This result is the dynamic pricing equivalent of the seminal maximal domain theorem by Gul and Stacchetti [JET'99] for Walrasian equilibrium. Yang [JET'17] discovered an error in their original proof, and established a different, incomparable version of their maximal domain theorem. En route to our maximal domain theorem for optimal dynamic pricing, we provide the first complete proof of the original theorem by Gul and Stacchetti.

In various situations, decision makers face experts that may provide conflicting advice. This advice may be in the form of probabilistic forecasts over critical future events. We consider a setting where the two forecasters provide their advice repeatedly and ask whether the decision maker can learn to compare and rank the two forecasters based on past performance. We take an axiomatic approach and propose three natural axioms that a comparison test should comply with. We propose a test that complies with our axioms. Perhaps, not surprisingly, this test is closely related to the likelihood ratio of the two forecasts over the realized sequence of events. More surprisingly, this test is essentially unique. Furthermore, using results on the rate of convergence of supermartingales, we show that whenever the two experts' advice are sufficiently distinct, the proposed test will detect the informed expert in any desired degree of precision in some fi xed fi nite time.

In multi-agent environments in which coordination is desirable, the history of play often causes lock-in at sub-optimal outcomes. Notoriously, technologies with a significant environmental footprint or high social cost persist despite the successful development of more environmentally friendly and/or socially efficient alternatives. The displacement of the status quo is hindered by entrenched economic interests and network effects. To exacerbate matters, the standard mechanism design approaches based on centralized authorities with the capacity to use preferential subsidies to effectively dictate system outcomes are not always applicable to modern decentralized economies. What other types of mechanisms are feasible?

In this paper, we develop and analyze a mechanism that induces transitions from inefficient lock-ins to superior alternatives. This mechanism does not exogenously favor one option over another – instead, the phase transition emerges endogenously via a standard evolutionary learning model, Q-learning, where agents trade-off exploration and exploitation. Exerting the same transient influence to both the efficient and inefficient technologies encourages exploration and results in irreversible phase transitions and permanent stabilization of the efficient one. On a technical level, our work is based on bifurcation and catastrophe theory, a branch of mathematics that deals with changes in the number and stability properties of equilibria. Critically, our analysis is shown to be structurally robust to significant and even adversarially chosen perturbations to the parameters of both our game and our behavioral model. The full version of the paper can be found at https://arxiv.org/abs/2007.12877.

In this work, we analyze the influence of a single strategic agent on the quality of the other agents' matchings in a matching market. We consider a stable matching problem with an equal number of men and women with uniformly drawn preferences, and focus on the effect of a single woman who reports a modified preferences list in a way that is optimal from her perspective. We show that in this case, the quality of the matching dramatically improves from the other women's perspectives. When running the Gale-Shapley men-proposing algorithm, the expected women-rank is polylogarithmic in the market size, rather than an almost-linear rank under a truthful regime. Conversely, almost-surely, the men-rank is almost-linear in the market size, compared to a logarithmic rank under a truthful regime. These results suggest that the small number of stable solutions observed in real life may also be caused by strategic behavior by even a few participants.