This is the experimental HTML rendering of capstract:2611.00015v1. The PDF is the version of record.

Recovering Duty Rotations from Group Portraits

Daria Velcetti
Distributed Systems Unit, Valdessa Institute of Informatics
Turin, Italy
Nalini V. Edamar
Department of Computational Social Science, Kelmeri College of Technology
Pune, India
Kohei T. Hinase
Laboratory for Cooperative Systems, Natsuhara Graduate Institute
Kobe, Japan

Abstract

We consider a team that rotates the work of documenting a journey and retains the photographs after discarding the duty sheet. In a conventional group portrait the individual who performed the work is absent from the result. We ask when these omissions suffice to recover the rotation. Each stop contributes a set of possible photographers, and the one-turn-per-person agreement supplies a matching constraint across stops. For independent visibility errors we give the exact probability that a complete album identifies a single rotation. With eight travelers, two exposures per stop and a bystander omission probability of one quarter per exposure, 2.69% of albums identify every photographer from the corresponding stop alone. Joint decoding resolves 87.28%. This improvement depends on prior knowledge that the agreement was kept. In a four-person excursion with one unrecorded substitution, 12.73% of two-exposure albums uniquely identify a rotation that never occurred. We give a separate return value for assignments that require the agreement and examine the changes in the observation model required for mirror portraits, self-timers and pictures taken by a ninth person.

CCS Concepts• Computing methodologies → Multi-agent systems; • Mathematics of computing → Graph algorithms.

Keywordsmultiagent coordination, task allocation, partial observability, group photography, bipartite matching

Reference Format:
Daria Velcetti, Nalini V. Edamar, and Kohei T. Hinase. 2026. Recovering Duty Rotations from Group Portraits. Preprint, November 9, 2026.

1Introduction

On a journey with one camera, a member of the party periodically steps out of the group to make the record. A common arrangement is to take turns. If the turn list survives, the pictures can be sorted by maker from the list. If only the album survives, there is still information about who did the work. Every traveler visible in an ordinary forward-facing photograph can be excused from having taken it.

The problem arose in indexing a collection of excursion photographs for which families supplied fairly complete lists of the travelers and almost no photographer credits. One donor could remember the rule for passing the camera but could no longer remember who took it first. A captioning scheme that accepts the best face match has no entry for the member with the strongest claim to a credit. That person usually has no face in the image. Even a perfect list of the visible people need not identify the maker, since a second traveler may be behind somebody or out of frame. There is some value in looking at the next photograph before assigning credit for the first.

We study the inference available to a team which lacks a separate recorder. Each participant sees the same album at the end of a circuit. They know the membership of the party and which exposures were made at the same stop. Nobody supplies testimony as to who held the camera. The team wants either an assignment that follows from the record and its rotation agreement, or a precise account of the credits that remain open. In particular a deterministic vote for one of two interchangeable names at every handset would give agreement without settling the question.

Our results concern the information content of a particular record. Recording the operator at handoff would settle this question more cheaply. Ownership of a camera is a poor substitute for such a byline on an excursion where the owner hands it around [12]. We first derive the recovery probability for a circuit in which the rotation was honored. We then feed the same decoder a circuit which quietly doubled one person’s turn. The latter calculation sets a limit on how the resulting credits can be used to settle accounts.

2Prior work and the allocation contract

Models of cooperative task allocation usually give each agent a cost or a capacity and ask for an assignment before execution [4, 16, 21]. Here the participants have made their agreement in advance. They have even completed the work. A subsequent allocation of credit must refer to that execution. Minimizing the discomfort of the proposed rotation would amount to inserting a preference about what the party ought to have done. A minimum-cost assignment solver [8] would be entirely capable of making this mistake if given plausible preferences for spending a turn behind the camera.

Our evidence consists of positive sightings that rule out assignments. Multiple observations of an individual can be combined by set union. This permits agents to exchange partial catalogs without agreeing on the order in which the observations arrived [9, 11]. An independent issue is whether the same event identifier has been assigned to two photographs. Work on reconstructing shared event sequences uses landmarks and local time stamps for this purpose [20]. We assume event identifiers have been settled before attribution starts. One picture of a fountain on the outward journey and another on the return can have different makers even if the dates were lost and the fountain is unchanged.

