I've been working on simulating a market with small numbers of mutually-exclusive sellers and buyers, where each individual can only ever enter one transaction. In pursuing this, I've been trying to figure out if the following game has Nash equilibria, and if so, how to find them:
- There is a market with two mutually-exclusive groups: $N$ sellers $(S_1, ..., S_N)$ of a product and $M$ buyers $(B_1, ... B_M)$ of a product.
- The sellers and buyers can enter deals with each other, where the seller sells the product to the buyer for an agreed upon price. Each seller can only sell to one buyer, and vice versa. Not everyone needs to enter a deal.
- Each seller wants to enter a deal that maximizes their price, while each buyer wants to enter a deal that minimizes it. Each seller also, furthermore, has a publicly-known minimum price they are willing to accept $(P_{S1}, P_{S2}, ..., P_{SN})$, and each buyer has a publicly-known maximum price $(P_{B1}, P_{B2}, ..., P_{BM})$ they are willing to accept. For convenience, let's suppose the sellers are ordered such that $P_{Si} \leq P_{S(i+1)}$ and the buyers are ordered such that $P_{Bj} \geq P_{B(j+1)}$, such that they each go from having the most to least options in the prices they are able to accept.
Equilibrium would be attained in seller-buyer matchings where nobody could offer a better deal to someone else without worsening their own position. I'm pretty sure an equilibrium always exists, but I can't figure out an algorithm to reliably find them.
What I've tried:
I've played around with $N = 1$ or $M = 1$ scenarios, which seem to be simple enough:
- When $N = 1$, the solitary seller $S_1$ will sell to $B_1$ for a price between $P_{S1}$ and $P_{B2}$, unless $P_{S1} > P_{B1}$, in which case there would be no deal.
- When $M = 1$, the solitary buyer $B_1$ will buy from $S_1$ for a price between $P_{S2}$ and $P_{B1}$, unless $P_{S1} > P_{B1}$, in which case there would be no deal.
I feel like there's gotta be a solution where either I can (1) recursively decompose problems with larger $N$ and $M$ into smaller sub-problems with smaller $N$s and $M$s, or (2) have some kind of converging algorithm where I start off with no deals, then run multiple rounds where sellers and buyers offer each other better deals than they had the last round until we reach some steady state. I can't quite figure out either, though, and I have no idea how I would go around proving it works. Any help would be appreciated!