Infinite Game Solver

Computing Best-Response Strategies in Infinite Games of Incomplete Information

Abstract

We describe an algorithm for computing best-response strategies in a class of two-player infinite games of incomplete information, defined by payoffs piecewise linear in agents' types and actions, conditional on linear comparisons of agents' actions. We show that this class includes many well-known games including a variety of auctions and a novel allocation game. In some cases, the best-response algorithm can be iterated to compute Bayes-Nash equilibria. We demonstrate the efficacy of our approach on existing and new games.

Full version: reeves.pdf -- reeves.ps -- 2004-05-24 21:40:29

DEXTER Paper (internal access only)

Slides: reeves.ppt (poster version)

Source code: bestResp.nb, bestResp2.nb, Equilibria.m, supplyChainGame.nb, Util.m

Best Response Finder -- Beta Version

Parameterized Payoff Function, Piecewise Uniform Type Distribution, and Piecewise Linear Strategies:

(* Canonical Games *)

fpsb = {{0,1/2,1}, {0,-1/2,-1}, {0,0,0}, {0,0,0}, {0,0,0}, {0,0}, -1};

vickreyAuction = {{0,1/2,1}, {0,0,0}, {0,0,0}, {0,-1/2,-1}, {0,0,0}, {0,0}, -1};

(* KPSB generalizes FPSB and Vickrey.  k = 0 is FPSB; k = 1 is Vickrey. *)
kpsb[k_] := {{0,1/2,1}, {0,(k-1)/2,k-1},{0,0,0},{0,-k/2,-k},{0,0,0},{0,0},-1}

sharedGoodAuction = {{0,1/2,1}, {0,-1/4,-1/2}, {0,0,0}, {1/2,1/4,0}, {0,0,0}, {0
,0}, -1};

allPayAuction = {{0,1/2,1}, {-1,-1,-1}, {0,0,0}, {0,0,0}, {0,0,0}, {0,0}, -1};

v = (10 - 5^(1/2))/5;   (* parameter for the Supply Chain Game *)
scAuction := {{-1,-1,0}, {1,1,0}, {0,0,0}, {0,0,0}, {0,0,0}, {v,v}, 1};

cost = 1;   (* parameter for the Joint Purchase Auction *)
jointBuy := {{0,1}, {0,-1/2}, {0,0}, {0,1/2}, {0,-cost/2}, {cost}, 1};

bargSeller = {{-1, 0}, {1/2, 0}, {0, 0}, {1/2, 0}, {0, 0}, {0}, -1};
bargBuyer = {{0, 1}, {0, -1/2}, {0, 0}, {0, -1/2}, {0, 0}, {0}, -1};

(* Canonical Type Distributions *)

uniformTypes = {{0,1},{1}};

(* Canonical Strategies *)

truthfulBidding = {{}, {1}, {0}};

(***********************************************************************
Above is for convenience of defining typical games;
Below are the only lines necessary, giving the payoff functions,
 type distributions, and seed strategies for each player.
GAME gives the utility function parameters for the 2 agents (see
  equation 2.1 and table 2.1 on pages 8 and 10 of my thesis).
  For a symmetric game this will be a pair of identical parameter lists
  for the two agents.
TYPES gives the piecewise uniform type distributions for the two agents
  (again, in a symmetric game, these will be identical).  An agent's
  type is represented by {d,f} where d is a list of the boundary points
  and f is a list of the pdf values.  (See appendix A.1 on page 121 of
  my thesis.)
STRATS are the initial seed strategies for the two agents.  A strategy
  is specified by {c,m,b}.  (See equation 2.2 on page 9 of my thesis.)
************************************************************************)

cmpr = {{0,1}, {0,-1}, {0,0}, {0,1}, {1/2,0}, {1}, 1};

GAME = {cmpr,cmpr};
TYPES = {uniformTypes,uniformTypes};
STRATS = {truthfulBidding,truthfulBidding};
STRATS = {{{0, 53/27, 175/54}, {1/3, 0, 1/3, 0}, {-61/162, 5/18, -61/162, 19/27}}, {{0, 53/27, 175/54}, {1/3, 0, 1/3, 0}, {-61/162, 5/18, -61/162, 19/27}}};

Iterations:

Daniel Reeves