The constraint model is an instance of all-different reasoning [2, 13]. An agent faces two kinds of uncertainty. Its local evidence may rule out some names for its own print. The one-turn quota may remove more names once other prints are in the catalog. We use a perfect matching for the second operation [5, 10], keeping the local candidate list as a separate return value. Group catalogs that collapse these two values to a single credit lose the means to revise the credit after a late change to the roster [1]. In the photographic literature a missing family member is often discussed as a choice of the person composing the frame [3]. Here the mechanism of interest is that the member composing the frame is missing.

3Camera service

There are people and stops, with . One camera is active. At stop it remains in one person’s hands for exposures. Let be this operator and let be the set of roster members positively identified in exposure . A turn pays one unit of service regardless of the number of exposures. The circuit agreement says that is a permutation of the roster. It does not prescribe an order. A rigid clockwise handoff with a known initial operator would settle all credits even with the lens cap on. We have in mind the less formal arrangement in which everybody is expected to do it once.

A stop has a single working side of the camera. No self-timer is in use, the shutter is operated by hand and the operator does not appear in a reflecting surface. Under these conditions for every . A picture containing four faces from a six-person roster therefore carries four exclusions. A partly seen traveler can be left unmarked. An uncertain identification entered as certain has a different effect and falls outside this one-sided observation model. The unit of identification is the person: a reflection of somebody standing in the group does not yield two exclusions.

Write for the roster and define

The sets in Eq. (1) have concrete archival interpretations. The first is the set of people who cannot be seen at a stop in any deposited exposure. The second is the set of complete bylines that the album could carry if turns were distributed according to the agreement. If it is empty, the catalog carries an exception. If it contains at least two permutations, listing the common assignments is permissible. Printing one whole permutation as the byline would erase the uncertainty. Our primary endpoint is the event that the set contains exactly one permutation in a circuit that actually followed a permutation.

3.1Exchange among members

Each participant can mark positive sightings privately and send just pairs of stop and person identifiers to the others. Duplicate pairs can be discarded. Once each member has announced completion of its list, exchange over a connected set of reliable channels yields the same union at each member, under eventual delivery. Completion requires knowledge of which list versions have arrived. A bare count of sightings does not establish this condition. With an album already present at each member, the same operation can be performed by one cataloger and the masks redistributed. Neither method transmits an operator’s name as evidence of service.

This contract gives the decoder a distinctly retrospective role. A traveler does not have to obtain a quorum before pressing the shutter. All group members may be in quite ordinary agreement about who has the camera at the time and unable to retrieve that knowledge six months later. A participant who retains a personal turn log could supply it as one more constraint. We exclude such reports in the calculations because the amount of photographic evidence needed would then depend on whose notebook happened to survive.

4Decoding the album

Construct a bipartite graph with stops on the left and people on the right. Edge is present when . Find a maximum-cardinality matching [6]. Failure to cover all stops gives a certificate in the form of a set of stops whose combined candidate list is too small. This follows from Hall’s condition. For example, two photographs each containing everyone except the same person cannot be credited to different operators if every member was present and the photographs belong to different stops.

Given a perfect matching , contract its edges to vertices and draw a directed arc from to when the operator assigned by at is also a candidate at , for . We will use the following familiar characterization of uniqueness [10].

Proposition 1 (Circuit ambiguity). A second complete set of credits exists if and only if the contracted graph has a directed cycle. A matched credit can change in another complete assignment exactly when its vertex belongs to a directed cycle.

Proof. Along a cycle each stop can be assigned the operator at the next vertex. All affected names remain distinct and every new assignment has a candidate edge. Conversely, comparing two permutations yields disjoint cycles on the positions where they differ. Each successor in such a cycle supplies an admissible candidate at the preceding stop.∎

