Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

Unit-sphere games

  • Original Paper
  • Published:
International Journal of Game Theory Aims and scope Submit manuscript

Abstract

This paper introduces a class of games, called unit-sphere games, in which strategies are real vectors with unit 2-norms (or, on a unit-sphere). As a result, they should no longer be interpreted as probability distributions over actions, but rather be thought of as allocations of one unit of resource to actions and the payoff effect on each action is proportional to the square root of the amount of resource allocated to that action. The new definition generates a number of interesting consequences. We first characterize the sufficient and necessary condition under which a two-player unit-sphere game has a Nash equilibrium. The characterization reduces solving a unit-sphere game to finding all eigenvalues and eigenvectors of the product matrix of individual payoff matrices. For any unit-sphere game with non-negative payoff matrices, there always exists a unique Nash equilibrium; furthermore, the unique equilibrium is efficiently reachable via Cournot adjustment. In addition, we show that any equilibrium in positive unit-sphere games corresponds to approximate equilibria in the corresponding normal-form games. Analogous but weaker results are obtained in n-player unit-sphere games.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

Notes

  1. According to certain existing empirical evaluations (see Agarwal et al. 2011), the CTR of an ad link is concave in payment, where the degree of concavity depends on the keyword length. In our example, the CTR is proportional to the square root of the money spent, which is one special and commonly used concave function. In fact, it is standard to assume that the cost of a certain amount of “effort” e (e.g., CTR in our example) is proportional to \(e^2\). See Holmstrom and Milgrom (1987), Hauser et al. (1994), Lafontaine and Slade (1996) and Hu et al. (2015).

  2. In cases where \(Ay = 0\) (resp. \(Bx = 0\)), one may set \(\alpha \) (resp. \(\beta \)) arbitrarily.

  3. We say a matrix \(A > 0\) if \(A_{ij} > 0\) for all (ij), and a vector \(x \ge 0\) if \(x_i \ge 0\) for all i.

  4. Recall that \(\rho (AB) = \rho (BA)\).

  5. Linear convergence is another way of saying the error diminishes exponentially fast in the number of iterations.

  6. A multiplicative k-approximate MSNE denotes a strategy profile where no player can improve her utility by k times via deviation.

References

  • Agarwal A, Hosanagar K, Smith MD (2011) Location, location, location: an analysis of profitability of position in online advertising markets. J Market Res 48(6):1057–1073

    Article  Google Scholar 

  • Berman A, Plemmons RJ (1979) Nonnegative matrices in the mathematical sciences. Academic Press, London

  • Chang KC, Pearson Kelly J, Zhang Tan (2013) Some variational principles for z-eigenvalues of nonnegative tensors. Linear Algebra Appl 438(11):4166–4182

    Article  Google Scholar 

  • Chen X, Deng X (2006) Settling the complexity of two-player nash equilibrium. FOCS 6:261–272

    Google Scholar 

  • Fiat A, Papadimitriou CH (2010) When the players are not expectation maximizers. In: Algorithmic game theory—third international symposium, SAGT 2010, Athens, Greece, October 18–20, 2010. Proceedings, pp 1–14

  • Hauser JR, Simester DI, Wernerfelt B (1994) Customer satisfaction incentives. Market Sci 13(4):327–350

    Article  Google Scholar 

  • Holmstron B, Milgrom P (1987) Aggregation and linearity in the provision of intertemporal incentives. Econometr J Econ Soc 55(2):303–328

  • Hu Y, Shin J, Tang Z (2015) Incentive problems in performance-based online advertising pricing: cost per click vs. cost per action. Manag Sci 62(7):2022–2038

  • Kolda TG, Mayo JR (2011) Shifted power method for computing tensor eigenpairs. SIAM J Matrix Anal Appl 32(4):1095–1124

    Article  Google Scholar 

  • Lafontaine F, Slade ME (1996) Retail contracting and costly monitoring: theory and evidence. Eur Econ Rev 40(3):923–932

    Article  Google Scholar 

  • Li W, Ng MK (2014) On the limiting probability distribution of a transition probability tensor. Linear Multilinear Algebra 62(3):362–385

    Article  Google Scholar 

  • Mises RV, Pollaczek-Geiringer H (1929) Praktische verfahren der gleichungsauflösung. ZAMM J Appl Math Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik 9(1):58–77

    Article  Google Scholar 

  • Roberson B (2006) The colonel blotto game. Econ Theory 29(1):1–24

    Article  Google Scholar 

  • Sorensen DC (2002) Numerical methods for large eigenvalue problems. Acta Numerica 11:519–584

    Article  Google Scholar 

Download references

Acknowledgements

We are grateful to Andrew Yao for helpful discussions. Part of this work is done while Pingzhong Tang was visiting Simons institute at UC Berkeley. This work was supported by the National Basic Research Program of China Grant 2011CBA00300, 2011CBA00301, the Natural Science Foundation of China Grant 61033001, 61361136003, 61303077, 61561146398, a Tsinghua Initiative Scientific Research Grant and a China Youth 1000-talent program.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Pingzhong Tang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tang, P., Zhang, H. Unit-sphere games. Int J Game Theory 46, 957–974 (2017). https://doi.org/10.1007/s00182-017-0565-y

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00182-017-0565-y

Keywords

Navigation