# Reasoning about Human-Friendly Strategies in Repeated Keyword Auctions

arXiv: https://arxiv.org/abs/2201.09616 · HTML: https://mlsanity.com/paper/2201.09616/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 79 references that are in the map.
- First posted on arXiv 24 Jan 2022.

## Builds on (most cited first, 9 of 9)

- [Verification of Agent-Based Artifact Systems](https://mlsanity.com/paper/1301.2678/) (2013)
- [Reasoning about Quality and Fuzziness of Strategic Behaviours](https://mlsanity.com/paper/1905.11537/) (2019)
- [Natural Strategic Abilities in Voting Protocols](https://mlsanity.com/paper/2007.12424/) (2020)
- [Alternating-time temporal logic with finite-memory strategies](https://mlsanity.com/paper/1307.4476/) (2013)
- [MCMAS-SLK: A Model Checker for the Verification of Strategy Logic Specifications](https://mlsanity.com/paper/1402.2948/) (2014)
- [Making the Best of Limited Memory in Multi-Player Discounted Sum Games](https://mlsanity.com/paper/1410.4154/) (2014)
- [Computer-aided verification in mechanism design](https://mlsanity.com/paper/1502.04052/) (2015)
- [An Introduction to Mechanized Reasoning](https://mlsanity.com/paper/1603.02478/) (2016)
- [Representing Strategies](https://mlsanity.com/paper/1607.03355/) (2016)

## Built on by (most cited first, 2 of 2)

- [Natural Strategic Ability in Stochastic Multi-Agent Systems](https://mlsanity.com/paper/2401.12170/) (2024)
- [A Neuro-Symbolic Approach to Strategy Synthesis for Strategic Logics](https://mlsanity.com/paper/2606.17962/) (2026)

## Abstract (arXiv)

In online advertising, search engines sell ad placements for keywords continuously through auctions. This problem can be seen as an infinitely repeated game since the auction is executed whenever a user performs a query with the keyword. As advertisers may frequently change their bids, the game will have a large set of equilibria with potentially complex strategies. In this paper, we propose the use of natural strategies for reasoning in such setting as they are processable by artificial agents with limited memory and/or computational power as well as understandable by human users. To reach this goal, we introduce a quantitative version of Strategy Logic with natural strategies in the setting of imperfect information. In a first step, we show how to model strategies for repeated keyword auctions and take advantage of the model for proving properties evaluating this game. In a second step, we study the logic in relation to the distinguishing power, expressivity, and model-checking complexity for strategies with and without recall.