Strongly connected components identify the credits that can move in time linear in the size of the constructed graph [17]. We report a local credit if is a singleton. A singleton component of the contracted graph with a larger local list gives a credit conditional on the circuit agreement. Components of size two or more mark unresolved credits. There are no self-loops in our convention. Construction and a maximum matching dominate the cost, after masks have been combined, where . The initial arbitrary choice of cannot change which stops receive a fixed credit, since by Proposition 1 that property is defined over all complete assignments.

Consider four travelers , in actual duty order . The respective candidate lists are . Only the last print can be credited locally. Once it is assigned, the third print must belong to . This in turn settles the first two prints. If the last list is changed to , all four prints become uncreditable individually under the agreement. There are precisely two full rotations, even though every print now has the same number of candidates. The decisive sighting in this example would be one of at the last stop. It would settle the bylines on the entire outing, including pictures made before that sighting.

5Recovery probability

In the reference channel, each nonoperator at each exposure is independently omitted with probability . These are section parameters, not estimates of the visibility of tourists. The party stands again for each exposure. An extra candidate survives at a stop with probability . Relabel people by the stops at which they actually served. The diagonal edges of the matching graph are then certain, and every off-diagonal edge is present independently with probability . We can contract the true matching for purposes of counting, although the agents running the decoder do not have it. Conditional recovery is the probability of acyclicity of this directed random graph.

The classical sink recurrence for counting labeled acyclic digraphs [14] admits a weighted form. Set . For ,

To see Eq. (2), choose vertices and insist they are sinks. Their outgoing arcs must be missing. With these arcs fixed absent, acyclicity is decided by the remaining vertices. Arcs from those vertices into a chosen sink are unrestricted. Inclusion-exclusion over the choice of sinks counts each acyclic graph once because every finite nonempty acyclic graph has at least one sink. Appendix A describes checks on the implementation. This argument concerns finite circuits. It needs no assumption about how rosters grow with the number of trips.

Local decoding succeeds on a full circuit with probability . Figure 1 compares this criterion with Eq. (2) at . The steep rise between exposures one and two under joint decoding can be understood from two-person exchanges. Their expected number is , already 1.75 at and . Longer exchanges also matter at this setting. It would be inaccurate to identify the chance of ambiguity with the expected number of pairs.

0.00.20.40.60.81.01234Exposures per stopWhole-album recoveryWith rotationLocal lists
Figure 1: Exact probability of recovering all eight credits. Each exposure has independent bystander omissions with probability one quarter.

Table 1 varies party size at fixed exposure count. A ten-person tour has ninety chances to leave a nonoperator out of both pictures at a stop. It is quite usual for at least one byline to depend on somebody else’s photographs. Whether there are ten pictures or twenty on the return journey matters because it changes the chance of leaving two people able to trade a pair of turns. We count every album once, including albums with so many uncertain portraits that none would ordinarily be submitted for individual credits.

Table 1: Complete recovery at two exposures per stop and . Entries are probabilities under the reference channel.
Travelers Possible extra edges Local With rotation
4 12 0.46095 0.97515
6 30 0.14426 0.93463
8 56 0.02694 0.87282
10 90 0.00300 0.78960
12 132 0.00020 0.68724

5.1Fixed positions within a stop

Burst shooting supplies several exposures without necessarily supplying several views. A shorter traveler immediately behind a taller traveler in the first picture may remain there for the rest of the strip [15]. In a second channel we give every nonoperator a probability of being concealed throughout one arrangement. Among those available to be seen, omission on individual exposures still has probability . A new arrangement independently redraws the concealed set. So do the different stops. With arrangements of exposures each, the marginal extra-edge probability is

Here concealment decisions are independent across people. Under that condition Eq. (2) remains exact with the substitution in Eq. (3). At and the four-exposure comparison in Figure 2 makes a practical distinction between asking the subjects to stay exactly as they are and having them stand again. Four shutter releases in one arrangement resolve 66.30% of circuits. Spending the same releases on two pairs of pictures resolves 98.18% when the pair boundaries correspond to actual rearrangements. The difference is smaller if people consistently return to the same positions across arrangements. Our calculations assign no statistical independence to files merely because their names differ.

