Mobile geo-location advertising, where mobile ads are targeted based on a user’s location, has been identified as a key growth factor for the mobile market. As with online advertising, a crucial ingredient for their success is the development of effective economic mechanisms. An important difference is that mobile ads are shown sequentially over time and information about the user can be learned based on their movements. Furthermore, ads need to be shown selectively to prevent ad fatigue. To this end, we introduce, for the first time, a user model and suitable economic mechanisms which take these factors into account. Specifically, we design two truthful mechanisms which produce an advertisement plan based on the user’s movements. One mechanism is allocatively efficient, but requires exponential compute time in the worst case. The other requires polynomial time, but is not allocatively efficient. Finally, we experimentally evaluate the trade off between compute time and efficiency of our mechanisms.

Strong Nash equilibrium (SNE) is an appealing solution concept when rational agents can form coalitions. A strategy profile is an SNE if no coalition of agents can benefit by deviating. We present the first general-purpose algorithms for SNE finding in games with more than two agents. An SNE must simultaneously be a Nash equilibrium (NE) and the optimal solution of multiple non-convex optimization problems. This makes even the derivation of necessary and sufficient mathematical equilibrium constraints difficult. We show that forcing an SNE to be resilient only to pure-strategy deviations by coalitions, unlike for NEs, is only a necessary condition here. Second, we show that the application of Karush-Kuhn-Tucker conditions leads to another set of necessary conditions that are not sufficient. Third, we show that forcing the Pareto efficiency of an SNE for each coalition with respect to coalition correlated strategies is sufficient but not necessary. We then develop a tree search algorithm for SNE finding. At each node, it calls an oracle to suggest a candidate SNE and then verifies the candidate. We show that our new necessary conditions can be leveraged to make the oracle more powerful. Experiments validate the overall approach and show that the new conditions significantly reduce search tree size compared to using NE conditions alone.