Tropical geometry and auction theory
Auction theory is a branch of economics dealing with the behavior of agents in auction markets, and tropical geometry is a branch of mathematics dealing with the geometry of convex piecewise linear functions with close connections to algebraic geometry, nonarchimedean fields, and number theory. This project will investigate questions related to a recent paper of Baldwin and Klemperer, which introduced a new approach to analyzing demand structures for mixed product auctions using a duality between Newton subdivisions in demand space and tropical hypersurfaces in price space. Potential directions to explore will include the incentives facing bidders in Klemperer’s product mix auctions and efficient computation of equilibria for these auctions, via methods from tropical geometry.
Bidding games: auction structures and multiplayer variations
Bidding games combine aspects of combinatorial games and economic games by having players bid for the right to move next, instead of alternating moves, while playing a traditional two player game such as tic-tac-toe, connect four, or chess. The goal, of course, is to win the game, but the optimal strategies change wildly when one player can potentially make several moves in a row. Traditional bidding games via first price auction, where both players bid and then the high bidder pays and makes a move, are relatively well studied, but even minor variations on this structure are largely unexplored. Participants in this project may explore bidding versions of multiplayer games, strategies and structure theory for bidding games with different auction structures, such as all-pay bidding, or variations in which players can bid on different packages of moves.
Cones of divisors
In our calculus classes we frequently use the geometry of curves and surfaces defined by polynomials to get insight into the solutions to given problems. In algebraic geometry we study higher dimensional generalizations of these curves and surfaces in search of geometric insight that can be applied to theoretical mathematics as well as to physics, engineering and computer science. Studying these higher dimensional analogs of curves and surfaces requires careful study of several invariants, one of which is called the cone of divisors. It turns out that elementary arguments together with some good intuition and creativity can lead to the description of some unknown cones of divisors of interesting geometric objects. This project involves extensive use of computational linear algebra, while the required basic algebraic geometry can be learned during SUMRY.
Mastermind, Hidden Permutations, and MTV’s Are You the One?
In the classic board game Mastermind there are two players, the codemaker and the codebreaker. The codemaker chooses a secret string of four colors chosen from a list of six possible colors. Each turn, the codebreaker gets to guess some string of four colors and is told how many of her guesses are the correct color in the correct position and how many are the correct color but in the incorrect position. In 1976 Knuth used a computer to show that the codebreaker has a strategy that is guaranteed to find the secret string within five turns. Since then many authors have analyzed extensions and variations of this game.
Suppose you have two groups of n elements {x_1, x_2, …, x_n} and {y_1, y_2, … , y_n}, and there is a secret matching between these two groups. That is, each x_i is matched with a unique y_j. Each turn you are allowed to submit a possible matching and are told how many of your matches are correct, but not which matches are correct. How many turns should it take to find this hidden matching?
These questions seem artificial at first but have proven useful in applications to DNA sequencing and information security. A completely different application comes from the MTV game show Are You the One?, currently in its second season. Ten men and ten women are secretly matched together and must uncover this hidden matching in order to split a million dollar prize. This summer we plan to investigate several Mastermindand hidden permutation problems and to determine whether there exists a winning strategy for Are You the One?
Counting Arcs in the Projective Plane
Consider a regular m by m grid. How many collections are there of n points, no three of which lie on a line? Such a collection is called an n-arc. This problem turns out to lead to some very interesting questions when we move from a regular grid in the plane to the finite projective plane P^2(Z/p Z). For each prime p we construct this finite projective plane by considering all triples (x,y,z) in (Z/p Z)^3 - (0,0,0), but where we identify (x,y,z) with (a x, a y, a z) for any nonzero a in Z/p Z. We see that the finite projective plane has (p^3-1)/(p-1) = p^2+p+1 total points.
It is known that the number of 6-arcs in P^2(Z/p Z) is:
1/720 * (p^2+p+1)*(p^2+p)*p^2*(p-1)^2*(p-2)*(p-3)*(p^2-9p+21).
There is also a formula like this for 7-arcs when p is odd. When counting 8-arcs the formula is similar, but depends on the value of p modulo 3.
It seems very likely that once we count n-arcs for n at least 10 something completely new begins to happen. This formula is currently unknown, and it should not be given by something as simple as a polynomial. Instead, complicated number-theoretic objects like elliptic curves and modular forms should start to enter the picture. This summer, we hope to give a complete formula for the number of 9-arcs in P^2(Z/p Z) and investigate some of the mysterious new behavior that occurs for 10 or more points. This project will draw on techniques from group theory, combinatorics and graph theory, and number theory.
Counting Subrings of Finite Rings
Given a finite abelian group G we can ask how many distinct subgroups it contains of each index n. This is not so difficult to answer, but if we ask try to ask the same question for subrings of a finite ring the situation is much more complicated. More specifically, let G = Z/p^k Z and consider the ring R given by the polynomial ring G[X] modulo the ideal generated by some polynomial f(X) in G[X] of degree n.
How does the factorization of f(X) in G[X] affect the total number of subrings of R? There is a natural guess. If f(X) is the product of n distinct linear factors, then this ring will have `as many subrings as possible.’
These types of questions have interesting applications to difficult counting problems in number theory. We plan to investigate these types of questions for small values of n and to see whether we can apply them to prove results about zeta functions of infinite rings. This project will involve lots of explicit examples and will be driven by concrete calculations.