0.00.20.40.60.81.02468Exposures per stopWhole-album recoveryOne arrangementNew pose each time
Figure 2: Recovery for eight travelers by exposure budget and number of arrangements. Each extra arrangement redraws persistent concealment.

One should be careful about the asymptote in Figure 2. With only one arrangement at a stop, arbitrarily many exposures leave a limiting extra-edge probability . This is a bound on what changing shutter frequency can achieve in the model. An album editor who drops all but the best composed frame from a stop changes the distribution again. A frame that is slightly blurred can be the only one showing a particular traveler’s sleeve and name badge, and hence the only evidence that the traveler was off duty.

6Substitution and the limits of a duty credit

Suppose four people agreed to take one turn each. The actual operators are in that order. The turn agreed to perform was covered by . A regular rotation is impossible in the underlying history. It can, nevertheless, be the sole history admitted by the decoder. At the second stop let be outside the frame on every exposure. Let all other nonoperators be visible at least once at each stop. The lists become . The inferred assignment is with no remaining ambiguity. The picture credited to was taken by . All the positive sightings on which this credit rests are accurate.

We evaluated this failure by enumerating the possible extra-edge masks in the four-person example. For each mask, all 24 permutations were tested against the lists. The mask with additional missing bystanders has probability . Table 2 partitions its total probability according to the number of feasible credits for the entire circuit. No interval estimates are required for this finite summation.

Table 2: Audit outcomes when the actual duty list is . Values are percentages under independent omissions, rounded separately.
Exposures per stop Infeasible One fair account Several fair accounts
1 43.321 33.093 23.587
2 86.497 12.726 0.777
3 96.804 3.165 0.030
4 99.214 0.784 0.002

The single-account column in Table 2 is a joint frequency over all substituted trips. Conditioning on the catalog accepting the trip changes its interpretation considerably. With two exposures, roughly 94% of accepted substituted trips have just one feasible rotation. A curator seeking well-documented examples of an equal division of labor could, by retaining only albums that give one complete rotation, preserve a sizable share of the evidence of unequal labor under the wrong attribution. The comparison with trips that kept the agreement is given in Figure 3. These conditional frequencies do not supply a posterior probability that a particular trip had a substitute. That probability would also require a prevalence for substitutions and a model for the substitution pattern.

0.00.20.40.60.81.01234Exposures per stopSingle-account probabilityAgreement keptOne substitution
Figure 3: Probability of a single feasible rotation for four travelers, by actual allocation of camera service.

A traveler can legitimately use a local singleton as evidence of making the picture under the camera and roster assumptions in Section 3. Errors of quota compliance cannot change this inference. A credit that requires the other travelers to have discharged their obligations is necessarily a weaker entry. A catalog export that marks both entries simply as photographer cannot later be used to establish that a participant discharged an obligation. This defect persists when every member’s software agrees on the export. We use separate provenance for the two entries, following earlier work on recoverable labeling decisions in small collections [7].

7Exceptions to the observation model

An album assembled by travelers occasionally includes a portrait made by a passerby. When all are visible the candidate list is empty and the exception is easy to detect. If one traveler has stepped outside the frame, the same photograph may constitute a local singleton for a person who did no work. Extending the roster with an outside operator for that stop restores a feasible assignment but leaves no basis for individual credit to any particular passerby. A stranger taking the entire series has the useful property of documenting every participant at every stop. Those prints carry no evidence that the camera circulated at all.

A polished window presents the converse difficulty. Its reflection can show the operator holding the camera in an otherwise conventional group portrait. A positive identification of that person would delete a true edge. In a manual catalog one can distinguish the reflected operator by reference to the visible camera and treat that patch as an operator observation, a constraint stronger than any inferred absence. This requires an optical interpretation of the picture. A reflected person merely standing behind the operator would supply no such byline. Images labeled only with a bag of names cannot be repaired by unconditionally removing one name at random. Work on catalogs with separate image and depiction records makes a similar distinction for pictures of photographs [19].

