Analysing Strategic Agents in Fair Division and Games of Identical Interest

We study strategic autonomous agents who aim to maximise their utility. Strategic agents, however, only have finite computational resources. As such, we seek to design efficient algorithms for them or prove that no such algorithms exist. This work is in the field of Algorithmic Game Theory and more generally in Computational Complexity. We consider two settings in particular:

- Fair Division - Games of Identical Interest

Fair Division is of interest as it is a very natural setting with limited work on strategic agents. Games of Identical Interest are interesting because we can encode optimisation problems as games. Results in optimisation carry over to Games of Identical Interest and vice versa.

Fair division studies mechanisms for dividing common resources among multiple agents. The aim is to divide resources in a way that agents receive what they believe they are entitled to. A special case of fair division is that of cake cutting.

Here, we divide a linear "cake" among n agents. We represent the cake as the closed interval [0, 1] and each agent has their own valuation of different subsets of the cake. We can phrase diverse problems in the simple language of cake cutting.

For example, sharing a family home during the holidays and assigning CPU time to different processes in an operating system. We want to assign the "cake" fairly. The strongest notion of fairness is that of envy-freeness: no agent prefers the pieces of another agent to their own.

We consider agents which are strategic. Research in Fair Division often assumes that agents report their truthful preferences. However, strategic agents might misrepresent their true valuations.

In strategic cake-cutting we design mechanisms where being truthful is a dominant strategy, while still maintaining some fairness guarantees. There is a result that for restricted valuation functions, there is a truthful mechanism for two agents that is envy-free. We aim to modify this mechanism and develop one for three or more agents.

Fair division is also concerned with dividing indivisible goods. A concrete example is that of family members dividing an inheritance that consists of indivisible goods such as a house and cars. One natural algorithm for dividing common goods is round-robin.

In round-robin, agents sequentially pick items. As soon as an agent picks an item, it is unavailable to other agents and agents must pick from the rest. In this setting, strategic agents do not need to act truthfully.

A strategic agent might pick a less preferred item if another agent will imminently pick this item. However, computing the optimal strategy for a strategic agent seems computationally hard. We conjecture that there is no efficient algorithm that returns a strategy for an agent and so we aim to prove that this problem is PSPACE-hard.

A separate thread of research is analysing games. A specific subcase of interest is polymatrix games of identical interest. Here, all agents receive equal payoff, so agents are searching for the actions that will lead to an optimum.

Here, the language of games and optimisation meets as finding a local optimum is equivalent to finding a pure Nash equilibrium. Finding a pure Nash Equilibrium in games of identical interest is computationally hard. However, the complexity of finding a mixed Nash Equilibrium is an open question.

We aim to determine the complexity of finding a mixed Nash Equilibrium for polymatrix games. A result for these games will carry over to an open problem for optimising quadratic programs.

Answering the above open questions will improve our understanding of computationally constrained autonomous agents in diverse settings. This project falls within the EPSRC Artificial intelligence technologies research area