Paul Goldberg, Nov. 2023
Notes for potential research students or collaborators. The following are some research topics that interest me. Certainly not an exhaustive list.
Generally, most of my papers suggest (explicitly or implicitly) follow-up work, so if you’re interested in the general topic of a recent paper, there may well be opportunities to explore it further.
Link to project web page for my EPSRC funded project Optimisation for Game Theory and Machine Learning.
This topic is in coorperation with colleagues at Kleros.
This is a potential topic for a DPhil student. We are interested in systems that aim to reach conclusions based on the judgements of human participants. For example, an implicit promise of Wikipedia is that diverse inputs on a topic have been received from the community, and they have been systematically combined and aggregated, resulting in a reliable coverage of topics. The project aims to mathematically model the process, including the aims and objectives of individual participants, with a view to informing the design of such systems.
Examples of such systems:
In more detail, the main starting-point is George (2023) which mentions some open problems. The paper studies mechanisms for crowdsourcing judgements of real-world scenarios, in settings where there is a ground truth, or correct answer, to be elicited. The general topic of research is voting schemes, which is a major theme of computational social choice theory. A general principle identified in the paper is that voting for the “right answer” to a question is a Schelling point, a strategy where the participant gets rewarded for being in agreement with other participants. Lesaege et al (2021) gives an overview of how Kleros aims to apply these ideas.
There is quite a wealth of research problems that could be investigated in this general line, based on models of the ground truth, and what signals are received by the participants. An intriguing concern with this general approach, is that it may be the case that the desire to agree with other participants may be in conflict with the desire to output one’s own best guess as to the right answer. This issue originates in the long-standing concept of a Keynesian beauty contest (KBC), in which participants may base their vote on their own assessment of their peers' assessment of the (subjective) beauty of the alternatives.
The project would investigate models of how the participants receive signals based on the ground truth, and analysis of where/how the KBC problem arises. The modelling may include, for example, multi-level reasoning amongst the participants about how they predict each other are likely to vote, along with the design of payoff systems, as discussed in (George 2023). (George 2023) also studies the presence of adversaries in the electorate, and the design of voting mechanisms that are resistant to those. It is likely that there are enough research issues in the adversary-free setting, but dealing with adversaries is of course of interest.
The topic is some extent a follow-up to an earlier paper I co-authored, Fixed Price Approximability of the Optimal Gain From Trade (link). A more-recent and highly relevant paper is On the Optimal Fixed-Price Mechanism in Bilateral Trade (link). There are various interesting-looking follow-up questions.
One of them is to study the setting of a buyer and seller who interact via an intermediary who wants to maximise profit (assume the intermediary knows the prior distributions of the buyer and seller’s values for the item). To what extent does the profit motive reduce the welfare of the buyer and seller? On the one hand, it should reduce welfare since the intermediary will offer a higher price to the seller than the buyer, and trade occurs if both prices are accepted, so there’s a higher risk of failure than with a welfare-maximising intermediary. On the other hand, it's in the intermediary's interest to make trade occur.
Another follow-up topic is to extent this kind of analysis to the multi-item setting, and analyse welfare-maximising mechanisms, assuming, say, that traders have decreasing marginal values for each additional item they end up with.
Wikipedia's page on the complexity class TFNP contains a diagram of the inclusions amongst the more important syntactic subclasses: CLS, PPAD, PPA, PPP, PLS. And one of many questions arising is, how many more similar complexity classes could we identify? Likely an infinite number, but what do they look like? We might focus on variants of PPP, for example problems associated with the weak pigeonhole principle seems to be a different class from problems associated with the regular pigeonhole principle. There there’s k-PPP, where the general problem is that you're given a circuit mapping kN+1 pigeons to N holes, and you want to find a k-collision (k pigeons mapping to one hole). k-PPP is a superset of (k−1)-PPP, but is it strict?
An interesting relevant recent paper: Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP (link.) Introduces “Polynomial long choice”, a generalisation of the (polynomial) pigeonhole principle (but seems to be a different generalisation from the above k-PPP). Right now, it seems that PPP gives rise to numerous variants, unlike PPAD, for which the natural-looking variants turn out to be equivalent to PPAD or PPADS.
The wikipedia page on fair cake-cutting introduces the concepts of cake-cutting protocols, and envy-freeness (along with alternative related desiderata of protocols). A well-known result of Aziz and McKenzie (cited in the wikipedia page) shows the existence of envy-free finite cake-cutting protocols for any number of players. But, their protocols are impractical due to the large number of cuts that are required.
One can define approximate envy-freeness in a natural way: a protocol is ε-envy-free if every player can ensure that his value for his own share is at most ε less that his value for anyone else’s share. One question that results is whether, for example, there is a 4-player cake-cutting protocol that is approximately envy-free while using not too many cuts. This also suggests the following computational challenge: given a cake-cutting protocol, compute that (smallest) value of of ε for which it is ε-envy-free. Example: Player 1 cuts the cake. Player 2 subdivides one of the 2 pieces. Player 3 chooses one of the 3 pieces, then player 2 chooses one of the remaining pieces, then player 1 gets the remaining piece. Notice, for example, that player 1 may end up with a piece that he values at 0, but if he initially divides the cake equally (according to his own valuation), his envy is at most 1/2.
There is (a surprising amount of) work to do in making precise the problem of computing the worst-case envy. To say what we mean by an input to the above problem, we need
Representation of protocols: The above example described a protocol in a ad-hoc manner. One general issue is whether there is a good, fully-general formal syntax for describing cake-cutting protocols, a question studied in Equivalence of Models of Cake-Cutting Protocols link. (We need to agree on such a syntax in order to make precise the problem: ‘Given a protocol, how much envy can there be in the worst case?’) Alternatively, one could focus on restricted subclasses of protocols, and investigate, for example, for what subclasses of protocols can the worst-case envy be efficiently computed. Also, note that protocols are sometimes presented in terms of queries to the players’ valuation functions (the Robertson-Webb query model), as opposed to the more abstract description used in the above example, which offers no guidance to the players about what they should do, based on their own (private) valuation functions.
Modelling how agents behave: suppose we modify the above example protocol so that after the players have taken their pieces, player 2 may donate his entire share to player 3. If player 2 is rational, he would not do so, but if “worst-case envy” allows other players to collude, then the worst-case envy for player 1 is now 1, not 1/2. That is, the concept of ‘worst-case envy’ needs to be made precise: should we allow all agents other that agent A to collude against A, or should we assume they will not sacrifice themselves in order to make things worse for A? Note that in the latter case, A may exploit the selfishness of his peers, and behave differently from how he would in a worst-case setting.
There are various follow-up questions arising from Contiguous Cake Cutting: Hardness Results and Approximation Algorithms link. The paper investigates the design of algorithms that allocate contiguous pieces to the agents, in a centralised setting where the valuation functions are all given, so there are no strategic issues of how players play against each other. The main question is to identify the computational complexity of envy-free allocations of contiguous pieces, for which there is a non-constructive proof of existence. A more specialised, but probably more tractable question is whether there is an improved algorithm that improves on the approximation guarantee of algorithms given in the paper? In particular, can we find a polynomial-time algorithm that obtains an improved approximation ratio?