The ownership of a self-timer picture is a further contractual matter. One member may carry the tripod, a second choose the viewpoint, and a third press the button and run into the frame. A duty defined as pressing the shutter occurred before the exposure and might best be recorded with a log at the camera. A duty defined as staying behind has no incumbent on that stop. Adding the tripod as a roster member would charge it a turn and impose an obligation to participate as a subject at the remaining stops. The current contract cannot express either interpretation. We retain these photographs in the album but leave them outside circuits on which this decoder is applied.

Table 3: Evidence needed to enter an observation in the camera-service model. An exceptional frame can be identified without necessarily identifying its maker.
Condition Consequence for a credit
Camera held by one roster member throughout stop A visible direct subject can be excluded
Passerby operated camera No roster member served on that exposure
Operator visible in mirror Identification as a subject can delete the true credit
Timer release Presence at exposure does not exclude shutter service
Mid-stop handoff Union across exposures can exclude both operators

Timing matters in the last row of Table 3. A reciprocal pair of pictures is often filed as a single group portrait because the two pictures, taken together, show everybody. The union then tells the decoder that nobody made it. Re-segmenting the pair as separate turns can restore a well-formed record. Such segmentation requires some independent indication of a handoff, for example two original captions naming different operators. Splitting a stop each time the decoder finds a contradiction would allow the quota to determine the very evidence on which it is supposed to be checked.

8Discussion

Our channel parameters describe omission and persistent concealment separately, two quantities a small collection is unlikely to estimate without external turn logs. The ideal test collection would record the operator on an independent sheet and retain the full strip from each stop, including empty frames. Estimating from the number of faces missing in final prints would confound a mechanical omission with the operator’s necessary absence. Estimating it only on trips for which matching recovers an attractive account would also select on the outcome. We have therefore reported the results as exact operating characteristics of stated channels. We make no estimate of how often travelers actually stand in rows or how frequently they lend the camera to strangers.

Larger groups frequently split up. Someone visiting a different room of a museum has an excellent reason for being absent from all the pictures in front of a particular exhibit. A stop-specific attendance roster can remove that person from the candidate list if the attendance observations are obtained independently [18]. Persistent nonattendance shared by the same few people at several stops induces dependence among extra edges. An independent-edges calculation with the correct marginal rate would still give a generally incorrect cycle probability. The matching characterization in Proposition 1 is deterministic and survives this change.

This allocation has a small historical asymmetry. Families tend to accession pictures of a person as evidence that the person went on a trip. Where turns were equally shared, an album with many identifiable pictures of everybody can also carry evidence of equal work, concentrated in the few pictures where each individual cannot be seen. Improving a print until it shows every last traveler can make it unsuitable for that particular use. For credit disputes the most useful surviving item may thus be the photographer’s turn sheet, even in a collection otherwise devoted entirely to pictures.

AArithmetic and independent checks

We computed Eq. (2) with rational probabilities, reducing the fractions after each operation, and rounded once for presentation. The sink sum has large terms of alternating sign even at , where induction gives . Double precision should not be used to extend the reported grid to much larger parties without checking cancellation. At and all arcs are present and . For two travelers , since these two travelers can exchange duties on paper only when both are missing from the stop where the other actually served.

To check the coefficient on intersecting sink events, consider . Among six optional directed arcs, a DAG has zero, one, two or three arcs. Its counts at those sizes are respectively. In particular . Treating the sinks as unordered independent events but omitting arcs between them would give the wrong result even for . In the substitution enumeration we used the actual operator at each stop as the always-present candidate. Reusing the diagonal from the permutation experiment would make a fair history feasible for every substituted trip by construction.

A small ledger is enough to reconstruct the tests. For integer row masks, bit of row is one if member can still be credited at stop . For each potential assignment take its bitwise membership tests and count a witness only if all pass. Stopping at the second witness distinguishes all three columns of Table 2. With no optional bits the substituted graph must be infeasible. With every optional bit it permits all 24 permutations. Under both checks the denominator for weighting a mask remains the number of optional positions, twelve. The mandatory edge in each row is present independently of exposure quality and does not receive a factor of .

BReading a partial catalog

Suppose a set of photographs is on loan during entry. Leave the corresponding stops in the circuit but set their candidate sets initially to the full roster. Provided there was one operator at each such stop, this treatment gives valid deductions conditional on the quota. It can result in a byline on a photograph which nobody making the catalog has seen: all other stops uniquely account for the other people. Such a credit belongs explicitly to the circuit record. The first positive sighting from the returned print may disprove the circuit agreement. If an entire stop was invented to fill a gap in an itinerary, this treatment would assume precisely what is missing, namely that there was a service event.

For a fully open component, a catalog can retain the stop numbers together with the candidate links belonging to some feasible match. Giving every stop every name in its component overstates the ambiguity when the component is not complete. To test one proposed link, force it, delete its row and column, then ask whether the remaining graph has a perfect matching. The answer describes the possible credit on the individual print. If two readers choose different feasible credits on different prints, the joint choice can still be inconsistent. The archival object in that case is the set of joint rotations, even when the user interface shows the names under one picture at a time.

Acknowledgments

We thank the Valdessa collections group for distinguishing subject names from creator credits in the original indexing question.

References

  1. [1]Malin Ciravelli. 2021. Attribution after a late correction to a catalog roster. Collection Records Quarterly (2021).
  2. [2]Rina Dechter. 2003. Constraint Processing. Morgan Kaufmann.
  3. [3]Alessia Dorvelin. 2016. People Outside the Family Frame. Ternale Academic Press.
  4. [4]Brian P. Gerkey and Maja J. Matarić. 2004. A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems. The International Journal of Robotics Research (2004).
  5. [5]Philip Hall. 1935. On Representatives of Subsets. Journal of the London Mathematical Society (1935).
  6. [6]John E. Hopcroft and Richard M. Karp. 1973. An n⁵⁄² Algorithm for Maximum Matchings in Bipartite Graphs. SIAM Journal on Computing (1973). https://doi.org/10.1137/0202019
  7. [7]Katalin Istrevi. 2023. Retaining the basis of a creator credit during catalog exchange. Studies in Descriptive Records (2023).
  8. [8]Harold W. Kuhn. 1955. The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly (1955).
  9. [9]Leslie Lamport. 1978. Time, Clocks, and the Ordering of Events in a Distributed System. Communications of the ACM (1978).
  10. [10]László Lovász and Michael D. Plummer. 1986. Matching Theory. North-Holland.
  11. [11]Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann.
  12. [12]Ela Pavritti and Toma Orvenal. 2019. Device ownership and creator attribution in donated image collections. In Proceedings of the Symposium on Small Digital Collections..
  13. [13]Jean-Charles Régin. 1994. A Filtering Algorithm for Constraints of Difference in CSPs. In Proceedings of the Twelfth National Conference on Artificial Intelligence..
  14. [14]Robert W. Robinson. 1973. Counting Labeled Acyclic Digraphs. In New Directions in the Theory of Graphs. Academic Press.
  15. [15]Adela Selnikar and Rafael Gunevi. 2020. Dependence between adjacent exposures in a shared portrait series. In Proceedings of the Meridan Workshop on Photographic Records..
  16. [16]Yoav Shoham and Kevin Leyton-Brown. 2009. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press.
  17. [17]Robert Tarjan. 1972. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing (1972).
  18. [18]Mikael Taronne and Devi Kalverri. 2024. Room attendance as auxiliary information for reconstructing itineraries. Journal of Itinerary Reconstruction (2024).
  19. [19]Leona Venicka and Tullio Amorevi. 2018. Separating depicted records from their carriers in household albums. Review of Photographic Collections (2018).
  20. [20]Samra Veradel and Ivar Jantelen. 2022. Linking recurrent places to distinct events in distributed trip records. Journal of Itinerary Reconstruction (2022).
  21. [21]Michael Wooldridge. 2002. An Introduction to MultiAgent Systems. John Wiley and Sons.